紅黑樹是一種自平衡的二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組(C++?STL?中的map/set)。它是在1972年由Rudolf?Bayer發明的，他稱之為"對稱二叉B樹"，它現代的名字是在?Leo?J.?Guibas?和?Robert?Sedgewick?于1978年寫的一篇論文中獲得的。紅黑樹雖然很復雜，但它的操作有著良好的最壞情況運行時間，并且在實踐中是高效的：?它可以在O(log?n)時間內做查找，插入和刪除，這里的n?是樹中元素的數目(來源:百度百科)。

?

算法導論對R-B?Tree的介紹：

紅黑樹，一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的。

?

由于紅黑樹也是一顆二叉查找樹,?因此紅黑樹也滿足二叉查找樹的一般性質(關于二叉查找樹的一般性質請參考博客:http://blog.csdn.net/zjf280441589/article/details/42611161)

但由于普通的二叉查找樹不具備自動平衡的功能,?因此普通的二叉查找樹樹很有可能會退化成為一條鏈表,?若二叉樹退化成了一棵具有n個結點的線性鏈后，則插入/刪除/查找操作最壞情況運行時間就變為了O（n）。

因此就有了紅黑樹,?他的最終查找、插入、刪除的時間復雜度最壞情況下依然為O（logn）,?而紅黑樹之所以這么牛的原因就是它在二叉查找樹的基礎上增加了著色和相關的性質,?這就是紅黑規則:

紅黑規則

? ?1.每一個節點不是紅色的就是黑色的;

? ?2.根總是黑色的;

? ?3.如果節點是紅色的,?則它的子節點必須是黑色的;

? ?4.從根到葉節點的每條路徑,?必須包含相同數目的黑色節點(黑高度相同);

? ?5.每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）是黑的;

? 根據規則4,?新增節點必須為紅;?

? 根據規則3,?新增節點之父節點必須為黑. ?

? 當新節點根據二叉樹的規則到達插入點,?卻未能符合上述紅黑規則時,?就必須調整顏色并旋轉樹形;

?

紅黑結點

template <typename Type> class RedBlackNode {friend RedBlackTree<Type>; private:RedBlackNode(const Type &_element = Type(),RedBlackNode *_left = NULL,RedBlackNode *_right = NULL,int _color = RedBlackTree<Type>::BLACK): element(_element), left(_left), right(_right), color(_color) {}private: //為了在紅黑樹尚未完成的時候進行測試 //故將之作為public, 待紅黑樹完成之時, //就是將其改為private之時; public:Type element; //節點值RedBlackNode *left;RedBlackNode *right;//紅黑樹的顏色int color; };

紅黑樹

template <typename Type> class RedBlackTree { public://為結點定義別名typedef RedBlackNode<Type> Node;enum {RED, BLACK};public://此時紅黑樹所支持的操作尚不完善,//而且函數功能(如析構函數, insert操作)//實現的也并不理想,//但隨著紅黑樹代碼的不斷演進,//這些代碼會不斷的完善RedBlackTree(const Type &negInf);~RedBlackTree();void insert(const Type &data);private: //為了在紅黑樹尚未完成的時候進行測試 //故將之作為public, 待紅黑樹完成之時, //就是將其改為private之時; public://指向紅黑樹的頭(偽根節點)//RedBlackNode<Type> *header;Node *header;//空節點Node *nullNode;//在插入過程中需要的指針Node *current; //當前節點Node *parent; //父節點Node *grand; //祖父節點(爺爺)Node *great; //曾祖父節點(爺爺的爸爸)/* 單旋轉 *///帶著左孩子旋轉: 向右旋轉void rotateWithLeftChild(Node *& k2) const;//帶著有孩子旋轉: 向左旋轉void rotateWithRightChild(Node *& k1) const;/* 雙旋轉 *///向右轉void doubleRotateWithLeftChild(Node *& k3) const;//向左轉void doubleRotateWithRightChild(Node *& k1) const; };

構造與析構

//構造函數 template <typename Type> RedBlackTree<Type>::RedBlackTree(const Type &negInf) {nullNode = new Node();header = new Node(negInf, nullNode, nullNode); } //這一版的析構函數實現并不完善,在后續的版本我們會繼續完善該析構函數 template <typename Type> RedBlackTree<Type>::~RedBlackTree() {delete nullNode;delete header; }

一個二叉查找樹的insert

//這時的insert其實就是一個普通的 //二叉查找樹的insert, 完全沒要照顧到 //二叉樹的平衡, 以及紅黑規則的實現 template <typename Type> void RedBlackTree<Type>::insert(const Type &data) {great = grand = parent = current = header;//在此處令nullNode成為data, 以作哨兵nullNode->element = data;while (current->element != data){//讓祖父成為曾祖父, 父親成為祖父, 自己成為父親//每個人都長了一輩great = grand;grand = parent;parent = current;current = (data < current->element) ? current->left: current->right;}//如果樹中包含相同的元素if (current != nullNode)throw DuplicateItemException();current = new Node(data, nullNode, nullNode);if (data < parent->element)parent->left = current;elseparent->right = current;//在后續的版本上,需要加上自動平衡(即實現紅黑規則) -> 紅黑樹 }

單旋轉

注意:內側孫子節點橫向移動(注意下圖結點37);

?

左(單)旋:

?

當在某個結點k1上，做左旋操作時，我們假設它的右孩子k2不是NIL[T](k1可以是任何不是NIL[T]的左孩子結點);?左旋以k1到k2之間的鏈為“支軸”進行，它使k2成為該子樹新的根，而k2的左孩子B則成為k1的右孩子。?

//實現 //向左轉 template <typename Type> void RedBlackTree<Type>::rotateWithRightChild(Node *& k1) const {Node *k2 = k1->right;//結點B橫向移動k1->right = k2->left;//令k2提領k1k2->left = k1;//令k2為根(使k2替代k1的位置)k1 = k2; }

右(單)旋:

?

? ? 過程與左旋類似;

//實現 //向右轉 template <typename Type> void RedBlackTree<Type>::rotateWithLeftChild(Node *& k2) const {//首先將B橫向移動Node *k1 = k2->left;k2->left = k1->right;//令k1提領k2k1->right = k2;//令k1為根(使k1替代k2的位置)k2 = k1; }

測試(在完成單旋轉之后):

?

? ? (構造一顆二叉查找樹樹如圖所示,?左邊為尚未旋轉之前,?右為旋轉之后)

//測試代碼如下: int main() {//用NEG_INF來代表負無窮大const int NEG_INF = -999999;RedBlackTree<int> tree(NEG_INF);//單旋轉時候的測試數據tree.insert(30);tree.insert(15);tree.insert(70);tree.insert(20);cout << tree.header->right->element << endl;cout << tree.header->right->left->element << endl;cout << tree.header->right->right->element << endl;cout << tree.header->right->left->right->element << endl; //20//向右旋轉cout << "向右旋轉" << endl;tree.rotateWithLeftChild(tree.header->right);cout << tree.header->right->element << endl; //15cout << tree.header->right->right->element << endl; //30cout << tree.header->right->right->left->element << endl; //20cout << tree.header->right->right->right->element << endl; //70//然后再向左轉(又轉了回來)cout << "向左旋轉" << endl;tree.rotateWithRightChild(tree.header->right);cout << tree.header->right->element << endl;cout << tree.header->right->left->element << endl;cout << tree.header->right->right->element << endl;cout << tree.header->right->left->right->element << endl; //20 }

雙旋轉

單旋轉有時會出現一個問題(如下圖所示):

? ? (如果內側子孫節點[k1]過深,?則將其單向移動是不會解決問題的)

?

于是就有了雙旋轉

向右雙旋轉:

? ?1.首先以k1為軸,?k1與k2向左旋轉;

? ?2.然后以k3為軸,?k3與旋轉之后的k1向右旋轉;

//實現 //向右雙旋轉 template <typename Type> void RedBlackTree<Type>::doubleRotateWithLeftChild(Node *& k3) const {//首先將其左兒子(k1)向左單旋轉rotateWithRightChild(k3->left);//然后將自己(k3)向右單旋轉rotateWithLeftChild(k3); }

向左雙旋轉:

? ?1.首先以k3為軸,?k2與k3向右旋轉;

? ?2.然后以k1為軸,?k1與旋轉之后的k2向左旋轉;

//實現 //向左雙旋轉 template <typename Type> void RedBlackTree<Type>::doubleRotateWithRightChild(Node *& k1) const {//首先將其右兒子(k2)向右單旋轉rotateWithLeftChild(k1->right);//然后將自己(k1)向左單旋轉rotateWithRightChild(k1); } //注:其實紅黑樹中并沒有用到雙旋轉, 而是自己實現了一個rotate操作, //在此只為了學習雙旋轉的理論;

測試(在完成雙旋轉之后):

(構造一顆二叉查找樹樹如圖所示,?左邊為尚未旋轉之前,?右為旋轉之后,?以8為軸進行雙旋轉)

int main() {//用NEG_INF來代表負無窮大const int NEG_INF = -999999;RedBlackTree<int> tree(NEG_INF);//雙旋轉時的測試數據tree.insert(12);tree.insert(16);tree.insert(8);tree.insert(10);tree.insert(4);tree.insert(14);tree.insert(2);tree.insert(6);tree.insert(5);cout << tree.header->right->element << endl; //12cout << tree.header->right->left->element << endl; //8cout << tree.header->right->right->element << endl; //16cout << tree.header->right->left->left->element << endl; //4cout << tree.header->right->left->right->element << endl; //10cout << tree.header->right->right->left->element << endl; //14 // cout << tree.header->right->left->right->left->element << endl; //5曾經做過哨兵 // cout << tree.header->right->left->right->right->element << endl; //5cout << tree.header->right->left->left->left->element << endl; //2cout << tree.header->right->left->left->right->element << endl; //6cout << tree.header->right->left->left->right->left->element << endl; //5cout << "\n向右雙旋轉" << endl;//以8為基準向右雙旋轉tree.doubleRotateWithLeftChild(tree.header->right->left);cout << tree.header->right->element << endl; //12cout << tree.header->right->left->element << endl; //6cout << tree.header->right->right->element << endl; //16cout << tree.header->right->left->left->element << endl; //4cout << tree.header->right->left->right->element << endl; //8cout << tree.header->right->right->left->element << endl; //14cout << tree.header->right->left->left->left->element << endl; //2cout << tree.header->right->left->left->right->element << endl; //5cout << tree.header->right->left->right->right->element << endl; //10 }

實現紅黑樹用到的異常

class DSException { public:DSException(const string &_message = string()): message(_message) {}~DSException() {}virtual string what() const{return message;}virtual string toString() const{return "Exception: " + what();}private:std::string message; };class DuplicateItemException : public DSException { public:DuplicateItemException(const string &_msg = string()): DSException(_msg) {} };

總結

以上是生活随笔為你收集整理的数据结构拾遗(1) --红黑树的设计与实现(上)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。