一.概念
紅黑樹是一棵二叉搜尋樹，它在每個節點上增加了一個存儲位來表示節點的顔色，可以是Red或Black。通過對任何一條從根到葉子簡單路徑上的顔色來限制，紅黑樹保證最長路徑不超過最短路徑的兩倍，因而近似于平衡。
2.性質：
- 每個節點，不是紅色就是黑色的
- 根節點是黑色的
- 如果一個節點是紅色的，則它的兩個子節點是黑色的(沒有連續的紅節點)
- 對每個節點，從該節點到其所有後代葉節點的簡單路徑上，均包含相同數目的黑色節點。（每條路徑的黑色節點的數量相等）
二.代碼實作
#include<iostream> using namespace std; enum COL { RED, BLACK }; template<class K, class V> struct RBTreeNode { K _key; V _value; COL _col; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; RBTreeNode(const K& key,const V& value) : _key(key) , _value(value) , _col(RED) , _left(NULL) , _right(NULL) , _parent(NULL) {} }; template<class K,class V> class RBTree { typedef RBTreeNode<K, V> Node; public: RBTree() :_root(NULL) {} ~RBTree() {} bool Insert(const K& key, const V& value) { //尋找插入節點的位置 if (_root == NULL) { _root = new Node(key, value); _root->_col = BLACK; return true; } Node* cur = _root; Node* parent = NULL; while (cur) { if (key > cur->_key) { parent = cur; cur = cur->_right; } else if (key < cur->_key) { parent = cur; cur = cur->_left; } else { return false; } } //插入 cur = new Node(key, value); if (key > parent->_key) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } //判斷是否符合紅黑樹 //判斷規則3（不能有連續的兩個紅節點） while (cur != _root&&parent->_col==RED)//cur!=_root保證了parent不為空 { Node* Grandparent = parent->_parent; //找叔叔節點 if (Grandparent->_left == parent) { Node* uncle = Grandparent->_right; //第一種情況：叔叔節點存在且為紅 if (uncle&&uncle->_col == RED) { //将parent和uncle變黑，grandparent變紅,再把cur指派給grandparent，向上調整 parent->_col = uncle->_col = BLACK; Grandparent->_col = RED; cur = Grandparent; parent = cur->_parent; } //第二種情況：叔叔節點不存在或為黑（此時grandparent、parent、cur構成了單旋的條件） else { //第三種情況：此時grandparent、parent、cur構成了雙旋的條件 if (parent->_right == cur) { //對parent做左單旋，轉換為第二種情況 RotateL(parent); //注意：旋轉後指針位置需交換 swap(parent, cur); } RotateR(Grandparent); //将parent變黑，grandparent變紅 parent->_col = BLACK; Grandparent->_col = RED; break; } } //和上面相反 else { Node* uncle = Grandparent->_left; //第一種情況 if (uncle&&uncle->_col == RED) { parent->_col = uncle->_col = BLACK; Grandparent->_col = RED; cur = Grandparent; parent = cur->_parent; } //第二種情況 else { //第三種情況 轉換為第二種情況 if (parent->_left == cur) { RotateR(parent); swap(parent, cur); } RotateL(Grandparent); parent->_col = BLACK; Grandparent->_col = RED; break; } } } _root->_col = BLACK; return true; } void InOrder() { _InOrder(_root); cout << endl; } bool IsBlance() { if (_root == NULL) return true; //第2條規則：根節點是黑色的 //判斷根節點 if (_root->_col == RED) { return false; } Node* cur = _root; int k = 0; while (cur) { //第4條規則：每條路徑的黑色節點的數量相等 //統計每個左右子樹黑色節點的個數 if (cur->_col == BLACK) { k++; } cur = cur->_left; } int count = 0; return _IsBlance(_root,k,count); } protected: Node* _root; void _InOrder(Node* root) { if (root == NULL) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } bool _IsBlance(Node* root,const int k,int count) { if (root == NULL) return true; //第3條規則：沒有連續的紅節點 if (root->_col == RED) { if (root->_parent->_col == RED) { cout << "顔色不對" << root->_key << endl; return false; } } //統計黑色節點 else { ++count; } if (root->_left == NULL&&root->_right) { if (count == k) return true; else { cout << "黑色節點數量不相同" << root->_key << endl; return false; } } return _IsBlance(root->_left, k, count) && _IsBlance(root->_right, k, count); } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (ppNode == NULL) { _root = subR; subR->_parent = NULL; } else { subR->_parent = ppNode; if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } Node* ppNode = parent->_parent; subL->_right = parent; parent->_parent = subL; if (ppNode == NULL) { _root = subL; subL->_parent = NULL; } else { subL->_parent = ppNode; if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } } } }; int main() { int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; RBTree<int, int> rbt; for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { rbt.Insert(a[i],i); cout <<a[i]<< " Is Blance ?" << rbt.IsBlance() << endl; } rbt.InOrder(); cout<<"Is Blance ?"<<rbt.IsBlance()<<endl; system("pause"); return 0; } ![#拍照#素人模特#快遞#ice#blackpink[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)