【MySQL】红黑树详解

红黑树是一种自平衡的二叉查找树，它具有以下特性：

节点颜色

• 每个节点要么是红色，要么是黑色
• 根节点必须是黑色
• 叶子节点(NIL)都是黑色

关键规则

• 红色节点的子节点必须是黑色（不能有连续的红色节点）
• 从根到任意叶子节点的路径上，黑色节点数量相同
• 让我们通过代码实现来理解红黑树：

public class RedBlackTree<T extends Comparable<T>> {
    // 定义节点颜色
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    
    // 节点类定义
    private class Node {
        T data;           // 节点数据
        Node left;        // 左子节点
        Node right;       // 右子节点
        Node parent;      // 父节点
        boolean color;    // 节点颜色
        
        Node(T data) {
            this.data = data;
            this.color = RED;    // 新插入的节点默认为红色
        }
    }
    
    private Node root;    // 根节点
    
    // 左旋操作
    private void leftRotate(Node x) {
        // 获取右子节点
        Node y = x.right;
        
        // 将y的左子树变为x的右子树
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        
        // 更新y的父节点
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        
        // 将x设为y的左子节点
        y.left = x;
        x.parent = y;
    }
    
    // 插入节点后的修复操作
    private void fixAfterInsertion(Node k) {
        Node u;  // 叔叔节点
        
        while (k.parent != null && k.parent.color == RED) {
            if (k.parent == k.parent.parent.left) {
                u = k.parent.parent.right;
                if (u != null && u.color == RED) {
                    // 情况1：叔叔节点为红色
                    k.parent.color = BLACK;
                    u.color = BLACK;
                    k.parent.parent.color = RED;
                    k = k.parent.parent;
                } else {
                    // 情况2和3：叔叔节点为黑色
                    if (k == k.parent.right) {
                        // 情况2：当前节点是右子节点
                        k = k.parent;
                        leftRotate(k);
                    }
                    // 情况3
                    k.parent.color = BLACK;
                    k.parent.parent.color = RED;
                    rightRotate(k.parent.parent);
                }
            } else {
                // 对称情况
                // ... 类似的代码，方向相反
            }
        }
        root.color = BLACK;  // 确保根节点为黑色
    }
}

红黑树的主要操作

插入操作

先按普通二叉查找树方式插入
将新节点着色为红色
通过旋转和重新着色来修复红黑树性质

删除操作

比插入更复杂
需要处理多种情况
可能需要多次旋转和重新着色

旋转操作

左旋：将节点向左旋转
右旋：将节点向右旋转
用于维持树的平衡

红黑树的优势

平衡性能
保证最坏情况下的时间复杂度为O(log n)
插入、删除、查找都是O(log n)
实际应用
Java的TreeMap和TreeSet
Linux内核的进程调度
数据库索引
相比AVL树
插入和删除时旋转次数更少
在写入密集的场景下性能更好

红黑树虽然实现复杂，但是它的自平衡特性使其在很多实际应用中表现优异，特别是在需要频繁插入删除的场景下。

原文地址：https://blog.csdn.net/2403_87669205/article/details/144037740

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！