數據結構

紅黑樹理論及實現上一篇:DFS非遞歸實現方式下一篇:AVL樹的C語言實現作者:dzf閱讀次數:253時間:2006-12-3 13:41:25數據結構紅黑樹二叉樹在平衡時或者葉子結點到根結點的高度在一定的範圍內時工作起來是最有效的。紅黑樹演算法是平衡樹的一種演算法。這個名字就是由於樹的每個結點都被著上了紅色或者黑色，結點所著的顏色被用來檢測樹的平衡性。在對結點插入和刪除的操作中，可能會被旋轉來保持樹的平衡性。平均和最壞情況插入，刪除，查找時間都是 O (lg n)。詳細內容請參考Cormen [2001]。理論一個紅黑樹是一顆二叉查找樹，具有下列的屬性:1. 所有的結點都被著色為紅色或者是黑色。2. 每一個葉子結點都是空結點，並且被著為黑色。3. 如果父結點是紅色的，那麼兩個子結點都是黑色的。4. 結點到其子孫結點的每條簡單路徑上都包含相同數目的黑色結點。5. 根結點永遠是黑色的。從根結點到葉結點的黑色結點數被稱為樹的黑色高度。前面關於紅黑樹的性質保證了從根結點到葉結點的路徑長度不會超過任何其他路徑的兩倍。我們來看一下為什麼這個結論是正確的。考慮一顆黑色高度為3 得紅黑樹，從根結點到葉結點的最短路徑長度是2(黑-黑-黑)，最長路徑為4(黑-紅-黑-紅-黑)。由於第4條性質，不可能在最長路徑中加入更多的黑色 結點，因為性質3規定紅色結點的子結點必須是黑色的，因此在同一簡單路徑中不允許有兩個連續的紅色結點。因此，我們能夠建立的最長路徑將是一個紅黑交替的 路徑。概括起來：對於給定的黑色高度為n的紅黑樹，從根結點到葉結點的簡單路徑的最短長度為n-1，最大長度為2(n-1)。所有對樹的操作必須保持上面列出的屬性。特別要指出的是，插入和刪除樹的結點的操作必須遵循這些原則。插入要插入結點，搜索這棵樹，找到插入點並添加結點。新的結點替代一個已經存在的在樹底部的空結點，並且將擁有兩個作為子結點的空結點，在簡單的實現中，空結點就是就是一個指向被染為黑色的監視結點的指針，提醒C語言程序員 — 這不是一個空指針！插入新的結點之後，新的結點被染為紅色。而後，結點的父結點會被測試看看紅黑樹的屬性有沒有被保留下來。如果需要，做一些調整已適應平衡樹的需求。當插入一個紅色結點以及他帶的兩個空的子結點時符合性質4，我們還必須確保紅色結點的兩個子結點都是黑色的(性質3)。儘管如此，新結點的子結點是黑色時，插入紅色的子結點將是違反屬性的。這時存在兩種要考慮的情況。紅色父結點，父結點的紅色兄弟結點圖3-6 描述了一個紅-紅錯誤。結點 X 是新插入的結點, 父結點和父親兄弟結點都被著為紅色。一個簡單的著色就可以解決這個紅-紅錯誤。在重著色後必須檢查祖父結點 (結點 B )是否合法，因為它的父結點也可能是紅色的，我們不允許連續出現兩個紅色結點。這樣會產生使紅色結點上移的效果。結束時根結點應當是黑色的，如果它原先是紅色的，則紅黑樹的黑色高度將增1。

圖 3-6: 插入 -紅色父結點，父結點的紅色兄弟結點紅色父結點,父結點的黑色兄弟結點圖 3-7 描述了一個紅-紅錯誤，父親的兄弟結點是黑色的。如果我們試圖給結點重新著色,將結點 A 著成黑色, 這棵樹就不平衡了因為我們增加了左支的黑色高度而沒有同時增加右支的黑色高度。如果我們同時將結點B改成紅色, 兩支的黑色高度減小，而且樹還是不平衡。如果我們將節點 A 染成黑色，節點C染成紅色。情況更為糟糕。因為我們增加了左支的黑色高度，但是減小了右支的黑色高度。為了解決這個問題，我們將要旋轉並且重新為結點作如 下的著色。在這點上，這個演算法就結束了，因為子樹的頂點 (節點A)被著為黑色，這樣就沒有紅-紅衝突了。

