内容

红黑树

红黑树

在计算机科学中，红黑树是一种自平衡二叉搜索树。典型用途是实现关联数组(即map)。红黑树是从 4 阶 B 树（即2-3-4树）衍生出来的形式。

以下内容来自wiki：https://en.wikipedia.org/wiki/Red–black_tree
1972年，鲁道夫·拜耳发明了一种B 树的特殊 4 阶形式。这个 4 阶 B 树维护从根到叶的所有路径，节点数相同，从而创建完美平衡的树（然而，并不是二叉搜索树）。拜尔在他的论文中称呼他们为“对称二叉 B 树”（symmetric binary B-tree），后来这种 4 阶 B 树被称为2-3-4 树。

在 1978 年的论文《A Dichromatic Framework for Balanced Trees》中，Leonidas J. Guibas和Robert Sedgewick从 2-3-4 树中衍生出了红黑树。

之所以选择“红色”是因为它是作者在Xerox PARC工作时可用的彩色激光打印机打印出的最好看的颜色。Guibas 的另一个回应是，这是因为他们可以使用红色和黑色的笔来画树。

1993 年，Arne Andersson 提出右倾树的概念，以简化插入和删除操作。
1999 年， Chris Okasaki展示了如何使插入操作纯粹函数化（purely functional）。其平衡函数只需要处理 4 种不平衡情况和 1 种默认平衡情况。
原始算法需要处理 8 种不平衡情况，但 2001 年，Cormen 等人将其简化为 6 种不平衡情况。Sedgewick 通过实践证明，插入操作仅需46行Java代码即可实现。
2008 年，Sedgewick 基于 Arne Andersson 简化插入和删除操作的理念，提出了左倾红黑树。该结构初期允许节点拥有两个红色子节点（更接近2-3-4树特性），后期通过增加节点限制使其更贴近2-3树结构。改进后，Sedgewick将插入算法的代码量从46行精减至33行，显著提升了代码效率。

每个节点存储一个表示“颜色”（“红色”或“黑色”）的额外位，用于确保树在插入和删除期间保持平衡。

当树被修改时，新树被重新排列并“重新绘制”以恢复限制树在最坏情况下可能变得多么不平衡的着色属性。这些属性被设计成可以有效地执行这种重新排列和重新着色。

重新平衡并不完美，但保证在 $O(\log n)$ 时间内搜索，其中 $n$ 是条目数。插入和删除操作以及树的重新排列和重新着色也在 $O(\log n)$ 时间内执行。

跟踪每个节点的颜色只需要每个节点的一位信息，因为只有两种颜色。该树不包含任何其他特定于它是红黑树的数据，因此它的内存占用几乎与经典（未着色）二叉搜索树的内存占用相同。在许多情况下，无需额外的内存成本即可存储额外的信息位。

红黑树与AVL的对比

实际上树节点的结构与AVL一模一样, 只是balance的状态值只有两个, 然后又在这个基础上, 对其进行了一些限制;

这样的好处就是, 对于红黑树的插入/删除操作, 在编写代码时, 只需考虑其两种状态即可, 这有利于开发实践; 而AVL需要考虑三种状态, 对于开发代码来说难度加大, 并且AVL树过于理想化, 导致旋转操作过多, 反而会影响性能;

AVL树本来想解决什么问题呢? 是为了防止不加限制的二叉搜索树在持续插入一些极端的值(依次插入有序的数)后, 搜索树的结构退化为了一个长度为n的链表, 因此查找性能也会退化;

但是, 对二叉搜索树的极度限制, 使其保持一个理想化的平衡又显得矫枉过正, 虽然插入数据时不用做过多的旋转(最多做2次旋转操作), 但是删除操作的时候, 可能会涉及到一长串的旋转处理( $\log n$ 次), 这也会导致性能的退化;

于是, 红黑树的性质就像是同时克服了两者的缺点, 但是在高度平衡上, 做出了一些妥协, 但是这也是无伤大雅的, 红黑树节点的左右子树高度差, 长的长度不超过短的长度的2倍;

