一起学习交流~

红黑树-01-红黑树的特性和基本结构

算法 laomuji 10个月前 (11-26) 486次浏览 已收录 0个评论

建议先去看AVL再来看红黑树,红黑树实现起来要比AVL麻烦

一、什么是红黑树

百度百科解释如下:

也就是说 红黑树本质上还是一个二叉查找树,只不过需要旋转变色

红黑树有以下性质:

性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。(叶子是NIL结点)
性质4. 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。

二、红黑树的优缺点

优点:

功能、性能、空间开销的折中结果, 时间复杂度都是logn

缺点:

实现起来很麻烦

和AVL树进行比较:

很多教材上说,红黑树查找比AVL树慢,但插入删除比AVL快,

但实际上 经过优化的AVL树,插入删除速度并不逊色红黑树

知乎大神的回答:https://www.zhihu.com/question/19856999/answer/258118494

三、节点信息

节点要比正常的节点多了一些

   /*
        红黑树的颜色
        BLACK
        RED
    */
    enum class COLOR {BLACK, RED};
    /*
        红黑树的节点
        不仅存储值和左右子节点
        还存储颜色,父节点
    */
    struct Node{
         T value;//节点值
         Node* left;//左孩子
         Node* right;//右孩子
         RBTree::COLOR color;//颜色
         Node* parent;//父节点
    };

四、旋转

红黑树的左旋和右旋和AVL树很相似,但是多了一个变色的操作

    /*
        红黑树左旋
    */
    void leftRotate(Node*x) {
        Node* y = x->parent;
        Node* z = y->parent;
        x->parent = z;
        if (z == nullptr) {
            root = x;
        }
        else if (z->left == y){
            z->left = x;
        }
        else {
            // if (z->right == y)
            z->right = x;
        }
        y->right = x->left;
        if (x->left != nullptr)x->left->parent = y;
        x->left = y;
        y->parent = x;
    }
    /*
        红黑树右旋
    */
    void rightRotate(Node* x) {
        Node* y = x->parent;
        Node* z = y->parent;
        x->parent = z;
        if (z == nullptr) {
            root = x;
        }
        else if (z->left == y) {
            z->left = x;
        }
        else {
            // if (z->right == y)
            z->right = x;
        }
        y->left = x->right;
        if (x->right != nullptr)x->right->parent = y;
        x->right = y;
        y->parent = x;
    }
喜欢 (2)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论