圖 3-7: 插入 - 紅色父結點,父結點的黑色兄弟結點結束為了插入一個結點，我們可能要對結點進行重新著色或者旋轉來確保紅黑樹的屬性。 如果完成了旋轉，作了簡單的重著色，我們看到的是紅色的結點在子樹的頂部，必需遍歷這棵樹，重複這個過程以確保黑色高度屬性的保持。最壞的情況是，我們會一直執行到根結點。插入時間為O(lg n).刪除的技術方法和時間與此類似。// C語言實現// red-black tree#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdarg.h>//////////////////////// supplied by user ////////////////////////typedef int KeyType; // type of keytypedef struct { // value related to keyint stuff;} ValType;// how to compare keys#define compLT(a,b) (a < b)#define compEQ(a,b) (a == b)/////////////////////////////////////// implementation independent code ///////////////////////////////////////typedef enum {RBT_STATUS_OK,RBT_STATUS_MEM_EXHAUSTED,RBT_STATUS_DUPLICATE_KEY,RBT_STATUS_KEY_NOT_FOUND} RbtStatus;typedef enum { BLACK, RED } nodeColor;typedef struct NodeTag {struct NodeTag *left; // left childstruct NodeTag *right; // right childstruct NodeTag *parent; // parentnodeColor color; // node color (BLACK, RED)KeyType key; // key used for searchingValType val; // data related to key} NodeType;#define SENTINEL &sentinel // all leafs are sentinelsstatic NodeType sentinel = { SENTINEL, SENTINEL, 0, BLACK, 0};static NodeType *root = SENTINEL; // root of red-black treestatic void rotateLeft(NodeType *x) {// rotate node x to leftNodeType *y = x->right;// establish x->right linkx->right = y->left;if (y->left != SENTINEL) y->left->parent = x;// establish y->parent linkif (y != SENTINEL) y->parent = x->parent;if (x->parent) {if (x == x->parent->left)x->parent->left = y;elsex->parent->right = y;} else {root = y;}// link x and yy->left = x;if (x != SENTINEL) x->parent = y;}static void rotateRight(NodeType *x) {// rotate node x to rightNodeType *y = x->left;// establish x->left linkx->left = y->right;if (y->right != SENTINEL) y->right->parent = x;// establish y->parent linkif (y != SENTINEL) y->parent = x->parent;if (x->parent) {if (x == x->parent->right)x->parent->right = y;elsex->parent->left = y;} else {root = y;}// link x and yy->right = x;if (x != SENTINEL) x->parent = y;}static void insertFixup(NodeType *x) {// maintain red-black tree balance// after inserting node x// check red-black propertieswhile (x != root && x->parent->color == RED) {// we have a violationif (x->parent == x->parent->parent->left) {NodeType *y = x->parent->parent->right;if (y->color == RED) {// uncle is REDx->parent->color = BLACK;y->color = BLACK;x->parent->parent->color = RED;x = x->parent->parent;} else {// uncle is BLACKif (x == x->parent->right) {// make x a left childx = x->parent;rotateLeft(x);}// recolor and rotatex->parent->color = BLACK;x->parent->parent->color = RED;rotateRight(x->parent->parent);}} else {// mirror image of above codeNodeType *y = x->parent->parent->left;if (y->color == RED) {// uncle is REDx->parent->color = BLACK;y->color = BLACK;x->parent->parent->color = RED;x = x->parent->parent;} else {// uncle is BLACKif (x == x->parent->left) {x = x->parent;rotateRight(x);}x->parent->color = BLACK;x->parent->parent->color = RED;rotateLeft(x->parent->parent);}}}root->color = BLACK;}// insert new node (no duplicates allowed)RbtStatus rbtInsert(KeyType key, ValType val) {NodeType *current, *parent, *x;// allocate node for data and insert in tree// find future parentcurrent = root;parent = 0;while (current != SENTINEL) {if (compEQ(key, current->key))return RBT_STATUS_DUPLICATE_KEY;parent = current;current = compLT(key, current->key) ?current->left : current->right;}// setup new nodeif ((x = malloc (sizeof(*x))) == 0)return RBT_STATUS_MEM_EXHAUSTED;x->parent = parent;x->left = SENTINEL;x->right = SENTINEL;x->color = RED;x->key = key;x->val = val;// insert node in treeif(parent) {if(compLT(key, parent->key))parent->left = x;elseparent->right = x;} else {root = x;}insertFixup(x);return RBT_STATUS_OK;}static void deleteFixup(NodeType *x) {// maintain red-black tree balance// after deleting node xwhile (x != root && x->color == BLACK) {if (x == x->parent->left) {NodeType *w = x->parent->right;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rotateLeft (x->parent);w = x->parent->right;}if (w->left->color == BLACK && w->right->color == BLACK) {w->color = RED;x = x->parent;} else {if (w->right->color == BLACK) {w->left->color = BLACK;w->color = RED;rotateRight (w);w = x->parent->right;}w->color = x->parent->color;x->parent->color = BLACK;w->right->color = BLACK;rotateLeft (x->parent);x = root;}} else {NodeType *w = x->parent->left;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;rotateRight (x->parent);w = x->parent->left;}if (w->right->color == BLACK && w->left->color == BLACK) {w->color = RED;x = x->parent;} else {if (w->left->color == BLACK) {w->right->color = BLACK;w->color = RED;rotateLeft (w);w = x->parent->left;}w->color = x->parent->color;x->parent->color = BLACK;w->left->color = BLACK;rotateRight (x->parent);x = root;}}}x->color = BLACK;}// delete nodeRbtStatus rbtErase(NodeType * z) {NodeType *x, *y;if (z->left == SENTINEL || z->right == SENTINEL) {// y has a SENTINEL node as a childy = z;} else {// find tree successor with a SENTINEL node as a childy = z->right;while (y->left != SENTINEL) y = y->left;}// x is y『s only childif (y->left != SENTINEL)x = y->left;elsex = y->right;// remove y from the parent chainx->parent = y->parent;if (y->parent)if (y == y->parent->left)y->parent->left = x;elsey->parent->right = x;elseroot = x;if (y != z) {z->key = y->key;z->val = y->val;}if (y->color == BLACK)deleteFixup (x);free (y);return RBT_STATUS_OK;}// find keyNodeType *rbtFind(KeyType key) {NodeType *current;current = root;while(current != SENTINEL) {if(compEQ(key, current->key)) {return current;} else {current = compLT (key, current->key) ?current->left : current->right;}}return NULL;}// in-order walk of treevoid rbtInorder(NodeType *p, void (callback)(NodeType *)) {if (p == SENTINEL) return;rbtInorder(p->left, callback);callback(p);rbtInorder(p->right, callback);}// delete nodes depth-firstvoid rbtDelete(NodeType *p) {if (p == SENTINEL) return;rbtDelete(p->left);rbtDelete(p->right);free(p);}void displayNode(NodeType *p) {printf("%d %d
", p->key, p->val.stuff);}int main(int argc, char **argv) {int maxnum, ct;KeyType key;RbtStatus status;// command-line://// rbt 2000// process 2000 recordsNodeType *p;maxnum = atoi(argv[1]);printf("maxnum = %d
", maxnum);for (ct = maxnum; ct; ct--) {key = rand() % 90 + 1;if ((p = rbtFind(key)) != NULL) {if (p->val.stuff != 10*key) printf("fail val
");status = rbtErase(p);if (status) printf("fail: status = %d
", status);} else {ValType val;val.stuff = 10*key;status = rbtInsert(key, val);if (status) printf("fail: status = %d
", status);}}// output nodes in orderrbtInorder(root, displayNode);rbtDelete(root);return 0;}C語言實現 一個用ANSI-C 實現的紅黑樹包含在這裡。 Typedefs recType , keyType , 以及 compLT 和 compEQ 應當改變以反映在樹中的數據存儲。每一個結點都由 left , right , 和 parent 指針組成。指出每個子結點和父結點。結點的顏色存儲在 color 中, 或者是 RED 或者是 BLACK . 所有的椰子結點都是一個監視結點。函數 insert 分配了一個新的結點並且將這個結點插入樹當中。而後，它調用 insertFixup 來確保紅黑樹屬性的維持 erase 從樹中刪除個結點，為了維護紅黑樹的屬性, deleteFixup 會被調用。函數 find 查找樹中的一個特殊值
推薦閱讀：