大师兄的数据结构学习笔记(十二）: 红黑树

大师兄的数据结构学习笔记(十一）: B树
 大师兄的数据结构学习笔记(十三）: KD树

一、关于红黑树

1. 比较两种平衡二叉树的优劣

类型	优点	缺点
伸展树	- 实现简便 - 无需修改结点结构 - 分摊复杂度低	最坏情况下单次操作耗时 $\Omega(n)$
AVL树	最坏情况下单次操作速度 $\Omega(\log n)$	- 需要在结点中嵌入平衡因子等标识 - 删除操作之后的重平衡可能需要做多达 $\Omega(\log n)$ 次旋转

红黑树针对AVL树的不足进行了改进，通过指定结点颜色，并巧妙地动态调整，可保证在每次插入或删除操作之后的重新平衡过程中，全树拓扑结构的更新涉及常数个结点。

2. 关于红黑树

红黑树(Red Black Tree)是红、黑两色节点组成的二叉搜索树，且满足以下条件：

1) 树根始终为黑色。
2) 外部节点均为黑色。
3) 其余节点若为红色，则其孩子结点必为黑色。
4) 从任一外部节点到根节点的沿途，黑结点的数目相等。

根据以上条件，可以获得一些隐含的条件：

1) 红节点均为内部节点，且其父、左、右孩子节点必然存在。
2) 红节点之父节点必为黑色, 因此不存在相邻的红节点。
3) 从根节点通往任一节点，黑节点不少于红节点。
4) 所有外部节点的黑深度统一。

从根节点到任一节点，沿途所经黑节点的总数成为该节点的黑深度(black depth)，根节点的深度为0。
从任一节点通往其任一后代外部节点的沿途，出去外部节点，途径的黑色节点总数称为该节点的黑高度(black height), 外部节点的黑高度为0。

3. 红黑树与B树

如果将一颗红黑树自顶而下逐层转换。
每遇到一个红节点，都将对应的子树整体提升一层，与父节点水平对齐，并将二者之间的联边相应调整为横向。
则可以转换为B树。

4. 红黑树的平衡性

红黑树不能如完全二叉树那样做到立项平衡。
也不如AVL树那样做到较严格的适度平衡。
但其高度扔控制在最小高的两倍以内，即: $h\leq2H\leq2\log_2(n+1) = \sigma(logn)$ 。

二、红黑树的调整

当插入或删除结点时，红黑树的规则有可能被打破，这时就需要通过变色或旋转来维持规则。

1. 旋转

红黑树的旋转规则可参考二叉搜索树。

2. 变色

在红黑树调整时，为了重新符合红黑树的规则，会尝试把红色节点变为黑色，或者把黑色节点变为红色。

2.1 双红修正

由于插入新节点，导致父子节点同为红色的情况，称为双红(double red)。
情况一: 叔父节点为黑色

1) 将x的父亲与祖父分别记作p和g。既然此前的红黑树合法,故作为红节点p的父亲,g必然存在且为黑色。
2) g作为内部节点,其另一孩子(即p的兄弟、x的叔父)也必然存在,将其记作u。

3) 将黑节点g调整到中间重构即可。

情况二: 叔父节点为红色

1) 在这种情况下，需要将相邻的结点染色，以满足红黑树规则。

