小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

隨想錄（用好紅黑樹(shù)）

 WUCANADA 2012-09-20

隨想錄（用好紅黑樹(shù)）

分類(lèi)： 隨想錄 2012-05-13 16:41 3245人閱讀 評(píng)論(1) 收藏 舉報(bào)

【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing @163.com】


    紅黑樹(shù)作為一種特殊類(lèi)型的二叉樹(shù)，在軟件中有很多的用處。但是在網(wǎng)絡(luò)上面，講解紅黑樹(shù)的文章和博客很多，可是真正找一份可以信賴的、方便使用的紅黑樹(shù)代碼卻不多。本篇文章的目的就是介紹如何正確使用紅黑樹(shù)的代碼。


    本篇文章的紅黑樹(shù)代碼主要來(lái)自linux kernel 2.6.7，其中實(shí)現(xiàn)文件保存在ib/rbtree.c，而頭文件保存在include/linux/rbtree.h。當(dāng)前的linux代碼已經(jīng)升級(jí)到 3.0以上了，但是關(guān)于紅黑樹(shù)的代碼內(nèi)容卻沒(méi)有什么大的改變，這說(shuō)明關(guān)于紅黑樹(shù)的代碼是非常穩(wěn)定的。


（1）紅黑樹(shù)的來(lái)源

    a）雙向鏈表是二叉樹(shù)的最初來(lái)源，雖然二叉樹(shù)也可以做到基本有序，但是查找起來(lái)十分麻煩

    b）在雙向鏈表的基礎(chǔ)上，人們發(fā)明了二叉樹(shù)，二叉樹(shù)保證了數(shù)據(jù)可以像數(shù)組一樣快速完成二分查找，極大地提高了查找效率

    c）二叉樹(shù)存在各個(gè)數(shù)據(jù)查找效率不一致的情況，為了做到數(shù)據(jù)查找效率一致，人們?cè)O(shè)計(jì)了二叉平衡樹(shù)，左子樹(shù)和右子樹(shù)的高度絕對(duì)值之差要小于1

    d）為了減少子樹(shù)旋轉(zhuǎn)的次數(shù)，人們?cè)O(shè)計(jì)了紅黑樹(shù)，進(jìn)一步提高了數(shù)據(jù)插入和刪除的效率


（2）紅黑樹(shù)的概念

    a）紅黑樹(shù)的每個(gè)節(jié)點(diǎn)必須是紅色或者是黑色

    b）根節(jié)點(diǎn)到葉節(jié)點(diǎn)之間的路徑不存在連續(xù)的紅色節(jié)點(diǎn)

    c）根節(jié)點(diǎn)到葉節(jié)點(diǎn)之間的黑色節(jié)點(diǎn)數(shù)相同


（3）紅黑樹(shù)的基本結(jié)構(gòu)定義

  1. #ifndef _RBTREE_H  
  2. #define _RBTREE_H  
  3.   
  4. #include <stdio.h>  
  5.   
  6. struct rb_node  
  7. {  
  8.     struct rb_node *rb_parent;  
  9.     int rb_color;  
  10. #define RB_RED      0  
  11. #define RB_BLACK    1  
  12.     struct rb_node *rb_right;  
  13.     struct rb_node *rb_left;  
  14. };  
  15.   
  16. struct rb_root  
  17. {  
  18.     struct rb_node *rb_node;  
  19. };  
  20.   
  21. #define RB_ROOT { NULL }  
  22. #define rb_entry(ptr, type, member)                 \  
  23.     ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))  
  24.   
  25. extern void rb_insert_color(struct rb_node *, struct rb_root *);  
  26. extern void rb_erase(struct rb_node *, struct rb_root *);  
  27.   
  28. /* Find logical next and previous nodes in a tree */  
  29. extern struct rb_node *rb_next(struct rb_node *);  
  30. extern struct rb_node *rb_prev(struct rb_node *);  
  31. extern struct rb_node *rb_first(struct rb_root *);  
  32.   
  33. /* Fast replacement of a single node without remove/rebalance/add/rebalance */  
  34. extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,   
  35.                 struct rb_root *root);  
  36.   
  37. static void rb_link_node(struct rb_node * node, struct rb_node * parent,  
  38.                 struct rb_node ** rb_link)  
  39. {  
  40.     node->rb_parent = parent;  
  41.     node->rb_color = RB_RED;  
  42.     node->rb_left = node->rb_right = NULL;  
  43.   
  44.     *rb_link = node;  
  45. }  
  46.   
  47. #endif  /* _RBTREE_H */  

