红黑树原理浅谈(附Linux内核源码注释)

骑猪看日落 2022-10-06 00:42 112阅读 0赞

引言：红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(log n) 时间内做查找，插入和删除，这里的n是树中元素的数目。——摘自维基百科

红黑树的性质：  
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树有如下的额外要求：

1.节点是红色或黑色。  
2.根是黑色。  
3.所有叶子都是黑色（叶子是NIL节点）。  
4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）  
5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70]  
这个网站可以看各种数据结构的动态演变  
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

操作：  
因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再匹配红黑树的性质。恢复红黑树的性质需要少量 O(log n)的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n)次。

红黑树的应用  
它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。比如  
①JDK1.8中的TreeMap 或  
②C++的STL中的set和map函数或  
③Linux内核中的rbtree.h和rbtree.c  
都有红黑树的应用，这些集合均提供了很好的性能。

什么时候用AVL树？什么时候用红黑树？  
首先AVL树和红黑树都是基于BST树(二叉搜索树)，对于只读操作均和BST树相同，但BST树连续插入顺序递增或递减结点时会导致BST树退化成链表，性能大幅度降低。BST顺序插入如图：  
![在这里插入图片描述][20210617110726982.png]

因此，AVL树和红黑树均在BST树的基础上进行了进一步的优化。以增加旋转操作(增加算法复杂度)来提升对于最坏情况下的性能。提升复杂度往往从两方面入手：  
①提升数据结构的复杂度  
②提升算法的复杂度  
其中，红黑树为了降低原有算法复杂度，就以提升数据结构复杂度来间接减轻其算法复杂度。即在其结点中增加颜色属性，颜色只能有红色和黑色。在红黑树中只要任意结点左右孩子的黑色高度平衡(两边任意路径黑色结点数量相同)即可且对于有些情况可以通过变色来代替旋转从而减少一定的空间开销。

①AVL树采用平衡因子的绝对值<2来保证平衡，这种平衡是高度平衡的。要保证这种平衡需要更复杂的操作来维持。  
②红黑树采用同一结点到叶结点的任意路径黑色结点数量相同来保证平衡，这种平衡只能保证从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。保证这种平衡只需要较少的操作来维持。

下图是从根到叶子的最长的可能路径=最短的可能路径的两倍长的情况：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 1]

综上所述：删除结点最坏情况下，AVL树需要旋转的量级是O(log n)，而红黑树最多只需3次旋转，只需要O(1)的复杂度。

下图是知乎大神提供的性能测试：  
![在这里插入图片描述][2021061711125911.png]  
由此可见：  
①红黑树由于插入删除时较少的旋转操作，对于需要频繁进行插入删除的场景性能比AVL树好  
②反之，对于不需要频繁插入删除的场景。由于AVL树的高度平衡，使得同等结点数量下，AVL树的高度比红黑树更低，使得AVL树的查找性能比红黑树好。

JDK1.8里的TreeMapEntry对红黑树数据结构的定义  
/\*\*  
\* Node in the Tree. Doubles as a means to pass key-value pairs back to  
\* user (see Map.Entry).  
\*/

static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        TreeMapEntry<K,V> left = null;//左子树
        TreeMapEntry<K,V> right = null;//右子树
        TreeMapEntry<K,V> parent;//父节点
        boolean color = BLACK;//默认为黑色
    
        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    
        /**
         * Returns the key.
         *
         * @return the key
         */
        public K getKey() {
            return key;
        }
    
        /**
         * Returns the value associated with the key.
         *
         * @return the value associated with the key
         */
        public V getValue() {
            return value;
        }
        /*...各种方法*/

Linux内核文件rbtree.h中对红黑树的数据结构的定义  
struct rb\_node  
\{/*long是四个字节，占用共4x8=32bit，其中有两位存储父结点指针+自己的颜色值*/  
unsigned long rb\_parent\_color; /*注意：此处保存的是父指针+自己颜色*/  
\#define RB\_RED 0  
\#define RB\_BLACK 1  
struct rb\_node *rb\_right;  
struct rb\_node rb\_left;  
\} / **attribute**((aligned(sizeof(long))))*/;  
/\* The alignment might seem pointless, but allegedly CRIS needs it \*/

struct rb\_root  
\{  
struct rb\_node \*rb\_node;  
\};

以及rbtree.h中在插入新结点时，初始化红黑树结点操作

static inline void rb\_init\_node(struct rb\_node \*rb)  
\{  
rb->rb\_parent\_color = 0;  
rb->rb\_right = NULL;  
rb->rb\_left = NULL;  
RB\_CLEAR\_NODE(rb);  
\}

在此需要先了解左旋和右旋的原理  
结点E左旋操作：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 2]  
(动图来源于网络)  
代码如下：  
/\*