template<class T>
void RBTree<T>::insertFixUp(RBTNode<T>*& root, RBTNode<T>* node)
{
    RBTNode<T>* parent, * gparent;

    // 若父节点存在，并且父节点的颜色是红色
    while ((parent = node->parent) && parent->color==RED)
    {
        gparent = parent->parent;

        if (parent == gparent -> lc)    // 若父节点是祖父结点的左孩子
        {
            //如果叔叔节点是红色
            RBTNode<T>* uncle = gparent->rc;
            if (uncle && uncle->color == RED)
            {
                uncle->color = BLACK; // 改变颜色
                parent->color = BLACK;
                gparent->color = RED;
                node = gparent;
                continue;
            }

            //若叔叔节点是黑色，并且当前节点是右孩子
            if (parent->rc == node)
            {
                RBTNode<T>* tmp;
                leftRotate(root, parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            //若叔叔节点是黑色，并且当前节点是左孩子
            parent->color = BLACK;
            gparent->color = RED;
            rightRotate(root, gparent);
        }
        else //若父节点是祖父结点的右孩子
        {
            // 如果叔叔节点是红色
            RBTNode<T>* uncle = gparent->lc;
            if (uncle && uncle->color == RED)
            {
                uncle->color = BLACK;
                parent->color = BLACK;
                gparent->color = RED;
                node = gparent;
                continue;
            }
        
            // 如果叔叔是黑色，并且当前节点是左孩子
            if (parent->lc == node)
            {
                RBTNode<T>* tmp;
                rightRotate(root, parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            // 如果叔叔是黑色，且当前节点是右孩子
            parent->color = BLACK;
            gparent->color = RED;
            leftRotate(root, gparent);
        }
    }

    root->color = BLACK; // 根节点设为黑色
}

2.2 双黑修正

在删除节点时，如果由于被删除节点和替换节点同为黑色，导致红黑树的黑高度不同的情况，称为双黑(double black)。
情况一: 待删除结点的兄弟结点为黑色，且至少有一个红孩子

1) 通过关键码的旋转消除超级节点的下溢。

情况二b: 待删除结点的兄弟结点为黑色，且两个孩子均为黑，父节点为黑

1) 兄弟结点转红

情况二r: 待删除结点的兄弟结点为黑色，且两个孩子均为黑，父节点为红

1) 兄弟结点转红。

情况三: 兄弟结点为红

1) zap(p)或zig(p)
2) 红s转黑，黑p转红

template<class T>
void RBTree<T>::removeFixUp(RBTNode<T>*& root, RBTNode<T>* node, RBTNode<T>* parent)
{
    RBTNode<T>* other;//node的兄弟节点
    while ((!node || node->color == BLACK) && node != root) //node为非根节点、为空或为黑色节点
    {
        if (parent->lc == node) //如果是左孩子
        {
            other = parent->rc;
            if (other->color == RED) // 如果兄弟为红
            {
                other->color = BLACK;
                parent->color = RED;
                leftRotate(root, parent);
                other = parent->rc;
            }
            if ((!other->lc || other->lc->color == BLACK) && (!other->rc || other->rc->color == BLACK))
            {
                //如果兄弟和兄弟的孩子节点都是黑
                other->color = RED;
                node = parent;
                parent = node->parent;
            }
            else
            {
                if (!other->rc || other->rc->color == BLACK)
                {
                    //如果兄弟的右孩子是黑色
                    other->lc->color = BLACK;
                    other->color = RED;
                    rightRotate(root, other);
                    other = parent->rc;
                }
                //如果右孩子是红色的
                other->color = parent->color;
                parent->color = BLACK;
                other->lc->color = BLACK;
                rightRotate(root, parent);
                node = root;
                break;
            }
        }
    }
    if (node)
    {
        node->color = BLACK;
    }
}

三、实现红黑树

1. 节点结构

#ifndef _REDBLACKTREE_H_
#define _REDBLACKTREE_H_

#include <iostream>
#include <iomanip>
using namespace std;
enum RBTColor{RED,BLACK};

template<class T>
class RBTNode
{
public:
    RBTColor color;     //红黑色
    T key;              //键值 
    RBTNode* lc;        //左子树
    RBTNode* rc;        //右子树
    RBTNode* parent;    //父节点

    RBTNode(T value, RBTColor c,RBTNode*p,RBTNode *l,RBTNode *r):
        key(value), color(c),parent(),lc(l),rc(r){}
};

2. 树结构

template<class T>
class RBTree {
public:
    RBTree() :_root(nullptr) { _root = nullptr; };          //构造函数
    ~RBTree() { destroy(); };           //析构函数
    void preOrder();    //前序遍历
    void inOrder();     //中序遍历
    void postOrder();   //后序遍历
    RBTNode<T>* search(T key); //查找节点
    T minimum();        //最小值
    T maximum();        //最大值
    RBTNode<T>* successor(RBTNode<T>* x); //找数值大于x的最小结点
    RBTNode<T>* predecessor(RBTNode<T>* x); //找数值小于x的最大结点
    void insert(T key); //插入结点
    void remove(T key); //删除结点
    void destroy();     //销毁红黑树
    void print();       //打印结点
private:
    void preOrder(RBTNode<T>* tree) const; //先序遍历
    void inOrder(RBTNode<T>* tree) const; //中序遍历
    void postOrder(RBTNode<T>* tree) const; //后序遍历
    RBTNode<T>* search(RBTNode<T>* x, T key) const; //查找节点
    RBTNode<T>* minimum(RBTNode<T>* tree);  //最小节点
    RBTNode<T>* maximum(RBTNode<T>* tree);  //最大节点
    void leftRotate(RBTNode<T>*& root, RBTNode<T>* x); //左旋
    void rightRotate(RBTNode<T>*& root, RBTNode<T>* x); //右旋
    void insert(RBTNode<T>*& root, RBTNode<T>* node); //插入函数
    void insertFixUp(RBTNode<T>*& root, RBTNode<T>* node); //插入修正函数
    void remove(RBTNode<T>*& root, RBTNode<T>* node); //删除函数
    void removeFixUp(RBTNode<T>*& root, RBTNode<T>* node, RBTNode<T>* parent); //删除修正函数
    void destroy(RBTNode<T>*& tree);
    void print(RBTNode<T>* tree, T key, int direction);
private:
    RBTNode<T>* _root; //根节点
};

