红黑树与平衡二叉树的区别

定义

红黑树

**红黑树（Red-Black Tree）**是一种自平衡二叉查找树，每个节点上都有一个存储位表示节点的颜色（红或黑）。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，确保没有一条路径会比其他路径长出两倍，因此是接近平衡的。

平衡二叉树（AVL树）

**平衡二叉树（Balanced Binary Tree，通常指AVL树）**是一种高度平衡的二叉查找树，任何节点的两个子树的高度差不超过1。它通过旋转操作来维持平衡。

红黑树的性质

红黑树满足以下5条性质：

1. 每个节点要么是红色，要么是黑色
2. 根节点是黑色
3. 所有叶子节点（NIL节点，空节点）都是黑色
4. 如果一个节点是红色的，则它的子节点必须是黑色的（即不能有连续的红色节点）
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

AVL树的平衡因子

AVL树中每个节点都有一个平衡因子，表示该节点的左子树高度减去右子树高度的值。平衡因子只能是-1、0或1。

主要区别

平衡条件

操作效率

实现与空间

优缺点比较

红黑树

优点：

• 插入和删除操作比AVL树更快，因为需要更少的旋转操作
• 在频繁插入和删除的场景下性能更好

缺点：

• 查找效率略低于AVL树
• 实现和理解相对复杂

AVL树

优点：

• 查找效率高，因为树的高度更加平衡
• 在查找操作频繁的场景下性能更好

缺点：

• 插入和删除操作可能需要更多的旋转操作
• 实现也较为复杂

应用场景

红黑树

适用于插入、删除操作较多的场景，例如：

• C++ STL中的map和set
• Java中的TreeMap和TreeSet
• Linux内核中的完全公平调度器

AVL树

适用于查找操作较多，插入、删除操作较少的场景，例如：

• 数据库索引
• 文件系统

代码示例

红黑树节点定义和插入操作

enum Color { RED, BLACK };

struct RedBlackNode {
    int data;
    Color color;
    RedBlackNode *left;
    RedBlackNode *right;
    RedBlackNode *parent;
    
    RedBlackNode(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

class RedBlackTree {
private:
    RedBlackNode *root;
    
    void leftRotate(RedBlackNode *x) {
        // 左旋操作
        RedBlackNode *y = x->right;
        x->right = y->left;
        if (y->left != nullptr) {
            y->left->parent = x;
        }
        y->parent = x->parent;
        if (x->parent == nullptr) {
            root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
        y->left = x;
        x->parent = y;
    }
    
    void rightRotate(RedBlackNode *y) {
        // 右旋操作
        RedBlackNode *x = y->left;
        y->left = x->right;
        if (x->right != nullptr) {
            x->right->parent = y;
        }
        x->parent = y->parent;
        if (y->parent == nullptr) {
            root = x;
        } else if (y == y->parent->left) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }
        x->right = y;
        y->parent = x;
    }
    
    void insertFixup(RedBlackNode *z) {
        // 插入修复操作
        while (z->parent != nullptr && z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                RedBlackNode *y = z->parent->parent->right;
                if (y != nullptr && y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        leftRotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    rightRotate(z->parent->parent);
                }
            } else {
                // 对称情况
                RedBlackNode *y = z->parent->parent->left;
                if (y != nullptr && y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        rightRotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    leftRotate(z->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }
    
public:
    RedBlackTree() : root(nullptr) {}
    
    void insert(int data) {
        RedBlackNode *z = new RedBlackNode(data);
        RedBlackNode *y = nullptr;
        RedBlackNode *x = root;
        
        while (x != nullptr) {
            y = x;
            if (z->data < x->data) {
                x = x->left;
            } else {
                x = x->right;
            }
        }
        
        z->parent = y;
        if (y == nullptr) {
            root = z;
        } else if (z->data < y->data) {
            y->left = z;
        } else {
            y->right = z;
        }
        
        insertFixup(z);
    }
};

AVL树节点定义和插入操作

struct AVLNode {
    int data;
    int height;
    AVLNode *left;
    AVLNode *right;
    
    AVLNode(int data) : data(data), height(1), left(nullptr), right(nullptr) {}
};

class AVLTree {
private:
    AVLNode *root;
    
    int getHeight(AVLNode *node) {
        if (node == nullptr) return 0;
        return node->height;
    }
    
    int getBalanceFactor(AVLNode *node) {
        if (node == nullptr) return 0;
        return getHeight(node->left) - getHeight(node->right);
    }
    
    void updateHeight(AVLNode *node) {
        node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1;
    }
    
    AVLNode *rightRotate(AVLNode *y) {
        // 右旋操作
        AVLNode *x = y->left;
        AVLNode *T3 = x->right;
        
        x->right = y;
        y->left = T3;
        
        updateHeight(y);
        updateHeight(x);
        
        return x;
    }
    
    AVLNode *leftRotate(AVLNode *x) {
        // 左旋操作
        AVLNode *y = x->right;
        AVLNode *T2 = y->left;
        
        y->left = x;
        x->right = T2;
        
        updateHeight(x);
        updateHeight(y);
        
        return y;
    }
    
    AVLNode *insert(AVLNode *node, int data) {
        // 标准BST插入
        if (node == nullptr) {
            return new AVLNode(data);
        }
        
        if (data < node->data) {
            node->left = insert(node->left, data);
        } else if (data > node->data) {
            node->right = insert(node->right, data);
        } else {
            return node; // 不允许重复值
        }
        
        // 更新高度
        updateHeight(node);
        
        // 获取平衡因子
        int balance = getBalanceFactor(node);
        
        // 如果不平衡，有4种情况
        
        // 左左情况
        if (balance > 1 && data < node->left->data) {
            return rightRotate(node);
        }
        
        // 右右情况
        if (balance < -1 && data > node->right->data) {
            return leftRotate(node);
        }
        
        // 左右情况
        if (balance > 1 && data > node->left->data) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
        
        // 右左情况
        if (balance < -1 && data < node->right->data) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
        
        return node;
    }
    
public:
    AVLTree() : root(nullptr) {}
    
    void insert(int data) {
        root = insert(root, data);
    }
};

可视化对比

参考链接

1. 红黑树 - 维基百科
2. AVL树 - 维基百科
3. Red-Black Tree - GeeksforGeeks
4. AVL Tree - GeeksforGeeks
5. 红黑树详解 - 图解