当前位置: 首页 > 网站开发 > 正文

红黑树原理详解(一)

1 星2 星3 星4 星5 星 (1 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

一、红黑树概述

红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。这一点在我们了解了红黑树的实现原理后,就会有更加深切的体会。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。学过数据结构的人应该都已经领教过AVL树的复杂,但AVL树的复杂比起红黑树来说简直是小巫见大巫,红黑树才是真正的变态级数据结构。

由于STL中的关联式容器默认的底层实现都是红黑树,因此红黑树对于后续学习STL源码还是很重要的,有必要掌握红黑树的实现原理和源码实现。

红黑树是AVL树的变种,红黑树通过一些着色法则确保没有一条路径会比其它路径长出两倍,因而达到接近平衡的目的。所谓红黑树,不仅是一个二叉搜索树,而且必须满足一下规则:

1、每个节点不是红色就是黑色。
2、根节点为黑色。
3、如果节点为红色,其子节点必须为黑色。
4、任意一个节点到到NULL(树尾端)的任何路径,所含之黑色节点数必须相同。

上面的这些约束保证了这个树大致上是平衡的,这也决定了红黑树的插入、删除、查询等操作是比较快速的。 根据规则4,新增节点必须为红色;根据规则3,新增节点之父节点必须为黑色。当新增节点根据二叉搜索树的规则到达其插入点时,却未能符合上述条件时,就必须调整颜色并旋转树形,如下图:
1342081846_5019
假设我们为上图分别插入节点3、8、35、75,根据二叉搜索树的规则,插入这四个节点后,我们会发现它们都破坏了红黑树的规则,因此我们必须调整树形,也就是旋转树形并改变节点的颜色。

二、红黑树上结点的插入
在讨论红黑树的插入操作之前必须要明白,任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解,因为插入黑点会增加某条路径上黑结点的数目,从而导致整棵树黑高度的不平衡。但如果新结点的父结点为红色时(如下图所示),将会违反红黑树的性质:一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。
1342082295_4867
为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点;使用“父”字表示新插入点的父结点;使用“叔”字表示“父”结点的兄弟结点;使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况:

1、黑父
如下图所示,如果新节点的父结点为黑色结点,那么插入一个红点将不会影响红黑树的平衡,此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见,从而使红黑树需要旋转的几率相对AVL树来说会少一些。
1342082985_8252
2、红父

如果新节点的父结点为红色,这时就需要进行一系列操作以保证整棵树红黑性质。如下图所示,由于父结点为红色,此时可以判定,祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作,而每次进行不平衡判断的起始点(我们可将其视为新点)都不一样。所以我们在此使用一个蓝色箭头指向这个起始点,并称之为判定点。
1342083075_5573
2.1 红叔

当叔父结点为红色时,如下图所示,无需进行旋转操作,只要将父和叔结点变为黑色,将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色,从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上(迭代)进行平衡操作。

需要注意的是,无论“父节点”在“叔节点”的左边还是右边,无论“新节点”是“父节点”的左孩子还是右孩子,它们的操作都是完全一样的(其实这种情况包括4种,只需调整颜色,不需要旋转树形)。

2.2 黑叔
当叔父结点为黑色时,需要进行旋转,以下图示了所有的旋转可能:
Case 1:
1342083532_9981
Case 2:
1342083571_7513
Case 3:
1342083759_7035
Case 4:
1342083770_6903

可以观察到,当旋转完成后,新的旋转根全部为黑色,此时不需要再向上回溯进行平衡操作,插入操作完成。需要注意,上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

其实红黑树的插入操作不是很难,甚至比AVL树的插入操作还更简单些。红黑树的插入操作源代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
// 元素插入操作  insert_unique()  
// 插入新值:节点键值不允许重复,若重复则插入无效  
// 注意,返回值是个pair,第一个元素是个红黑树迭代器,指向新增节点  
// 第二个元素表示插入成功与否  
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>  
pair<typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator , bool>  
rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_unique(const Value &v)  
{  
    rb_tree_node* y = header;    // 根节点root的父节点  
    rb_tree_node* x = root();    // 从根节点开始  
    bool comp = true;  
    while(x != 0)  
    {  
        y = x;  
        comp = key_compare(KeyOfValue()(v) , key(x));    // v键值小于目前节点之键值?  
        x = comp ? left(x) : right(x);   // 遇“大”则往左,遇“小于或等于”则往右  
    }  
    // 离开while循环之后,y所指即插入点之父节点(此时的它必为叶节点)  
    iterator j = iterator(y);     // 令迭代器j指向插入点之父节点y  
    if(comp)     // 如果离开while循环时comp为真(表示遇“大”,将插入于左侧)  
    {  
        if(j == begin())    // 如果插入点之父节点为最左节点  
            return pair<iterator , bool>(_insert(x , y , z) , true);  
        else     // 否则(插入点之父节点不为最左节点)  
            --j;   // 调整j,回头准备测试  
    }  
    if(key_compare(key(j.node) , KeyOfValue()(v) ))  
        // 新键值不与既有节点之键值重复,于是以下执行安插操作  
        return pair<iterator , bool>(_insert(x , y , z) , true);  
    // 以上,x为新值插入点,y为插入点之父节点,v为新值  
 
    // 进行至此,表示新值一定与树中键值重复,那么就不应该插入新值  
    return pair<iterator , bool>(j , false);  
}  
 
// 真正地插入执行程序 _insert()  
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>  
typename<Key , Value , KeyOfValue , Compare , Alloc>::_insert(base_ptr x_ , base_ptr y_ , const Value &v)  
{  
    // 参数x_ 为新值插入点,参数y_为插入点之父节点,参数v为新值  
    link_type x = (link_type) x_;  
    link_type y = (link_type) y_;  
    link_type z;  
 
    // key_compare 是键值大小比较准则。应该会是个function object  
    if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) ))  
    {  
        z = create_node(v);    // 产生一个新节点  
        left(y) = z;           // 这使得当y即为header时,leftmost() = z  
        if(y == header)  
        {  
            root() = z;  
            rightmost() = z;  
        }  
        else if(y == leftmost())     // 如果y为最左节点  
            leftmost() = z;          // 维护leftmost(),使它永远指向最左节点  
    }  
    else  
    {  
        z = create_node(v);        // 产生一个新节点  
        right(y) = z;              // 令新节点成为插入点之父节点y的右子节点  
        if(y == rightmost())  
            rightmost() = z;       // 维护rightmost(),使它永远指向最右节点  
    }  
    parent(z) = y;      // 设定新节点的父节点  
    left(z) = 0;        // 设定新节点的左子节点  
    right(z) = 0;       // 设定新节点的右子节点  
    // 新节点的颜色将在_rb_tree_rebalance()设定(并调整)  
    _rb_tree_rebalance(z , header->parent);      // 参数一为新增节点,参数二为根节点root  
    ++node_count;       // 节点数累加  
    return iterator(z);  // 返回一个迭代器,指向新增节点  
}  
 
 
// 全局函数  
// 重新令树形平衡(改变颜色及旋转树形)  
// 参数一为新增节点,参数二为根节点root  
inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root)  
{  
    x->color = _rb_tree_red;    //新节点必为红  
    while(x != root && x->parent->color == _rb_tree_red)    // 父节点为红  
    {  
        if(x->parent == x->parent->parent->left)      // 父节点为祖父节点之左子节点  
        {  
            _rb_tree_node_base* y = x->parent->parent->right;    // 令y为伯父节点  
            if(y && y->color == _rb_tree_red)    // 伯父节点存在,且为红  
            {  
                x->parent->color = _rb_tree_black;           // 更改父节点为黑色  
                y->color = _rb_tree_black;                   // 更改伯父节点为黑色  
                x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色  
                x = x->parent->parent;  
            }  
            else    // 无伯父节点,或伯父节点为黑色  
            {  
                if(x == x->parent->right)   // 如果新节点为父节点之右子节点  
                {  
                    x = x->parent;  
                    _rb_tree_rotate_left(x , root);    // 第一个参数为左旋点  
                }  
                x->parent->color = _rb_tree_black;     // 改变颜色  
                x->parent->parent->color = _rb_tree_red;  
                _rb_tree_rotate_right(x->parent->parent , root);    // 第一个参数为右旋点  
            }  
        }  
        else          // 父节点为祖父节点之右子节点  
        {  
            _rb_tree_node_base* y = x->parent->parent->left;    // 令y为伯父节点  
            if(y && y->color == _rb_tree_red)    // 有伯父节点,且为红  
            {  
                x->parent->color = _rb_tree_black;           // 更改父节点为黑色  
                y->color = _rb_tree_black;                   // 更改伯父节点为黑色  
                x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色  
                x = x->parent->parent;          // 准备继续往上层检查  
            }  
            else    // 无伯父节点,或伯父节点为黑色  
            {  
                if(x == x->parent->left)        // 如果新节点为父节点之左子节点  
                {  
                    x = x->parent;  
                    _rb_tree_rotate_right(x , root);    // 第一个参数为右旋点  
                }  
                x->parent->color = _rb_tree_black;     // 改变颜色  
                x->parent->parent->color = _rb_tree_red;  
                _rb_tree_rotate_left(x->parent->parent , root);    // 第一个参数为左旋点  
            }  
        }  
    }//while  
    root->color = _rb_tree_black;    // 根节点永远为黑色  
}  
 
 
// 左旋函数  
inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root)  
{  
    // x 为旋转点  
    _rb_tree_node_base* y = x->right;          // 令y为旋转点的右子节点  
    x->right = y->left;  
    if(y->left != 0)  
        y->left->parent = x;           // 别忘了回马枪设定父节点  
    y->parent = x->parent;  
 
    // 令y完全顶替x的地位(必须将x对其父节点的关系完全接收过来)  
    if(x == root)    // x为根节点  
        root = y;  
    else if(x == x->parent->left)         // x为其父节点的左子节点  
        x->parent->left = y;  
    else                                  // x为其父节点的右子节点  
        x->parent->right = y;  
    y->left = x;  
    x->parent = y;  
}  
 
 
// 右旋函数  
inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root)  
{  
    // x 为旋转点  
    _rb_tree_node_base* y = x->left;          // 令y为旋转点的左子节点  
    x->left = y->right;  
    if(y->right != 0)  
        y->right->parent = x;           // 别忘了回马枪设定父节点  
    y->parent = x->parent;  
 
    // 令y完全顶替x的地位(必须将x对其父节点的关系完全接收过来)  
    if(x == root)  
        root = y;  
    else if(x == x->parent->right)         // x为其父节点的右子节点  
        x->parent->right = y;  
    else                                  // x为其父节点的左子节点  
        x->parent->left = y;  
    y->right = x;  
    x->parent = y;  
}

本文固定链接: http://www.chepoo.com/red-black-tree-detailed-principles-one.html | IT技术精华网

红黑树原理详解(一):等您坐沙发呢!

发表评论