3. 方法实现

template<class T>
// 先序遍历
void RBTree<T>::preOrder(RBTNode<T>* tree) const
{
    if (tree)
    {
        cout << tree->key << endl;
        preOrder(tree->lc);
        preOrder(tree->rc);
    }
}

template<class T>
// 先序遍历
void RBTree<T>::preOrder()
{
    preOrder(_root);
}

template<class T>
// 中序遍历
void RBTree<T>::inOrder(RBTNode<T>* tree) const
{
    if (tree)
    {
        preOrder(tree->lc);
        cout << tree->key << endl;
        preOrder(tree->rc);
    }
}

template<class T>
// 中序遍历
void RBTree<T>::inOrder()
{
    inOrder(_root);
}

template<class T>
// 后序遍历
void RBTree<T>::postOrder(RBTNode<T>* tree) const
{
    if (tree)
    {
        preOrder(tree->lc);
        preOrder(tree->rc);
        cout << tree->key << endl;
    }
}

template<class T>
// 后序遍历
void RBTree<T>::postOrder()
{
    postOrder(_root);
}

template<class T>
//查找节点
RBTNode<T>* RBTree<T>::search(RBTNode<T>* x, T key) const
{
    if (x == nullptr || x->key == key)
    {
        return x;
    }
    if (key < x->key)
    {
        return search(x->lc,key);
    }
    else
    {
        return search(x->rc, key);
    }
}

template<class T>
//查找节点
RBTNode<T>* RBTree<T>::search(T key)
{
    serch(_root, key);
}

template<class T>
//最小节点
RBTNode<T>* RBTree<T>::minimum(RBTNode<T>* tree)
{   
    if (!tree) {
        return nullptr;
    }
    while (tree->lc)
    {
        tree = tree->lc;
    }
    return tree;
}

template<class T>
//最小节点
T RBTree<T>::minimum()
{
    RBTNode<T>* p = minimum(_root);
    if (p)
    {
        return p->key;
    }
    return (T)nullptr;
}


template<class T>
//最大节点
RBTNode<T>* RBTree<T>::maximum(RBTNode<T>* tree)
{
    if (!tree) {
        return nullptr;
    }
    while (tree->rc)
    {
        tree = tree->rc;
    }
    return tree;
}

template<class T>
//最大节点
T RBTree<T>::maximum()
{
    RBTNode<T>* p = maximum(_root);
    if (p)
    {
        return p->key;
    }
    return (T)nullptr;
}

template<class T>
//左旋
void RBTree<T>::leftRotate(RBTNode<T>*& root, RBTNode<T>* x)
{
    RBTNode<T>* y = x->rc;  // x的右子树设为y
    x->rc = y->lc; //向左旋转
    if (y->lc)
        y->lc->parent = x; //更新父节点为x

    y->parent = x->parent; //重设y的父节点为x的父节点
    if (!x->parent) //如果是根节点
    {
        _root = y; 
    }
    else
    {
        if (x->parent->lc == x)
        {
            x->parent->lc = y;
        }
        else
        {
            x->parent->rc = y;
        }
    }

    y->lc = x; //完成旋转的后半部分
    x->parent = y; 
}

template<class T>
//右旋
void RBTree<T>::rightRotate(RBTNode<T>*& root, RBTNode<T>* x)
{
    RBTNode<T>* y = x->lc;  // x的左子树设为y
    x->lc = y->rc; //向左旋转
    if (y->rc)
        y->rc->parent = x; //更新父节点为x

    y->parent = x->parent; //重设y的父节点为x的父节点
    if (!x->parent) //如果是根节点
    {
        _root = y;
    }
    else
    {
        if (x->parent->lc == x)
        {
            x->parent->lc = y;
        }
        else
        {
            x->parent->rc = y;
        }
    }

    y->rc = x; //完成旋转的后半部分
    x->parent = y;
}