操作	AVL的时间复杂度	红黑树的时间复杂度
增删查	$O(\log n)$	$O(\log n)$
Insert最多旋转次数	2	2
remove最多旋转次数	$O(\log n)$	3

根据上表, 可以得出, 如果操作涉及到查询/插入较多, 优先选择AVL树, AVL是绝对平衡的树, 查询效率不会低于红黑树; 而插入效率两者等效;

如果操作涉及修改较多, 查询不多, 则选择红黑树; 除此之外, 红黑树在百万级数据或更大规模的数据场景中表现将会脱颖而出;

如果增删查三者操作都比较多, 红黑书综合性能要更优;

红黑树的性质

红黑树是每个节点都带有颜色属性的二叉查找树，颜色是红色或黑色。基于二叉查找树的强制要求，对于任何有效的红黑树我们增加了如下的额外要求：

每个节点不是红色就是黑色。
如果左右孩子是NIL, 则把此孩子看作黑色节点; 实际上这个NIL节点是哨兵节点, 可看作一个公共叶子节点;
根节点是黑色。
从每个叶子到根的所有路径上不能有两个连续的红色节点; 如此, 每个红色节点的两个子节点都是黑色。
从任一节点到其每个叶子(可以包含NIL公共叶节点)的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

是性质4导致路径上不能有两个连续的红色节点确保了这个结果。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

思考: 为什么满足上面的性质，红黑树就能保证: 其最长路径中节点个数不会超过最短路径节点个数的两倍(红黑树节点的左右子树高度差, 长的长度不超过短的长度的2倍; )？

可以做个假设: 一个节点到其叶子节点1, 全部是黑色节点, 共10个; 而到其叶子节点2, 黑红节点交替, 共20个, 这种是满足性质5最大的极限了, 由于性质5的限制, 其最长路径中节点个数不会超过最短路径节点个数的两倍;

用途和好处

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。不只在时间敏感的应用如实时应用（real time application）中有价值; 而且在提供最坏情况担保的其他数据结构中作为基础模板有价值, 例如，在计算几何中使用的很多数据结构都可以基于红黑树实现。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构（persistent data structure）之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了 $O(\log n)$ 的时间之外，红黑树的持久版本对每次插入或删除需要 $O(\log n)$ 的空间。

红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。

红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

RB树的结构设计

红黑树相比于AVL树, 有一个伎俩, 就是设置了一个哨兵节点, 作为每个叶节点的左右孩子, 或者是: 不为叶节点, 但有一孩子指针为空时指向的一个节点, 这会使编程难度降低;

还可以引入一个作为整个红黑树的头节点, 双亲指针指向红黑树根节点, 左孩子指针指向红黑树最左节点(最小值), 右孩子指针指向红黑树最右节点(最大值), 根节点的双亲指针指向该头节点;

节点结构

typedef enum { RED = 0, BLACK = 1 } ColorType;
typedef int KeyType;
typedef struct rb_node
{
    rb_node * leftchild;
    rb_node * parent;
    rb_node * rightchild;
    ColorType color;
    KeyType key;
}rb_node, *RBTree;
static rb_node *NIL = BuyNode();

新建节点函数 - BuyNode

rb_node * BuyNode()
{
    rb_node * s = (rb_node*)malloc(sizeof(rb_node));
    if(nullptr == s) exit(1);
    memset(s, 0, sizeof(rb_node));
    s->leftchild = NIL;
    s->rightchild = NIL;
    s->color = RED;		//出生的红黑树节点默认为红色
    return s;
}

插入

建根函数

rb_node * MakeRoot(KeyType kx)
{
    rb_node * root = BuyNode();
    root->color = BLACK;		//默认根节点为黑色
    root->key = kx;
    return root;
}

Insert

