红黑树

首页 > 代码库 > 红黑树

2024-07-04 19:39:58 227人阅读

性质导致了 强约束,也导致了O（lgn）的高度

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点（不包括该节点）到其每个叶子的所有简单路径都包含相同数目的黑色节点。

得出的结论

1 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

2 最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点

3 红色结点的父结点或子节点一定是黑色结点

4 在五个性质前提下推导出树的高度为o（lgn）的结论，

即进行插入或删除时，只需关注保持五个性质，而五个性质决定了算法的复杂度为o（lgn）

插入需要注意的点

1 插入新节点总是红色节点

2 如果插入节点的父节点是黑色, 能维持性质

3 如果插入节点的父节点是红色, 破坏了性质. 故需要通过重新着色或旋转, 来维持性质

插入关键部分

解决相邻的两个节点为红色的结点，同时维持任意路径黑高度（黑色结点个数）相同

删除需要需要注意的点

1 如果删除的是红色节点, 不破坏性质

2 如果删除的是黑色节点, 那么这个路径上就会少一个黑色节点, 破坏了性质. 故需要通过重新着色或旋转, 来维持性质

删除关键部分

如果删除的是左子树黑色结点，维持的最终目的是左右黑高度相同，即维持右子树黑高度的同时，增加左子树的黑高度