template<class T>
//插入函数
void RBTree<T>::insert(RBTNode<T>*& root, RBTNode<T>* node)
{
    RBTNode<T>* y = nullptr;
    RBTNode<T>* x = root;

    // 添加节点到树
    while (x)
    {
        y = x;
        if (node->key < x->key)
        {
            x = x->lc;
        }
        else {
            x = x->rc;
        }
    }

    node->parent = y;
    if (y)
    {
        if (node->key < y->key)
        {
            y->lc = node;
        }
        else {
            y->rc = node;
        }
    }
    else
    {
        root = node;
    }

    // 设定节点颜色
    node->color = RED;

    // 修正树
    insertFixUp(root, node);
}

template<class T>
//插入修正函数
void RBTree<T>::insertFixUp(RBTNode<T>*& root, RBTNode<T>* node)
{
    RBTNode<T>* parent, * gparent;

    // 若父节点存在，并且父节点的颜色是红色
    while ((parent = node->parent) && parent->color==RED)
    {
        gparent = parent->parent;

        if (parent == gparent -> lc)    // 若父节点是祖父结点的左孩子
        {
            //如果叔叔节点是红色
            RBTNode<T>* uncle = gparent->rc;
            if (uncle && uncle->color == RED)
            {
                uncle->color = BLACK; // 改变颜色
                parent->color = BLACK;
                gparent->color = RED;
                node = gparent;
                continue;
            }

            //若叔叔节点是黑色，并且当前节点是右孩子
            if (parent->rc == node)
            {
                RBTNode<T>* tmp;
                leftRotate(root, parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            //若叔叔节点是黑色，并且当前节点是左孩子
            parent->color = BLACK;
            gparent->color = RED;
            rightRotate(root, gparent);
        }
        else //若父节点是祖父结点的右孩子
        {
            // 如果叔叔节点是红色
            RBTNode<T>* uncle = gparent->lc;
            if (uncle && uncle->color == RED)
            {
                uncle->color = BLACK;
                parent->color = BLACK;
                gparent->color = RED;
                node = gparent;
                continue;
            }
        
            // 如果叔叔是黑色，并且当前节点是左孩子
            if (parent->lc == node)
            {
                RBTNode<T>* tmp;
                rightRotate(root, parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            // 如果叔叔是黑色，且当前节点是右孩子
            parent->color = BLACK;
            gparent->color = RED;
            leftRotate(root, gparent);
        }
    }

    root->color = BLACK; // 根节点设为黑色
}

template<class T>
//插入结点
void RBTree<T>::insert(T key)
{
    RBTNode<T>* z = nullptr;
    
    if ((z = new RBTNode<T>(key, BLACK, nullptr, nullptr, nullptr)) == nullptr)
    {
        return;
    }

    insert(_root, z);
}

template<class T>
//删除函数
void RBTree<T>::remove(RBTNode<T>*& root, RBTNode<T>* node)
{
    RBTNode<T>* child, * parent;
    RBTColor color;
    
    // 如果被删除节点左右孩子都存在
    if (node->lc && node->rc)
    {
        RBTNode<T>* replace = node; //取代的结点

        //获取后继节点
        replace = replace->rc;
        while (replace->lc)
        {
            replace = replace->lc;
        }
        if (node->parent) // 如果不是根节点
        {
            if (node->parent->lc == node) // 如果是左结点
            {
                node->parent->lc = replace;
            }
            else
            {
                node->parent->rc = replace;
            }
        }
        else
        {
            root = replace; //更新根节点
        }

        child = replace->rc; //replace必然不存在左孩子
        parent = replace->parent;  //保存父节点
        color = replace->color; //保存颜色

        if (parent == node) //如果被删除节点是后继街店的父节点
        {
            parent = replace;
        }
        else
        {
            if (child)
            {
                child->parent = parent;
            }
            parent->lc = child;

            replace->rc = node->rc;
            node->rc->parent = replace;
        }

        replace->parent = node->parent;
        replace->color = node->color;
        replace->lc = node->lc;
        node->lc->parent = replace;

        if (color == BLACK)
        {
            removeFixUp(root, child, parent);
        }
        delete node;
        return;
    }

    if (node->lc)
    {
        child = node->lc;
    }
    else
    {
        child = node->rc;
    }

    parent = node->parent;
    color = node->color;

    if (child)
    {
        child->parent = parent;
    }

    if (parent)
    {
        if (parent->lc = node)
        {
            parent->lc = child;
        }
        else
        {
            parent->rc = child;
        }
    }
    else
    {
        root = child;
    }

    if (color == BLACK)
    {
        removeFixUp(root, child, parent);
    }
    delete node;
}

template<class T>
//删除修正函数
void RBTree<T>::removeFixUp(RBTNode<T>*& root, RBTNode<T>* node, RBTNode<T>* parent)
{
    RBTNode<T>* other;//node的兄弟节点
    while ((!node || node->color == BLACK) && node != root) //node为非根节点、为空或为黑色节点
    {
        if (parent->lc == node) //如果是左孩子
        {
            other = parent->rc;
            if (other->color == RED) // 如果兄弟为红
            {
                other->color = BLACK;
                parent->color = RED;
                leftRotate(root, parent);
                other = parent->rc;
            }
            if ((!other->lc || other->lc->color == BLACK) && (!other->rc || other->rc->color == BLACK))
            {
                //如果兄弟和兄弟的孩子节点都是黑
                other->color = RED;
                node = parent;
                parent = node->parent;
            }
            else
            {
                if (!other->rc || other->rc->color == BLACK)
                {
                    //如果兄弟的右孩子是黑色
                    other->lc->color = BLACK;
                    other->color = RED;
                    rightRotate(root, other);
                    other = parent->rc;
                }
                //如果右孩子是红色的
                other->color = parent->color;
                parent->color = BLACK;
                other->lc->color = BLACK;
                rightRotate(root, parent);
                node = root;
                break;
            }
        }
    }
    if (node)
    {
        node->color = BLACK;
    }
}

template<class T>
//删除结点
void RBTree<T>::remove(T key)
{
    RBTNode<T> *res = search(_root, key);
    if (res)
    {
        remove(_root, res);
    }
}

template<class T>
void RBTree<T>::destroy(RBTNode<T>*& tree)
{
    if (!tree)return;

    if (tree->lc) 
    {
        return destroy(tree->lc);
    }
    if (tree->rc)
    {
        return destroy(tree->rc);
    }
    delete tree;
    tree = nullptr;
}

template<class T>
//销毁红黑树
void RBTree<T>::destroy()
{
    destroy(_root);
}

template<class T>
void RBTree<T>::print(RBTNode<T>* tree, T key, int direction)
{
    if (tree)
    {
        if (direction == 0)
        {
            cout << setw(2) << tree->key << "(B) is root" << endl;
        }
        else
        {
            cout << setw(2) << tree->key << (tree->color == RED ? "(R)" : "(B)");
        }
        print(tree->lc, tree->key, -1);
        print(tree->rc, tree->key, 1);
    }
}

template<class T>
void RBTree<T>::print()
{
    if (_root)
    {
        print(_root, _root->key, 0);
    }
}

template<class T>
//找数值大于x的最小结点
RBTNode<T>* RBTree<T>::successor(RBTNode<T>* x)
{
    if (x->rc) //如果存在右孩子
    {
        return minimum(x->rc);
    }
    //如果不存在右孩子
    RBTNode<T>* y = x->parent;
    while (y && x == y->rc)
    {
        x = y;
        y = y->parent;
    }
    return y;
}

template<class T>
//找数值小于x的最大结点
RBTNode<T>* RBTree<T>::predecessor(RBTNode<T>* x)
{
    if (x->lc) //如果存在左孩子
    {
        return maximum(x->lc);
    }
    //如果不存在左孩子
    RBTNode<T>* y = x->parent;
    while (y && x == y->lc)
    {
        x = y;
        y = y->parent;
    }
    return y;
}
#endif

最后编辑于：2020.12.09 11:15:49

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,588评论 6赞 496
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,456评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,146评论 0赞 350
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,387评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,481评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,510评论 1赞 293
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,522评论 3赞 414
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,296评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,745评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,039评论 2赞 330
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,202评论 1赞 343
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,901评论 5赞 338
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,538评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,165评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,415评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,081评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,085评论 2赞 352

大师兄的数据结构学习笔记(十二）: 红黑树

一、关于红黑树

1. 比较两种平衡二叉树的优劣

2. 关于红黑树

3. 红黑树与B树

4. 红黑树的平衡性

二、红黑树的调整

1. 旋转

2. 变色

2.1 双红修正

2.2 双黑修正

三、实现红黑树

1. 节点结构

2. 树结构

3. 方法实现

推荐阅读更多精彩内容