*  左旋操作Linux c代码(来源于Linux内核rbtree.c)  
    \*/  
    static void \_\_rb\_rotate\_left(struct rb\_node \*node, struct rb\_root \*root)  
    \{  
    struct rb\_node \*right = node->rb\_right;  
    struct rb\_node \*parent = rb\_parent(node);
    
    if ((node->rb\_right = right->rb\_left)) //node的右指针指向node右孩子的左孩子  
    rb\_set\_parent(right->rb\_left, node);//node右孩子的左孩子的父亲指定为node  
    right->rb\_left = node;
    
    rb\_set\_parent(right, parent); //node右孩子祖父指定为node原父亲
    
    if (parent) //node原父亲存在，即原node不是根结点  
    \{  
    if (node == parent->rb\_left)  
    parent->rb\_left = right;  
    else  
    parent->rb\_right = right;  
    \}  
    else //原node是根结点  
    root->rb\_node = right;  
    rb\_set\_parent(node, right); //node现任父亲指定为node原右孩子  
    \}

结点S右旋操作：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 3]

(动图来源于网络，代码与左旋对调)

红黑树插入操作逻辑  
https://naotu.baidu.com/file/c0fa8088fa5643598484bae7e81fbb49?token=cc0609045c2ebee9  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 4]

红黑树删除操作逻辑  
https://naotu.baidu.com/file/70158a0693b8421b3bd0fe56cde6e361?token=6e76ac0c14851a5b  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 5]  
Linux内核源码注释解析  
rbtree.c  
/\*  
Red Black Trees  
© 1999 Andrea Arcangeli [andrea@suse.de][andrea_suse.de]  
© 2002 David Woodhouse [dwmw2@infradead.org][dwmw2_infradead.org]

This program is free software; you can redistribute it and/or modify  
it under the terms of the GNU General Public License as published by  
the Free Software Foundation; either version 2 of the License, or  
(at your option) any later version.

This program is distributed in the hope that it will be useful,  
but WITHOUT ANY WARRANTY; without even the implied warranty of  
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
GNU General Public License for more details.

You should have received a copy of the GNU General Public License  
along with this program; if not, write to the Free Software  
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

linux/lib/rbtree.c  
\*/

\#include “rbtree.h”  
/\*