bool Insert(rb_node *& tree, KeyType kx)
{
    if(tree == nullptr)
    {
        tree = MakeRoot(kx);
        return true;
    }
    rb_node * pa = nullptr;
    rb_node * p = tree;
    while(p != nullptr && p->key != kx)
    {
        pa = p;
        p = kx < p->key ? p->leftchild : p->rightchild;
    }
    if(p != nullptr && p->key == kx) return false;
    p = BuyNode();
    p->key = kx;
    p->parent = pa;
    if(kx < pa->key)
    {
        pa->leftchild = p;
    }
    else
    {
        pa->rightchild = p;
    }
    PassRBTree(tree, p);    //红黑树调整
    return true;
}

红黑树调整

左单旋 - RotateLeft

void RotateLeft(rb_node *& tree, rb_node * ptr)
{
    rb_node * newroot = ptr->rightchild;
    newroot->parent = ptr->parent;
    ptr->rightchild = newroot->leftchild;  //1 原根继承 轴节点的左孩子
    if(newroot->leftchild != nullptr)
    {
        newroot->leftchild->parent = ptr;  
    }
    
    newroot->leftchild = ptr;              //2 轴节点包揽原根
    //3 处理 原根父节点(或无父节点) 的左右孩子指针(或tree指针)
    if(ptr == tree)
    {
        tree = newroot;
    }
    else
    {
        if(ptr->parent->leftchild == ptr)
        {
            ptr->parent->leftchild = newroot;
        }
        else
        {
            ptr->parent->rightchild = newroot;
        }
    }
    
    ptr->parent = newroot;
}

右单旋 - RotateRight

void RotateRight(rb_node *& tree, rb_node * ptr)
{
    rb_node * newroot = ptr->leftchild;
    newroot->parent = ptr->parent;
    ptr->leftchild = newroot->rightchild;
    if(newroot->rightchild != nullptr)
    {
        newroot->rightchild->parent = ptr;
    }
    newroot->rightchild = ptr;
    if(ptr == tree)
    {
        tree = newroot;
    }
    else
    {
        if(ptr->parent->leftchild == ptr)
        {
            ptr->parent->leftchild = newroot;
        }
        else
        {
            ptr->parent->rightchild = newroot;
        }
    }
    ptr->parent = newroot;
}

调整函数

对红黑树修改时, 出现不平衡或颜色冲突, 对其调整使其平衡, 颜色正确的函数

void PassRBTree(rb_node *& tree, rb_node *p)
{
    rb_node * _X = nullptr;
    for(; p != tree && p->parent->color == RED; )
    {
        if(p->parent->parent->rightchild == p->parent)//说明在爷爷的右边插入
        {
            _X = p->parent->parent->leftchild;
            if(_X->color == RED)
            {
                _X->color = BLACK;
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                p = p->parent->parent;	//接下来循环看他爷爷的双亲是不是红
            }
            else //左单旋
            {
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                RotateLeft(tree, p->parent->parent);
            }
        }
        else
        {
            
        }
        
    }
    tree->color = BLACK;
}

加上双旋的情况

void PassRBTree(rb_node *& tree, rb_node *p)
{
    rb_node * _X = nullptr;
    for(; p != tree && p->parent->color == RED; )
    {
        if(p->parent->parent->rightchild == p->parent)//说明在爷爷的右边插入
        {
            _X = p->parent->parent->leftchild;
            if(_X->color == RED)
            {
                _X->color = BLACK;
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                p = p->parent->parent;	//接下来循环看他爷爷的双亲是不是红
            }
            else
            {
                if(p->parent->leftchild == p)//在父节点的左边, 需要双旋
                {
                    p = p->parent;       //关键一步, 偷换p, 以与下面语句串联
                    RotateRight(tree, p);//这是双旋第1步, 之后p调到其父节点的右边了
                }
                //不管上面的情况, 到这一步, p肯定在父节点的右边, 只需要左旋
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                RotateLeft(tree, p->parent->parent);
            }
        }
        else
        {
            _X = p->parent->parent->rightchild;
            if(_X->color == RED)
            {
                
            }
            else //要旋转
            {
                
            }
        }
        
    }
    tree->color = BLACK;
}