代码主要根据上图实现

  1 #include <iostream>
  2 #include <crtdbg.h>
  3 #include <string>
  4 using namespace std;
  5 /*红黑树*/
  6 /*实现中假设关键元素互不相同*/
  7 typedef int DataType;
  8 
  9 class BST
 10 {
 11 private:
 12     enum {BLACK = 0, RED = 1};
 13     /*结点的数据结构*/
 14     struct node
 15     {
 16         DataType data;
 17         bool color;
 18         node *left;
 19         node *right;
 20         node *parent;
 21 
 22         node()
 23         {
 24             color = RED;
 25             left = NULL;
 26             right = NULL;
 27             parent = NULL;
 28             data = http://www.mamicode.com/0;
 29         }
 30         node *Grandfather()
 31         {
 32             if (parent == NULL)
 33             {
 34                 return NULL;
 35             }
 36             return parent->parent;
 37         }
 38         node *Uncle()
 39         {
 40             if(Grandfather() == NULL)
 41                 return NULL;
 42             if (parent == Grandfather()->left)
 43             {
 44                 return Grandfather()->right;
 45             }
 46             else
 47             {
 48                 return Grandfather()->left;
 49             }
 50         }
 51         node *Sibling()
 52         {
 53             if (parent->left == this)
 54             {
 55                 return parent->right;
 56             }
 57             else
 58             {
 59                 return parent->left;
 60             }
 61         }
 62     };
 63     void Left_rotate(node *p )
 64     {
 65         //把y的左子树连接到p的右子树下面，并更新父节点
 66         node *y = p->right;
 67         p->right = y->left;
 68         if (y->left != NIL)
 69         {
 70             y->left->parent = p;
 71         }
 72         //更新y的父节点
 73         y->parent = p->parent;
 74         if (p->parent == NIL) //判断根结点
 75         {
 76             root = y;
 77         }
 78         //更新原x父节点的子节点
 79         else if (p == p->parent->left)
 80         {
 81             p->parent->left = y;
 82         }
 83         else
 84         {
 85             p->parent->right = y;
 86         }
 87         //更新x 与 y 的关系
 88         y->left = p;
 89         p->parent = y;
 90     }
 91     void Right_rotate(node *p)
 92     {
 93         node *y = p->left;
 94         p->left = y->right;
 95         if (y->right != NIL)
 96         {
 97             y->right->parent = p;
 98         }
 99         y->parent = p->parent;
100         if (p->parent == NIL) //判断根结点
101         {
102             root = y;
103         }
104         else if (p == p->parent->left)
105         {
106             p->parent->left = y;
107         }
108         else
109         {
110            p->parent->right = y;
111         }
112         y->right = p;
113         p->parent = y;
114     }
115     string OutputColor(bool color)
116     {
117         return color ? "RED":"BLACK";
118     }
119     /*纠正因插入而破坏的性质*/
120     void Insert_Fixup(node *p)
121     {
122         /*由于p结点为红色（新插入默认赋值为红色），
123           判断p的父节点是否为红色，如果为红色则破坏了红黑树的性质，需要维护*/
124         while(p->parent->color == RED)
125         {
126             if (p->parent == p->Grandfather()->left) 
127             {
128                 node *y = p->Grandfather()->right;
129                 if (y->color == RED)  /*case 3*/
130                 {
131                     p->parent->color = BLACK;
132                     y->color = BLACK;
133                     p->Grandfather()->color = RED;
134                     p = p->Grandfather();/*p结点向上移*/
135                 }
136                 else if (p == p->parent->right) /*case 2*/
137                 {
138                     p = p->parent;/*p结点向上移*/
139                     Left_rotate(p);
140                 }
141                 else
142                 {
143                     p->parent->color = BLACK; /*case 3*/
144                     p->Grandfather()->color = RED;
145                     Right_rotate(p->Grandfather());/*注意是祖父结点*/
146                 }
147             }
148             else
149             {
150                 node *y = p->Grandfather()->left;
151                 if (y->color == RED)  /*case 3*/
152                 {
153                     p->parent->color = BLACK;
154                     y->color = BLACK;
155                     p->Grandfather()->color = RED;
156                     p = p->Grandfather();
157                 }
158                 else if (p == p->parent->left) /*case 2*/
159                 {
160                     p = p->parent;
161                     Right_rotate(p);
162                 }
163                 else
164                 {
165                     p->parent->color = BLACK; /*case 3*/
166                     p->Grandfather()->color = RED;
167                     Left_rotate(p->Grandfather());
168                 }
169             }
170         }
171         root->color = BLACK;/*确保插入根结点时，满足红黑树的性质*/
172     }
173     /*纠正因删除而破坏的性质*/
174     void Delete_Fixup(node *p)
175     {
176         /*判断p结点是否为黑色
177          如果是红色不破坏红黑树性质
178          原因1.删除红色树黑高度不变2.不存在两个相邻红色结点
179          3. 如果y是红色的，就不可能是根，即根仍然是黑色的
180          为保证性质任何路径上黑结点个数相同，假设p结点为多重颜色（双黑或红黑）*/
181         while (p != root && p->color == BLACK)
182         {
183             if(p == p->parent->left)
184             {
185                 node *pSibling = p->parent->right;
186                 if (pSibling->color == RED)/*case1*/
187                 {
188                     pSibling->color = BLACK;
189                     Left_rotate(p->parent);
190                     pSibling = p->parent->right;
191                 }
192                 else if (pSibling->left->color == BLACK && pSibling->right->color == BLACK)/*case2*/
193                 {
194                     pSibling->color = RED;
195                     p = p->parent;
196                 }                
197                 else
198                 {
199                     if (pSibling->right->color == BLACK)/*case3*/
200                     {
201                         pSibling->left->color = BLACK;
202                         pSibling->color = RED;
203                         Right_rotate(pSibling);
204                         pSibling = p->parent->right;
205                     }
206                     pSibling->color = p->parent->color;/*case4*/
207                     p->parent->color = BLACK;
208                     pSibling->right->color = BLACK;
209                     Left_rotate(p->parent);
210                     p = root;
211                 }
212             }
213             else
214             {
215                 node *pSibling = p->parent->left;
216                 if (pSibling->color == RED)/*case1*/
217                 {
218                     pSibling->color = BLACK;
219                     Left_rotate(p->parent);
220                     pSibling = p->parent->left;
221                 }
222                 else if (pSibling->left->color == BLACK && pSibling->right->color == BLACK)/*case2*/
223                 {
224                     pSibling->color = RED;
225                     p = p->parent;
226                 }                
227                 else
228                 {
229                     if (pSibling->left->color == BLACK)/*case3*/
230                     {
231                         pSibling->right->color = BLACK;
232                         pSibling->color = RED;
233                         Left_rotate(pSibling);
234                         pSibling = p->parent->left;
235                     }
236                     pSibling->color = p->parent->color;/*case4*/
237                     p->parent->color = BLACK;
238                     pSibling->right->color = BLACK;
239                     Right_rotate(p->parent);
240                     p = root;
241                 }
242             }
243         }
244         p->color = BLACK;
245     }
246     /*中序遍历*/
247     void InOrderTree(node *p)
248     {
249         if (p == NULL || p == NIL)
250         {
251             return;
252         }
253         InOrderTree(p->left);
254         cout << p->data << "\t" << OutputColor(p->color) << endl;
255         InOrderTree(p->right);
256     }
257     /*获取结点的后继*/
258     node *TreeAfter(node *p)
259     {
260         if (p->right != NIL)
261         {
262             node *pTemp = p->right;
263             while(pTemp != NIL)
264             {
265                 p = pTemp;
266                 pTemp = p->left;
267             }
268         }
269         return p;
270     }
271 private:
272     node *root;
273     node *NIL;
274 public:
275     BST()
276     {
277         NIL = new node();
278         NIL->color = BLACK;
279         root = NULL;
280     }
281     ~BST()
282     {
283         if (root != NULL)
284         {
285             Destory(root);
286             root = NULL;
287         }
288         delete NIL;
289         NIL = NULL;
290     }
291     void Destory(node *p)
292     {
293         if (p == NULL || p == NIL)
294             return;
295         Destory(p->left);
296         Destory(p->right);
297         delete p;
298     }
299     void Insert(DataType data)
300     {
301         node *p = root;
302         node *pTemp = NIL;
303         while( p != NIL && p != NULL)
304         {
305             pTemp = p;
306             if (data < p->data)
307             {
308                 p = p->left;
309             }
310             else
311             {
312                 p = p->right;
313             }
314         }
315         node *pNew = new node();
316         pNew->parent = pTemp;
317         pNew->data =http://www.mamicode.com/ data;
318         if (pTemp == NIL)
319         {
320             root = pNew;
321         }
322         else
323         {
324             if (pNew->data < pTemp->data)
325             {
326                 pTemp->left = pNew;
327             }
328             else
329             {
330                 pTemp->right = pNew;
331             }
332         }
333         pNew->left = NIL;
334         pNew->right = NIL;
335         Insert_Fixup(pNew);
336     }
337     /*非递归版本*/
338     node* Find(DataType key)
339     {
340         node *p = root;
341         while(p != NULL && p->data != key)
342         {
343             if (key < p->data)
344             {
345                 p = p->left;
346             }
347             else
348             {
349                 p = p->right;
350             }
351         }
352         return p;
353     }
354     void Delete(DataType data)
355     {
356         /*获取data的指针*/
357         node *p = Find(data);
358         node *pDelete= NIL;
359         node *pNode = NIL;/*要删除节点的子节点*/
360         if (p->left == NIL || p->right == NIL)
361         {
362             pDelete = p;
363         }
364         else
365         {
366             pDelete = TreeAfter(p);
367         }
368         /*获取子结点*/
369         if(pDelete->left != NIL)
370         {
371             pNode = pDelete->left;
372         }
373         else
374         {
375             pNode = pDelete->right;
376         }
377         /*更新父结点*/
378         pNode->parent = pDelete->parent;
379         /*更新子结点*/
380         if (pDelete->parent == NIL)
381         {
382             root = pNode;
383         }
384         else if(pDelete->parent->left == pDelete)
385         {
386             pDelete->parent->left = pNode;
387         }
388         else
389         {
390             pDelete->parent->right = pNode;
391         }
392         if (pDelete != p)
393         {
394             p->data = http://www.mamicode.com/pDelete->data;
395         }
396         /*如果要删除的结点pDelete是红色的，
397         不影响黑高度，即不会破坏红黑树的性质*/
398         if (pDelete->color == BLACK)
399         {
400             Delete_Fixup(pNode);
401         }

402         delete pDelete;
403         pDelete = NULL;
404     }
405     void InOrder()
406     {
407         if (root == NULL)
408         {
409             return;
410         }
411         InOrderTree(root);
412         cout << endl;
413     }
414 };
415 
416 void main()
417 {
418     _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
419 
420      BST bst;
421      
422      bst.Insert(11);
423      bst.Insert(2);
424      bst.Insert(14);
425      bst.Insert(15);
426      bst.Insert(1);
427      bst.Insert(7);
428      bst.Insert(5);
429      bst.Insert(8);
430      bst.Insert(4);
431 
432      bst.InOrder();
433 
434      //bst.Delete(4);
435      //bst.Delete(14);
436      bst.Delete(7);
437      bst.InOrder();
438 
439     system("pause");
440 }

（转载请注明作者和出处 :) Seven++ http://www.cnblogs.com/sevenPP/ ）

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 红黑树

红黑树

看完仍有疑问？有类似问题直接问程序猿