*  左旋操作  
    \*/  
    static void \_\_rb\_rotate\_left(struct rb\_node \*node, struct rb\_root \*root)  
    \{  
    struct rb\_node \*right = node->rb\_right;  
    struct rb\_node \*parent = rb\_parent(node);
    
    if ((node->rb\_right = right->rb\_left)) //node的右指针指向node右孩子的左孩子  
    rb\_set\_parent(right->rb\_left, node);//node右孩子的左孩子的父亲指定为node  
    right->rb\_left = node;
    
    rb\_set\_parent(right, parent); //node右孩子祖父指定为node原父亲
    
    if (parent) //node原父亲存在，即原node不是根结点  
    \{  
    if (node == parent->rb\_left)  
    parent->rb\_left = right;  
    else  
    parent->rb\_right = right;  
    \}  
    else //原node是根结点  
    root->rb\_node = right;  
    rb\_set\_parent(node, right); //node现任父亲指定为node原右孩子  
    \}  
    /\*
 *  右旋操作  
    \*/  
    static void \_\_rb\_rotate\_right(struct rb\_node \*node, struct rb\_root \*root)  
    \{  
    struct rb\_node \*left = node->rb\_left;  
    struct rb\_node \*parent = rb\_parent(node);
    
    if ((node->rb\_left = left->rb\_right))  
    rb\_set\_parent(left->rb\_right, node);  
    left->rb\_right = node;
    
    rb\_set\_parent(left, parent);
    
    if (parent)  
    \{  
    if (node == parent->rb\_right)  
    parent->rb\_right = left;  
    else  
    parent->rb\_left = left;  
    \}  
    else  
    root->rb\_node = left;  
    rb\_set\_parent(node, left);  
    \}  
    /\*
 *  插入结点操作  
    \*/  
    void rb\_insert\_color(struct rb\_node \*node, struct rb\_root \*root)  
    \{  
    struct rb\_node \*parent, \*gparent;  
    //情况1,2：node不是根结点，即有父结点P且P是红色的  
    while ((parent = rb\_parent(node)) && rb\_is\_red(parent))  
    \{  
    gparent = rb\_parent(parent);  
    //P是祖父G的左孩子  
    if (parent == gparent->rb\_left)  
    \{  
    \{  
    register struct rb\_node \*uncle = gparent->rb\_right;  
    if (uncle && rb\_is\_red(uncle)) //情况3：node的叔父结点是红色的  
    \{  
    rb\_set\_black(uncle);  
    rb\_set\_black(parent);  
    rb\_set\_red(gparent);  
    node = gparent;  
    continue;  
    \}  
    \}  
    //情况4：node和父结点P是LR型(变成LL型)  
    if (parent->rb\_right == node)  
    \{  
    register struct rb\_node \*tmp;  
    \_\_rb\_rotate\_left(parent, root);  
    tmp = parent;  
    parent = node;  
    node = tmp;  
    \}  
    //情况5：node和父结点P是LL型  
    rb\_set\_black(parent);  
    rb\_set\_red(gparent);  
    \_\_rb\_rotate\_right(gparent, root);  
    \} else \{ //P是祖父G的右孩子，与上述情况对调  
    \{  
    register struct rb\_node \*uncle = gparent->rb\_left;  
    if (uncle && rb\_is\_red(uncle))  
    \{  
    rb\_set\_black(uncle);  
    rb\_set\_black(parent);  
    rb\_set\_red(gparent);  
    node = gparent;  
    continue;  
    \}  
    \}
    
        if (parent->rb_left == node)
             {
                 register struct rb_node *tmp;
                 __rb_rotate_right(parent, root);
                 tmp = parent;
                 parent = node;
                 node = tmp;
             }
        
             rb_set_black(parent);
             rb_set_red(gparent);
             __rb_rotate_left(gparent, root);
         }
    
    \}  
    //若node是根结点||node的父结点P是黑色的，则把根结点->黑色  
    rb\_set\_black(root->rb\_node);  
    \}  
    /\*
 *  删除结点操作(Node和Child均是黑色的情况)  
    \*/  
    static void \_\_rb\_erase\_color(struct rb\_node \*node, struct rb\_node \*parent,  
    struct rb\_root \*root)  
    \{  
    struct rb\_node *other;  
    //以下循环体条件node不是根结点&&(node非空||node是黑色的)  
    while ((!node || rb\_is\_black(node)) && node != root->rb\_node)  
    \{  
    if (parent->rb\_left == node) //若node是父结点的左孩子  
    \{  
    other = parent->rb\_right;  
    if (rb\_is\_red(other)) //N的兄弟结点S是红色的  
    \{ //S由红色->黑色;P由黑色->红色;P左旋  
    rb\_set\_black(other);  
    rb\_set\_red(parent);  
    \_\_rb\_rotate\_left(parent, root);  
    other = parent->rb\_right;  
    \} //SL黑色&&SR黑色  
    if ((!other->rb\_left || rb\_is\_black(other->rb\_left)) &&  
    (!other->rb\_right || rb\_is\_black(other->rb\_right)))  
    \{  
    rb\_set\_red(other);  
    node = parent; //将P作为node带入以下检查程序  
    parent = rb\_parent(node);  
    \}  
    else  
    \{ //SL是红色(推断)，SR是黑色  
    if (!other->rb\_right || rb\_is\_black(other->rb\_right))  
    \{ //SL由红色->黑色;S由黑色->红色;右旋S;P的新右孩子是SL  
    rb\_set\_black(other->rb\_left);  
    rb\_set\_red(other);  
    \_\_rb\_rotate\_right(other, root);  
    other = parent->rb\_right;  
    \} //S由黑色->P的颜色;P->黑色;SR由红色->黑色;左旋P  
    rb\_set\_color(other, rb\_color(parent));  
    rb\_set\_black(parent);  
    rb\_set\_black(other->rb\_right);  
    \_\_rb\_rotate\_left(parent, root);  
    node = root->rb\_node;  
    break;  
    \}  
    \}  
    else //若node是父结点的右孩子，和上述情况对调  
    \{  
    other = parent->rb\_left;  
    if (rb\_is\_red(other))  
    \{  
    rb\_set\_black(other);  
    rb\_set\_red(parent);  
    \_\_rb\_rotate\_right(parent, root);  
    other = parent->rb\_left;  
    \}  
    if ((!other->rb\_left || rb\_is\_black(other->rb\_left)) &&  
    (!other->rb\_right || rb\_is\_black(other->rb\_right)))  
    \{  
    rb\_set\_red(other);  
    node = parent;  
    parent = rb\_parent(node);  
    \}  
    else  
    \{  
    if (!other->rb\_left || rb\_is\_black(other->rb\_left))  
    \{  
    rb\_set\_black(other->rb\_right);  
    rb\_set\_red(other);  
    \_\_rb\_rotate\_left(other, root);  
    other = parent->rb\_left;  
    \}  
    rb\_set\_color(other, rb\_color(parent));  
    rb\_set\_black(parent);  
    rb\_set\_black(other->rb\_left);  
    \_\_rb\_rotate\_right(parent, root);  
    node = root->rb\_node;  
    break;  
    \}  
    \}  
    \}  
    if (node)  
    rb\_set\_black(node);  
    \}  
    /*
 *  删除红黑树结点，处理除Node和Child均是黑色以外的情况，最后单独将这种情况用\_\_rb\_erase\_color函数处理  
    \*/  
    void rb\_erase(struct rb\_node \*node, struct rb\_root \*root)  
    \{  
    struct rb\_node \*child, \*parent;  
    int color;
    
    if (!node->rb\_left) //1.删除节点node左孩子为空  
    child = node->rb\_right; //child为node右孩子  
    else if (!node->rb\_right)//2.删除节点node右孩子为空  
    child = node->rb\_left; //child为node左孩子  
    else //3.删除节点node子结点均非空，则需要找到其右子树的最小的结点然后跟换两个结点的值  
    \{  
    struct rb\_node \*old = node, \*left;
    
        node = node->rb_right; //令node为原node的右孩子
         while ((left = node->rb_left) != NULL) //不断循环找到其最左的孩子(最小值结点)
             node = left;
        
         if (rb_parent(old)) {  //若原node(old)有父结点
             if (rb_parent(old)->rb_left == old) //若old是父结点的左孩子，则现在左孩子是新node
                 rb_parent(old)->rb_left = node;
             else
                 rb_parent(old)->rb_right = node;//若old是父结点的右孩子，则现在右孩子是新node
         } else
             root->rb_node = node; //若原node(old)是根结点，则现在的根是新node
        
         child = node->rb_right; //新node的右孩子的是child
         parent = rb_parent(node);//新node的父亲的是parent
         color = rb_color(node);//新node的颜色是color
         //以下将old替换为新node结点，同时将新node的非空子结点child成为P的左孩子
         if (parent == old) {
             parent = node;
         } else {
             if (child)
                 rb_set_parent(child, parent);
             parent->rb_left = child;  //P的左孩子由node变为child
        
             node->rb_right = old->rb_right;
             rb_set_parent(old->rb_right, node);
         }
        
         node->rb_parent_color = old->rb_parent_color;  //Linux内核中红黑树数据结构存储的是其父结点的颜色
         node->rb_left = old->rb_left;
         rb_set_parent(old->rb_left, node);
        
         goto color;  //goto到"color:"一行
    
    \}  
    //以下步骤是对换情况1和2的node和child两结点，使child为node的新父亲  
    parent = rb\_parent(node);  
    color = rb\_color(node);
    
    if (child)  
    rb\_set\_parent(child, parent);  
    if (parent)  
    \{  
    if (parent->rb\_left == node)  
    parent->rb\_left = child;  
    else  
    parent->rb\_right = child;  
    \}  
    else  
    root->rb\_node = child;  
    //以上步骤是对换情况1和2的node和child两结点，使child为node的新父亲  
    color:  
    if (color == RB\_BLACK) //若和child颠倒位置后的node结点是黑色  
    \_\_rb\_erase\_color(child, parent, root); //将child带入检查程序  
    \}  
    /\*
 *  替换结点函数(将结点victim替换为结点new)  
    \*/  
    void rb\_replace\_node(struct rb\_node \*victim, struct rb\_node \*new,  
    struct rb\_root \*root)  
    \{  
    struct rb\_node \*parent = rb\_parent(victim);
    
    /\* Set the surrounding nodes to point to the replacement \*/  
    if (parent) \{  
    if (victim == parent->rb\_left)  
    parent->rb\_left = new;  
    else  
    parent->rb\_right = new;  
    \} else \{  
    root->rb\_node = new;  
    \}  
    if (victim->rb\_left)  
    rb\_set\_parent(victim->rb\_left, new);  
    if (victim->rb\_right)  
    rb\_set\_parent(victim->rb\_right, new);
    
    /\* Copy the pointers/colour from the victim to the replacement \*/  
    *new = victim;  
    \}  
    /…后续扩展函数等*/  
    ————————————————  
    版权声明：本文为CSDN博主「SL\_World」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
    原文链接：https://blog.csdn.net/SL\_World/article/details/84584503

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70]: /images/20221005/8cbcd288a9bc424084730252964118d6.png
[20210617110726982.png]: /images/20221005/88b74a0cb6684d8cb5907871c3f498a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 1]: /images/20221005/b4caff4543f847579a8fd3e0b620021d.png
[2021061711125911.png]: /images/20221005/ef42cac804634441acf77eb7ca79a489.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 2]: /images/20221005/c1a6efecd1944d5d82507beb708aecd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 3]: /images/20221005/475c3239455e402a90c249b601c6505c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 4]: /images/20221005/6c837fd31a484fe5b845a8bf6eade444.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FybWxpbnV4d3c_size_16_color_FFFFFF_t_70 5]: /images/20221005/b45dbf3b06bf4243ab5dac26102bef81.png
[andrea_suse.de]: mailto:andrea@suse.de
[dwmw2_infradead.org]: mailto:dwmw2@infradead.org