（4） 紅黑樹(shù)的實(shí)現(xiàn)

    a） 完成內(nèi)容

    1、調(diào)整插入節(jié)點(diǎn)rb_node的顏色

    2、在rb_root中刪除指定rb_node

    3、獲取首節(jié)點(diǎn)

    4、獲取上一個(gè)節(jié)點(diǎn)

    5、獲取下一個(gè)節(jié)點(diǎn)

    6、替換節(jié)點(diǎn)


    b）實(shí)現(xiàn)源代碼

  1. #include "rbtree.h"  
  2.   
  3. static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)  
  4. {  
  5.     struct rb_node *right = node->rb_right;  
  6.   
  7.     if ((node->rb_right = right->rb_left))  
  8.         right->rb_left->rb_parent = node;  
  9.     right->rb_left = node;  
  10.   
  11.     if ((right->rb_parent = node->rb_parent))  
  12.     {  
  13.         if (node == node->rb_parent->rb_left)  
  14.             node->rb_parent->rb_left = right;  
  15.         else  
  16.             node->rb_parent->rb_right = right;  
  17.     }  
  18.     else  
  19.         root->rb_node = right;  
  20.     node->rb_parent = right;  
  21. }  
  22.   
  23. static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)  
  24. {  
  25.     struct rb_node *left = node->rb_left;  
  26.   
  27.     if ((node->rb_left = left->rb_right))  
  28.         left->rb_right->rb_parent = node;  
  29.     left->rb_right = node;  
  30.   
  31.     if ((left->rb_parent = node->rb_parent))  
  32.     {  
  33.         if (node == node->rb_parent->rb_right)  
  34.             node->rb_parent->rb_right = left;  
  35.         else  
  36.             node->rb_parent->rb_left = left;  
  37.     }  
  38.     else  
  39.         root->rb_node = left;  
  40.     node->rb_parent = left;  
  41. }  
  42.   
  43. void rb_insert_color(struct rb_node *node, struct rb_root *root)  
  44. {  
  45.     struct rb_node *parent, *gparent;  
  46.   
  47.     while ((parent = node->rb_parent) && parent->rb_color == RB_RED)  
  48.     {  
  49.         gparent = parent->rb_parent;  
  50.   
  51.         if (parent == gparent->rb_left)  
  52.         {  
  53.             {  
  54.                 register struct rb_node *uncle = gparent->rb_right;  
  55.                 if (uncle && uncle->rb_color == RB_RED)  
  56.                 {  
  57.                     uncle->rb_color = RB_BLACK;  
  58.                     parent->rb_color = RB_BLACK;  
  59.                     gparent->rb_color = RB_RED;  
  60.                     node = gparent;  
  61.                     continue;  
  62.                 }  
  63.             }  
  64.   
  65.             if (parent->rb_right == node)  
  66.             {  
  67.                 register struct rb_node *tmp;  
  68.                 __rb_rotate_left(parent, root);  
  69.                 tmp = parent;  
  70.                 parent = node;  
  71.                 node = tmp;  
  72.             }  
  73.   
  74.             parent->rb_color = RB_BLACK;  
  75.             gparent->rb_color = RB_RED;  
  76.             __rb_rotate_right(gparent, root);  
  77.         } else {  
  78.             {  
  79.                 register struct rb_node *uncle = gparent->rb_left;  
  80.                 if (uncle && uncle->rb_color == RB_RED)  
  81.                 {  
  82.                     uncle->rb_color = RB_BLACK;  
  83.                     parent->rb_color = RB_BLACK;  
  84.                     gparent->rb_color = RB_RED;  
  85.                     node = gparent;  
  86.                     continue;  
  87.                 }  
  88.             }  
  89.   
  90.             if (parent->rb_left == node)  
  91.             {  
  92.                 register struct rb_node *tmp;  
  93.                 __rb_rotate_right(parent, root);  
  94.                 tmp = parent;  
  95.                 parent = node;  
  96.                 node = tmp;  
  97.             }  
  98.   
  99.             parent->rb_color = RB_BLACK;  
  100.             gparent->rb_color = RB_RED;  
  101.             __rb_rotate_left(gparent, root);  
  102.         }  
  103.     }  
  104.   
  105.     root->rb_node->rb_color = RB_BLACK;  
  106. }  
  107.   
  108. static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,  
  109.                  struct rb_root *root)  
  110. {  
  111.     struct rb_node *other;  
  112.   
  113.     while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)  
  114.     {  
  115.         if (parent->rb_left == node)  
  116.         {  
  117.             other = parent->rb_right;  
  118.             if (other->rb_color == RB_RED)  
  119.             {  
  120.                 other->rb_color = RB_BLACK;  
  121.                 parent->rb_color = RB_RED;  
  122.                 __rb_rotate_left(parent, root);  
  123.                 other = parent->rb_right;  
  124.             }  
  125.             if ((!other->rb_left ||  
  126.                  other->rb_left->rb_color == RB_BLACK)  
  127.                 && (!other->rb_right ||  
  128.                 other->rb_right->rb_color == RB_BLACK))  
  129.             {  
  130.                 other->rb_color = RB_RED;  
  131.                 node = parent;  
  132.                 parent = node->rb_parent;  
  133.             }  
  134.             else  
  135.             {  
  136.                 if (!other->rb_right ||  
  137.                     other->rb_right->rb_color == RB_BLACK)  
  138.                 {  
  139.                     register struct rb_node *o_left;  
  140.                     if ((o_left = other->rb_left))  
  141.                         o_left->rb_color = RB_BLACK;  
  142.                     other->rb_color = RB_RED;  
  143.                     __rb_rotate_right(other, root);  
  144.                     other = parent->rb_right;  
  145.                 }  
  146.                 other->rb_color = parent->rb_color;  
  147.                 parent->rb_color = RB_BLACK;  
  148.                 if (other->rb_right)  
  149.                     other->rb_right->rb_color = RB_BLACK;  
  150.                 __rb_rotate_left(parent, root);  
  151.                 node = root->rb_node;  
  152.                 break;  
  153.             }  
  154.         }  
  155.         else  
  156.         {  
  157.             other = parent->rb_left;  
  158.             if (other->rb_color == RB_RED)  
  159.             {  
  160.                 other->rb_color = RB_BLACK;  
  161.                 parent->rb_color = RB_RED;  
  162.                 __rb_rotate_right(parent, root);  
  163.                 other = parent->rb_left;  
  164.             }  
  165.             if ((!other->rb_left ||  
  166.                  other->rb_left->rb_color == RB_BLACK)  
  167.                 && (!other->rb_right ||  
  168.                 other->rb_right->rb_color == RB_BLACK))  
  169.             {  
  170.                 other->rb_color = RB_RED;  
  171.                 node = parent;  
  172.                 parent = node->rb_parent;  
  173.             }  
  174.             else  
  175.             {  
  176.                 if (!other->rb_left ||  
  177.                     other->rb_left->rb_color == RB_BLACK)  
  178.                 {  
  179.                     register struct rb_node *o_right;  
  180.                     if ((o_right = other->rb_right))  
  181.                         o_right->rb_color = RB_BLACK;  
  182.                     other->rb_color = RB_RED;  
  183.                     __rb_rotate_left(other, root);  
  184.                     other = parent->rb_left;  
  185.                 }  
  186.                 other->rb_color = parent->rb_color;  
  187.                 parent->rb_color = RB_BLACK;  
  188.                 if (other->rb_left)  
  189.                     other->rb_left->rb_color = RB_BLACK;  
  190.                 __rb_rotate_right(parent, root);  
  191.                 node = root->rb_node;  
  192.                 break;  
  193.             }  
  194.         }  
  195.     }  
  196.     if (node)  
  197.         node->rb_color = RB_BLACK;  
  198. }  
  199.   
  200. void rb_erase(struct rb_node *node, struct rb_root *root)  
  201. {  
  202.     struct rb_node *child, *parent;  
  203.     int color;  
  204.   
  205.     if (!node->rb_left)  
  206.         child = node->rb_right;  
  207.     else if (!node->rb_right)  
  208.         child = node->rb_left;  
  209.     else  
  210.     {  
  211.         struct rb_node *old = node, *left;  
  212.   
  213.         node = node->rb_right;  
  214.         while ((left = node->rb_left))  
  215.             node = left;  
  216.         child = node->rb_right;  
  217.         parent = node->rb_parent;  
  218.         color = node->rb_color;  
  219.   
  220.         if (child)  
  221.             child->rb_parent = parent;  
  222.         if (parent)  
  223.         {  
  224.             if (parent->rb_left == node)  
  225.                 parent->rb_left = child;  
  226.             else  
  227.                 parent->rb_right = child;  
  228.         }  
  229.         else  
  230.             root->rb_node = child;  
  231.   
  232.         if (node->rb_parent == old)  
  233.             parent = node;  
  234.         node->rb_parent = old->rb_parent;  
  235.         node->rb_color = old->rb_color;  
  236.         node->rb_right = old->rb_right;  
  237.         node->rb_left = old->rb_left;  
  238.   
  239.         if (old->rb_parent)  
  240.         {  
  241.             if (old->rb_parent->rb_left == old)  
  242.                 old->rb_parent->rb_left = node;  
  243.             else  
  244.                 old->rb_parent->rb_right = node;  
  245.         } else  
  246.             root->rb_node = node;  
  247.   
  248.         old->rb_left->rb_parent = node;  
  249.         if (old->rb_right)  
  250.             old->rb_right->rb_parent = node;  
  251.         goto color;  
  252.     }  
  253.   
  254.     parent = node->rb_parent;  
  255.     color = node->rb_color;  
  256.   
  257.     if (child)  
  258.         child->rb_parent = parent;  
  259.     if (parent)  
  260.     {  
  261.         if (parent->rb_left == node)  
  262.             parent->rb_left = child;  
  263.         else  
  264.             parent->rb_right = child;  
  265.     }  
  266.     else  
  267.         root->rb_node = child;  
  268.   
  269.  color:  
  270.     if (color == RB_BLACK)  
  271.         __rb_erase_color(child, parent, root);  
  272. }  
  273.   
  274. /* 
  275.  * This function returns the first node (in sort order) of the tree. 
  276.  */  
  277. struct rb_node *rb_first(struct rb_root *root)  
  278. {  
  279.     struct rb_node  *n;  
  280.   
  281.     n = root->rb_node;  
  282.     if (!n)  
  283.         return 0;  
  284.     while (n->rb_left)  
  285.         n = n->rb_left;  
  286.     return n;  
  287. }  
  288.   
  289. struct rb_node *rb_next(struct rb_node *node)  
  290. {  
  291.     /* If we have a right-hand child, go down and then left as far 
  292.        as we can. */  
  293.     if (node->rb_right) {  
  294.         node = node->rb_right;   
  295.         while (node->rb_left)  
  296.             node=node->rb_left;  
  297.         return node;  
  298.     }  
  299.   
  300.     /* No right-hand children.  Everything down and left is 
  301.        smaller than us, so any 'next' node must be in the general 
  302.        direction of our parent. Go up the tree; any time the 
  303.        ancestor is a right-hand child of its parent, keep going 
  304.        up. First time it's a left-hand child of its parent, said 
  305.        parent is our 'next' node. */  
  306.     while (node->rb_parent && node == node->rb_parent->rb_right)  
  307.         node = node->rb_parent;  
  308.   
  309.     return node->rb_parent;  
  310. }  
  311.   
  312. struct rb_node *rb_prev(struct rb_node *node)  
  313. {  
  314.     /* If we have a left-hand child, go down and then right as far 
  315.        as we can. */  
  316.     if (node->rb_left) {  
  317.         node = node->rb_left;   
  318.         while (node->rb_right)  
  319.             node=node->rb_right;  
  320.         return node;  
  321.     }  
  322.   
  323.     /* No left-hand children. Go up till we find an ancestor which 
  324.        is a right-hand child of its parent */  
  325.     while (node->rb_parent && node == node->rb_parent->rb_left)  
  326.         node = node->rb_parent;  
  327.   
  328.     return node->rb_parent;  
  329. }  
  330.   
  331. void rb_replace_node(struct rb_node *victim, struct rb_node *new,  
  332.              struct rb_root *root)  
  333. {  
  334.     struct rb_node *parent = victim->rb_parent;  
  335.   
  336.     /* Set the surrounding nodes to point to the replacement */  
  337.     if (parent) {  
  338.         if (victim == parent->rb_left)  
  339.             parent->rb_left = new;  
  340.         else  
  341.             parent->rb_right = new;  
  342.     } else {  
  343.         root->rb_node = new;  
  344.     }  
  345.     if (victim->rb_left)  
  346.         victim->rb_left->rb_parent = new;  
  347.     if (victim->rb_right)  
  348.         victim->rb_right->rb_parent = new;  
  349.   
  350.     /* Copy the pointers/colour from the victim to the replacement */  
  351.     *new = *victim;  
  352. }  

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類(lèi)似文章 更多