红黑树—BTree
什么叫紅黑樹(shù)？
同AVL樹(shù)一樣，紅黑樹(shù)也是近似平衡的二叉搜索樹(shù)，與AVL樹(shù)不同的是紅黑樹(shù)沒(méi)有了平衡因子，但增加了一個(gè)枚舉變量，來(lái)標(biāo)明結(jié)點(diǎn)的顏（RED or BLACK）。因?yàn)榧t黑樹(shù)可以保證它的最長(zhǎng)路勁不超過(guò)它最短路徑的兩倍，所以它近似平衡。
紅黑樹(shù)具有以下幾點(diǎn)性質(zhì)：?
1. 每個(gè)結(jié)點(diǎn)都必須具有一種顏色（RED or BLACK）。?
2. 根結(jié)點(diǎn)為黑色。?
3. 如果一個(gè)結(jié)點(diǎn)為紅色，那么它的兩個(gè)孩子結(jié)點(diǎn)均為黑色（沒(méi)有連續(xù)的紅結(jié)點(diǎn)）。?
4. 對(duì)于每個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)到其所有后代葉子結(jié)點(diǎn)的路徑上，黑色結(jié)點(diǎn)的數(shù)量相同。?
5. 每個(gè)空結(jié)點(diǎn)（NIL結(jié)點(diǎn)）都當(dāng)作一個(gè)黑色結(jié)點(diǎn)。
下圖為一棵簡(jiǎn)單的紅黑樹(shù)：?
如何去創(chuàng)建并維護(hù)一棵紅黑樹(shù)？
紅黑樹(shù)的難點(diǎn)與AVL樹(shù)相同，插入一個(gè)結(jié)點(diǎn)并不難，難點(diǎn)在于插入一個(gè)結(jié)點(diǎn)后，很容易破壞這棵樹(shù)的平衡，我們就需要做一些調(diào)整工作讓這棵樹(shù)恢復(fù)平衡 。?
那么什么時(shí)候需要我們做調(diào)整工作呢？看上面紅黑樹(shù)性質(zhì)第三點(diǎn)，一棵紅黑樹(shù)需要滿足沒(méi)有連續(xù)的紅結(jié)點(diǎn)。?
需要調(diào)整的兩種情況：?
1. 當(dāng)我們對(duì)一個(gè)紅結(jié)點(diǎn)下插入一個(gè)紅結(jié)點(diǎn)時(shí)，出現(xiàn)了連續(xù)的紅結(jié)點(diǎn)。調(diào)整。?
2. 調(diào)整需要改變結(jié)點(diǎn)的顏色，當(dāng)我們把一個(gè)黑結(jié)點(diǎn)變?yōu)榧t結(jié)點(diǎn)，而恰好這個(gè)結(jié)點(diǎn)的父親是一個(gè)紅結(jié)點(diǎn)。又出現(xiàn)了連續(xù)的紅結(jié)點(diǎn)。繼續(xù)調(diào)整。
同時(shí)，性質(zhì)第4點(diǎn)也很重要， 對(duì)于每個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)到其所有后代葉子結(jié)點(diǎn)的路徑上，黑色結(jié)點(diǎn)的數(shù)量相同。當(dāng)我們對(duì)一棵子樹(shù)進(jìn)行調(diào)整，這棵子樹(shù)也可能擁有一棵兄弟子樹(shù)，所以我們不能改變當(dāng)前子樹(shù)上黑色節(jié)點(diǎn)的數(shù)量，即路徑上黑結(jié)點(diǎn)的數(shù)量不能改變。?
總結(jié)下來(lái)，調(diào)整方案就是：遇到連續(xù)紅結(jié)點(diǎn)就調(diào)整，調(diào)整的同時(shí)要保證路徑上黑色節(jié)點(diǎn)的數(shù)量不變。
PS：①在下面的講解中會(huì)改變結(jié)點(diǎn)的顏色，當(dāng)我們遇到連續(xù)的紅結(jié)點(diǎn)并進(jìn)行調(diào)整時(shí)，我們并不知道這個(gè)紅結(jié)點(diǎn)怎么來(lái)的，可能是新插入的，也可能是之前的調(diào)整由黑結(jié)點(diǎn)變過(guò)來(lái)的。②叔叔結(jié)點(diǎn)（uncle）。③a、b、c、d、e均為子樹(shù)，若一個(gè)為空，則都為空，此時(shí)cur為新插入結(jié)點(diǎn)。若不為空，則都不為空，此時(shí)cur為被調(diào)整改變的結(jié)點(diǎn)。注意這個(gè)三個(gè)概念，會(huì)幫助我們理解下面的講解。
插入情況1：
當(dāng)前結(jié)點(diǎn)cur為紅，父親結(jié)點(diǎn)parent為紅，gparent為黑，叔叔結(jié)點(diǎn)uncle存在且為紅。?
①?
?
②?
這種情況我們只需要改變結(jié)點(diǎn)顏色，不需要挪動(dòng)結(jié)點(diǎn)位置。?
顏色調(diào)整：將parent與叔叔結(jié)點(diǎn)uncle的顏色變?yōu)楹谏?#xff0c;將gparent的顏色變?yōu)榧t色。?
繼續(xù)向上調(diào)整：令cur = gparent，parent = gparent->_parent。繼續(xù)向上調(diào)整。
代碼
uncle->_col = parent->_col = BLACK; Gparent->_col = RED;// Gparent 可能為子樹(shù)，保證黑色節(jié)點(diǎn)數(shù)量不變//繼續(xù)向上調(diào)整 cur = Gparent; parent = cur->_parent;插入情況2：
當(dāng)前結(jié)點(diǎn)cur為紅色，parent為紅色，gparent為紅色，叔叔結(jié)點(diǎn)uncle不存在或者為黑。(ps：當(dāng)uncle結(jié)點(diǎn)不存在時(shí)，所有子樹(shù)都不存在，cur為新插入結(jié)點(diǎn)，當(dāng)uncle存在且為黑時(shí)，cur為被調(diào)整改變的結(jié)點(diǎn)。以下我們以u(píng)ncle存在且為黑為例。)
這個(gè)情況又可分為兩種小情況：?
① parent為gparent的左孩子，cur為parent的左孩子。?
?
這種情況需要對(duì)gparent進(jìn)行右單旋操作，看過(guò)之前我寫(xiě)的AVL樹(shù)講解的朋友們相信已經(jīng)對(duì)旋轉(zhuǎn)操作不再陌生了，這里我再講一下。?
旋轉(zhuǎn)操作：將parent的右子樹(shù)變成gparent的左子樹(shù)，將gparent以及其子樹(shù)變成parent的右子樹(shù)。將gparent的父親結(jié)點(diǎn)指向parent。?
顏色調(diào)整：將parent的顏色變成黑色，將gparent的顏色變成紅色。?
繼續(xù)向上調(diào)整：令cur = parnet， parent = parent->_parnet.
代碼：
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){if (ppNode->_left == parent)ppNode->_left = SubL;elseppNode->_right = SubL;SubL->_parent = ppNode;}else{SubL->_parent = NULL;_root = SubL;} }② parent為gparent的右孩子，cur為parent的右孩子。?
?
這種情況需要對(duì)gparent進(jìn)行左單旋操作。?
旋轉(zhuǎn)操作：將parent 的左子樹(shù)變?yōu)間parent的右子樹(shù)，將gparent以及其子樹(shù)變成parent的左子樹(shù)，將gparnet的父親結(jié)點(diǎn)指向parent。?
顏色調(diào)整：將parent變?yōu)楹谏?#xff0c;將gparent變?yōu)榧t色。?
繼續(xù)向上調(diào)整：令cur = parent，parent = parent->_parent。
代碼
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){if (ppNode->_left == parent)ppNode->_left = SubR;elseppNode->_right = SubR;SubR->_parent = ppNode;}else{SubR->_parent = NULL;_root = SubR;} }插入情況3：
當(dāng)前節(jié)點(diǎn)cur為紅色，parent為紅色，gparent為黑色。叔叔uncle結(jié)點(diǎn)不存在或?yàn)楹?ps：當(dāng)uncle結(jié)點(diǎn)不存在時(shí)，所有子樹(shù)都不存在，cur為新插入結(jié)點(diǎn)，當(dāng)uncle存在且為黑時(shí)，cur為被調(diào)整改變的結(jié)點(diǎn)。以下我們以u(píng)ncle存在且為黑為例。)
這種情況也可分成兩種：?
①parent為gparent左孩子，cur為parent右孩子。?
?
這種情況需要先對(duì)parent進(jìn)行左單旋操作，轉(zhuǎn)換為情況2的第①種情況。?
再進(jìn)行情況2的①操作。注意：左單旋之后，parent指針指向的位置，與cur指針指向的位置已經(jīng)改變。再進(jìn)行情況2的②操作之前需要交換parent與cur指針。調(diào)用swap函數(shù)swap（parent，cur）。
代碼：
if (cur == parent->_right) {RotateL(parent);swap(parent, cur);//保證parent指針?biāo)赶虻奈恢貌蛔?/span> } RotateR(Gparent);//保證左右子樹(shù)的黑色節(jié)點(diǎn)數(shù)量不變 parent->_col = BLACK; Gparent->_col = RED; //繼續(xù)向上調(diào)整cur = parent; parent = cur->_parent;②parent為gparent右孩子，cur為parent左孩子。?
?
這種情況需要先對(duì)parent進(jìn)行右單旋操作，轉(zhuǎn)換為情況2的第②種情況。?
再進(jìn)行情況2的②操作。同上，交換parent與cur指針。調(diào)用swap函數(shù)swap（parent，cur）。
代碼
if (cur == parent->_left) {RotateR(parent);swap(parent, cur); } RotateL(Gparent);parent->_col = BLACK; Gparent->_col = RED;cur = parent; parent = cur->_parent;總結(jié)?
紅黑樹(shù)與AVL樹(shù)都是高效的平衡二叉樹(shù)，增刪查改時(shí)間復(fù)雜的都為O（lgN），但是紅黑樹(shù)并不追求完全平衡，可以保證最長(zhǎng)路徑不超過(guò)最短路徑的2倍，相對(duì)而言，降低了旋轉(zhuǎn)要求，性能相對(duì)優(yōu)于AVL樹(shù)，所以實(shí)際運(yùn)用中紅黑樹(shù)運(yùn)用較多。
完整代碼
頭文件 RBTree.h
#pragma once #include<iostream> using namespace std;enum Colour {RED,BLACK };template<typename K,typename V> struct RBTreeNode {K _key;V _value;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const K& key, const V& value):_key(key), _value(value), _left(NULL), _right(NULL), _parent(NULL), _col(RED){} };template<typename K, typename V> class RBTree {typedef RBTreeNode<K, V> Node; public:RBTree():_root(NULL){}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 = cur;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;}//調(diào)整//parent肯定不為空//如果parent為黑色，則不用調(diào)整while (cur != _root && parent->_col == RED)//保證下一次循環(huán)parent不為空{Node* Gparent = parent->_parent;if (parent == Gparent->_left){//判斷叔叔節(jié)點(diǎn)的顏色//叔叔節(jié)點(diǎn)為RED//叔叔節(jié)點(diǎn)為BLACK或者不存在Node* uncle = Gparent->_right;if (uncle && uncle->_col == RED)//叔叔節(jié)點(diǎn)為RED{uncle->_col = parent->_col = BLACK;Gparent->_col = RED;// Gparent 可能為子樹(shù)，保證黑色節(jié)點(diǎn)數(shù)量不變//繼續(xù)向上調(diào)整cur = Gparent;parent = cur->_parent;}else//叔叔節(jié)點(diǎn)為BLACK或者不存在{if (cur == parent->_right){RotateL(parent);swap(parent, cur);//保證parent指針?biāo)赶虻奈恢貌蛔?/span>}RotateR(Gparent);//保證左右子樹(shù)的黑色節(jié)點(diǎn)數(shù)量不變parent->_col = BLACK;Gparent->_col = RED;//繼續(xù)向上調(diào)整cur = parent;parent = cur->_parent;}}else{Node* uncle = Gparent->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;Gparent->_col = RED;cur = Gparent;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(parent);swap(parent, cur);}RotateL(Gparent);parent->_col = BLACK;Gparent->_col = RED;cur = parent;parent = cur->_parent;}}}_root->_col = BLACK;return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsRBTree(){if (_root == NULL){return true;}if (_root->_col == RED){return false;}Node* cur = _root;size_t count = 0;while (cur){if (cur->_col == BLACK)count++;cur = cur->_left;}size_t k = 0;return _IsRBTree(_root, count, k++);} protected: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){if (ppNode->_left == parent)ppNode->_left = SubR;elseppNode->_right = SubR;SubR->_parent = ppNode;}else{SubR->_parent = NULL;_root = 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){if (ppNode->_left == parent)ppNode->_left = SubL;elseppNode->_right = SubL;SubL->_parent = ppNode;}else{SubL->_parent = NULL;_root = SubL;}}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}bool _IsRBTree(Node* root, const size_t& count, size_t k){if (root == NULL){return count == k;}Node * parent = root->_parent;if (parent && parent->_col == RED && root->_col == RED){return false;}if (root->_col == BLACK){k++;}return _IsRBTree(root->_left, count, k) && _IsRBTree(root->_right, count, k);} protected:Node* _root; };void TestRBTree() {RBTree<int, int> tree;int a[9] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };for (int i = 0; i < 9; i++){tree.Insert(a[i], i);cout << tree.IsRBTree() <<"->"<<a[i]<< endl;}tree.InOrder();cout << tree.IsRBTree() << endl; }test.cpp
#include"RBTree.h"int main() {TestRBTree();system("pause");return 0; }總結(jié)
- 上一篇： 进程组 会话 作业
- 下一篇： crond和crontab