情況一: cur為紅，p為紅，g為黑，u存在且為紅?

?

解決方式：將p,u改為黑, g改為紅, 然后把g當(dāng)成cur, 繼續(xù)向上調(diào)整。?

??

??

可以看到叔叔為紅的這種情況下只需要調(diào)整顏色就能又滿足規(guī)則.

可以簡(jiǎn)單討論一下子樹路徑黑結(jié)點(diǎn)和為1和2時(shí)候共有幾種情況:?

當(dāng)a,b,c,d,e都是0的時(shí)候,有四種情況:

??

當(dāng)a,b,c,d,e都是1的時(shí)候:

?

while (parent && parent->_col == RED)
{Node* grandparent = parent->_parent;//parent在grandparent的左if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}}//如果parent在grandparent的右,邏輯類似else if (parent == grandparent->_right){Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}}_root->_col = BLACK;//不管中間調(diào)了多少次,最后的根一定是黑,//如果被調(diào)整到根變紅了,需要調(diào)為黑,如果沒調(diào)到,重新賦值一遍也沒有影響
}

parent顏色為黑不需要單獨(dú)去判斷, 因?yàn)楸緛砭筒恍枰魏尾僮? 根本不會(huì)進(jìn)入循環(huán).

情況二: ?cur為紅，p為紅，g為黑，u不存在/u存在且為黑

??

說明: u的情況有兩種

1.如果u節(jié)點(diǎn)不存在, 則cur一定是新插入節(jié)點(diǎn), 因?yàn)榇藭r(shí)c,a,b,d,e都是空, 因?yàn)橐獫M足一個(gè)路徑的黑色結(jié)點(diǎn)個(gè)數(shù)相同.

?

2.如果u節(jié)點(diǎn)存在, 則其一定是黑色的, 那么cur節(jié)點(diǎn)原來的顏色一定是黑色的, 上面看到其是紅色的原因是因?yàn)閏ur的子樹在調(diào)整的過程中將cur節(jié)點(diǎn)的顏色由黑色改成紅色。

?

在這里又可以再細(xì)分為兩種子情況:

1. p為g的左孩子,cur為p的左孩子(左左)和p為g的右孩子, cur為p的右孩子(右右).

2.? p為g的左孩子,cur為p的右孩子(左右)和p為g的右孩子, cur為p的左孩子(右左).

1.左左和右右?

那對(duì)于這種情況我們要進(jìn)行的單旋轉(zhuǎn)+變色.

旋轉(zhuǎn):?

為什么要旋轉(zhuǎn)？

因?yàn)檫@種情況的話最長(zhǎng)路徑有可能已經(jīng)超過最短路徑的兩倍了, 比如上面這個(gè)圖如果如果d/e是空的話就已經(jīng)超過了, 所以要先旋轉(zhuǎn)降高度, 再去調(diào)整顏色使它符合紅黑樹.

進(jìn)行什么旋轉(zhuǎn)呢？

那就要看具體情況了, 其實(shí)還是我們AVL樹那里的四種情況:

當(dāng)前我們是 p為g的左孩子, cur為p的左孩子, 是在較高左子樹的左側(cè)插入(左左), 所以要進(jìn)行的旋轉(zhuǎn)是右單旋;

同理p為g的右孩子, cur為p的右孩子,是在較高右子樹的右側(cè)插入(右右),進(jìn)行左單旋.

變色:

變色的話不論那種旋轉(zhuǎn)是統(tǒng)一的:p、g變色–p變黑，g變紅

?

為什么不直接把cur變黑呢?

這樣也滿足路徑黑結(jié)點(diǎn)和保持不變啊:?

??

此時(shí)parent的顏色又變成了紅色, 又需要再繼續(xù)向上調(diào)整, 而一開始的方法中parent調(diào)整完就是黑的, 就結(jié)束了, 不需要再向上調(diào)整, 更簡(jiǎn)便!

代碼:?

while (parent && parent->_col == RED)
{Node* grandparent = parent->_parent;//parent在grandparent的左if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_left){rotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}}}//parent在grandparent的左else if (parent == grandparent->_right){Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){rotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}}}_root->_col = BLACK;
}

這里的旋轉(zhuǎn)復(fù)用AVL的旋轉(zhuǎn)即可, 去掉更新平衡因子的部分.?

2.左右和右左

雙旋+變色?

前提條件根上面一樣，還是cur為紅，p為紅，g為黑，u不存在/u存在且為黑?

''

進(jìn)行什么旋轉(zhuǎn)呢？?

1.p為g的左孩子，cur為p的右孩子，則針對(duì)p做左單旋, g作右單旋
2.相反，p為g的右孩子，cur為p的左孩子，則針對(duì)p做右單旋, g作左單旋.

以左右單旋圖中為例, 先進(jìn)行一個(gè)左單旋:?

再進(jìn)行一個(gè)右單旋:?

?再變色:

這樣就調(diào)整好了?

代碼:?

while (parent && parent->_col == RED)
{Node* grandparent = parent->_parent;//parent在grandparent的左if (parent == grandparent->_left){Node* uncle = grandparent->_right;//叔叔存在且為紅直接變色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//叔叔不存在或者叔叔是黑進(jìn)行旋轉(zhuǎn)else{/右單旋if (cur == parent->_left){rotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//左右雙旋else if (cur == parent->_right){rotateL(parent);rotateR(grandparent);grandparent->_col = RED;cur->_col = BLACK;}}}//parent在grandparent的左else if (parent == grandparent->_right){//叔叔存在且為紅直接變色Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//叔叔不存在或者叔叔是黑進(jìn)行旋轉(zhuǎn)else{//左單旋if (cur == parent->_right){rotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//右左雙旋else if (cur == parent->_left){rotateR(parent);rotateL(grandparent);grandparent->_col = RED;cur->_col = BLACK;}}}_root->_col = BLACK;
}

紅黑樹的測(cè)試

驗(yàn)證其為搜索二叉樹

首先我們還是先來驗(yàn)證他是否是二叉搜索樹，看它中序是否有序就行了:

void InOrderPrint()
{_InOrder(_root);
}void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);
}

int main()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrderPrint();cout << endl;return 0;
}

順序是正確的

?驗(yàn)證其是否平衡且滿足紅黑樹性質(zhì)

如何判斷它是否滿足是一棵紅黑樹呢？

其實(shí)就是去檢查那幾條規(guī)則（性質(zhì)）:

1.首先結(jié)點(diǎn)顏色要么是黑色, 要么是紅色, 這沒什么好檢查的。
2.然后根結(jié)點(diǎn)必須是黑色,?這個(gè)可以檢查一下,如果根結(jié)點(diǎn)不是黑色（是紅色）直接就不符合了

3.然后如果出現(xiàn)連續(xù)的紅色結(jié)點(diǎn), 那也不符合。
那怎么檢查有沒有出現(xiàn)連續(xù)紅色結(jié)點(diǎn)呢？
我們可以去遍歷這棵樹, 然后遇到紅色結(jié)點(diǎn)判斷它的孩子是不是紅色結(jié)點(diǎn), 如果存在紅色結(jié)點(diǎn)它的孩子也是紅色, 那就不符合, 這樣可以,但是不太好, 因?yàn)楹⒆拥脑捯獧z查兩個(gè),而且結(jié)點(diǎn)的孩子有還有可能不存在, 為空, 那還得再加一個(gè)判斷。
所以我們可以這樣做: 遍歷遇到紅色結(jié)點(diǎn)我們?nèi)タ此母赣H, 如果它的父親也為紅色那就不行。而判斷父親的話, 只有根結(jié)點(diǎn)沒有父親, 但是根結(jié)點(diǎn)是黑色的也不會(huì)去檢查它。

bool IsBalance()
{if (_root == nullptr)return true;if (_root->_col == RED)return false;return _Check(_root);
}bool _Check(Node* root)
{if (root == nullptr){return true;}if (root->_col == RED && root->_parent->_col == RED)return false;return _Check(root->_left, blacknum, ref)&& _Check(root->_right, blacknum, ref);
}

然后還剩一個(gè), 我們要檢查每條路徑黑色結(jié)點(diǎn)數(shù)量是否相等,?存在不相等的情況就不符合。
那這個(gè)要如何檢查呢？
我們可以先求出一條路徑的黑色結(jié)點(diǎn)數(shù)量, 把它作為基準(zhǔn)值, 然后再遞歸求出每條路徑的黑色結(jié)點(diǎn)數(shù)量和它比較, 如果存在不相等的情況, 就不符合, 不用管這個(gè)基準(zhǔn)值是不是正確的, 只要其他路徑和這個(gè)值不相同, 那就不符合.

bool IsBalance()
{if (_root == nullptr)return true;if (_root->_col == RED)return false;//找基準(zhǔn)值,這里以最左路為基準(zhǔn)Node* cur = _root;int ref = 0;while (cur){if (cur->_col == BLACK){ref++;}cur = cur->_left;}//定義一個(gè)blacknum來記錄路徑的黑色結(jié)點(diǎn)數(shù)目int blacknum = 0;return _Check(_root, blacknum,ref);
}bool _Check(Node* root,int blacknum, const int ref)
{if (root == nullptr){//root為空說明該路徑已經(jīng)找完,開始比較blacknum和ref,不相等就不符合if (blacknum != ref)return false;return true;}//如果節(jié)點(diǎn)是黑的blacknum就++if (root->_col == BLACK)blacknum++;//結(jié)點(diǎn)是紅色判斷它與父親結(jié)點(diǎn)是否為連續(xù)的紅if (root->_col == RED && root->_parent->_col == RED)return false;//繼續(xù)判斷左右子樹return _Check(root->_left, blacknum, ref)&& _Check(root->_right, blacknum, ref);
}

?注意這里的blacknum傳遞的非常巧妙, 因?yàn)槊恳粚拥腷lacknum都是獨(dú)立的, 所以向下一層傳遞blacknum的后blacknum的修改不會(huì)影響上一層, 為什么不想去影響上一層呢? 因?yàn)樯弦粚拥腷lacknum傳遞給了左子樹后還要傳遞給右子樹進(jìn)行判斷, 在左子樹中修改了上一層的值那再傳給右子樹就一定錯(cuò)了.

大量隨機(jī)數(shù)構(gòu)建紅黑樹進(jìn)行測(cè)試?

int main()
{const int N = 10000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert_time:" << end2 - begin2 << endl;cout << t.IsBalance() << endl;return 0;
}

?

插入和查找的時(shí)間測(cè)試:?

Node* Find(const pair<K, V>& kv)
{Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){cur = cur->_right;}else if (kv.first < cur->_kv.first){cur = cur->_left;}else{return cur;}}return nullptr;
}

int main()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();size_t begin1 = clock();for (auto e : v){t.Find(make_pair(e,e));}size_t end1 = clock();cout << "Find_time:" << end1 - begin1 << endl;cout << "Insert_time:" << end2 - begin2 << endl;cout << "是否平衡:"<<t.IsBalance() << endl;return 0;
}

?

插入相同數(shù)量隨機(jī)數(shù)比較AVL樹和紅黑樹的高度?

void test3()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand()+i);}RBTree<int, int> rbt;AVLTree<int, int> avlt;for (auto e : v){rbt.Insert(make_pair(e, e));avlt.Insert(make_pair(e, e));}cout << "插入了" << rbt.Size() << "個(gè)值" << endl;cout << "紅黑樹高度: " << rbt.Height()<<endl;cout << "AVL樹高度: " << avlt.Height() << endl;}

當(dāng)N為10w:?

插入10萬個(gè)數(shù)據(jù), 對(duì)產(chǎn)生的隨機(jī)數(shù)都加個(gè)i(減少重復(fù)值), 我們看到就有一些差異了?

當(dāng)N為100w:

?

100w個(gè)數(shù)據(jù)的差異就更大了, 還是紅黑樹要高一點(diǎn)

可以發(fā)現(xiàn)AVL樹對(duì)平衡的控制是比較嚴(yán)格的, 而紅黑樹是相對(duì)寬松的。?

紅黑樹的刪除

簡(jiǎn)單分析:

刪除節(jié)點(diǎn)一定都在最后一到兩層, 因?yàn)樯蠈佣伎梢蕴娲氯?

結(jié)點(diǎn)有紅色節(jié)點(diǎn)和黑色節(jié)點(diǎn), 我們就以刪除節(jié)點(diǎn)的顏色來區(qū)分刪除操作的所有情況

刪除紅色節(jié)點(diǎn)

如果刪除的節(jié)點(diǎn)是紅色直接刪除, 不用作任何調(diào)整。因?yàn)閯h除最后一層的紅色節(jié)點(diǎn), 并沒有影響紅黑樹的任何性質(zhì)。

刪除黑色節(jié)點(diǎn)

有3種情況：

1. 擁有 2 個(gè)紅色子節(jié)點(diǎn)的黑色節(jié)點(diǎn)

不可能被直接刪除，因?yàn)闀?huì)找它的子節(jié)點(diǎn)替代刪除，因此不用考慮這種情況

2. 擁有 1 個(gè)紅色子節(jié)點(diǎn)的黑色節(jié)點(diǎn)

修復(fù)步驟總結(jié)：

1. 用刪除節(jié)點(diǎn)的唯一子節(jié)點(diǎn)對(duì)其進(jìn)行替代
2. 將替代節(jié)點(diǎn)染成黑色

3. 黑色葉子節(jié)點(diǎn)

1.?刪除節(jié)點(diǎn)為根節(jié)點(diǎn),?直接刪除該節(jié)點(diǎn), 無需做其他操作。

2. 刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑色?

2.1兄弟節(jié)點(diǎn)至少有1個(gè)紅色子節(jié)點(diǎn)

? ? ? ? 2.1.1?兄弟節(jié)點(diǎn)有一個(gè)右子節(jié)點(diǎn)：

? ? ? ? 2.1.2 兄弟節(jié)點(diǎn)有一個(gè)左子節(jié)點(diǎn)：

? ? ? ? 2.1.3?兄弟節(jié)點(diǎn)有兩個(gè)左右子節(jié)點(diǎn)：

修復(fù)步驟總結(jié)：

? ? ? ? 1 進(jìn)行旋轉(zhuǎn)操作

? ? ? ? 2 旋轉(zhuǎn)之后的中心節(jié)點(diǎn)繼承父節(jié)點(diǎn)（刪除節(jié)點(diǎn)的父節(jié)點(diǎn)）的顏色

? ? ? ? 3 旋轉(zhuǎn)之后的左右節(jié)點(diǎn)染為黑色

2.2?兄弟節(jié)點(diǎn)沒有紅色子節(jié)點(diǎn)

? ? ? ? 2.2.1父節(jié)點(diǎn)為紅色

? ? ? ? 2.2.2父節(jié)點(diǎn)為黑色

修復(fù)步驟總結(jié)：

1. 父節(jié)點(diǎn)向下與兄弟節(jié)點(diǎn)進(jìn)行合并
2. 將兄弟染成紅色、父節(jié)點(diǎn)染成黑色即可修復(fù)紅黑樹性質(zhì)
   • 如果父節(jié)點(diǎn)是黑色，直接將父節(jié)點(diǎn)當(dāng)成被刪除的節(jié)點(diǎn)處理，來修復(fù)父節(jié)點(diǎn)的下溢情況

3.?刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色? ??

修復(fù)步驟總結(jié)：

1. 兄弟節(jié)點(diǎn)染成 BLACK, 父節(jié)點(diǎn)染成染成 RED, 對(duì)父節(jié)點(diǎn)進(jìn)行右旋
2. 于是又回到兄弟節(jié)點(diǎn)是黑色的情況（侄子節(jié)點(diǎn)變?yōu)樾值芄?jié)點(diǎn)），繼續(xù)使用兄弟節(jié)點(diǎn)為黑色的方法進(jìn)行修復(fù)

?具體可查看:

【精選】【數(shù)據(jù)結(jié)構(gòu)】史上最好理解的紅黑樹講解，讓你徹底搞懂紅黑樹_小七mod的博客-CSDN博客

完整代碼:

#pragma once
#include<assert.h>
enum COLOR
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K,V>* _parent;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _left;pair<K,V> _kv;COLOR _col;RBTreeNode(const pair<K,V>& kv): _parent(nullptr), _right(nullptr), _left(nullptr), _kv(kv), _col(RED){}};template<class K,class V>
class RBTree
{typedef RBTreeNode<K,V> Node;
public:bool Insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col= BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);//cur->_col = RED;if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}elseassert(false);//插入完成, 調(diào)整顏色parent的顏色是黑,不需要調(diào)整//if (parent->_col == BLACK)//{//	return true;//}//parent的顏色是紅,需要調(diào)整while (parent && parent->_col == RED){Node* grandparent = parent->_parent;//parent在grandparent的左//		 g			      g//   p	u		   p 	  u//c					  cif (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{//		 g//   p	u//cif (cur == parent->_left){rotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//		 g//   p	u//      celse if (cur == parent->_right){rotateL(parent);rotateR(grandparent);grandparent->_col = RED;cur->_col = BLACK;}}}//parent在grandparent的左//		 g			      g//   u 	p		   u 	  p//				c			celse if (parent == grandparent->_right){Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{//		 g//   u		p//				cif (cur == parent->_right){rotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//		 g//   u		p//      celse if (cur == parent->_left){rotateR(parent);rotateL(grandparent);grandparent->_col = RED;cur->_col = BLACK;}}}_root->_col = BLACK;}return true;}void InOrderPrint(){_InOrder(_root);}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;Node* cur = _root;int ref = 0;while (cur){if (cur->_col == BLACK){ref++;}cur = cur->_left;}int blacknum = 0;return _Check(_root, blacknum,ref);}Node* Find(const pair<K, V>& kv){Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){cur = cur->_right;}else if (kv.first < cur->_kv.first){cur = cur->_left;}else{return cur;}}return nullptr;}int Height(){return _Height(_root);}private:Node* _root = nullptr;bool _Check(Node* root,int blacknum, const int ref){if (root == nullptr){if (blacknum != ref)return false;return true;}if (root->_col == BLACK)blacknum++;if (root->_col == RED && root->_parent->_col == RED)return false;return _Check(root->_left, blacknum, ref)&& _Check(root->_right, blacknum, ref);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}void rotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_right)parentParent->_right = subR;else if (parent == parentParent->_left)parentParent->_left = subR;subR->_parent = parentParent;}}void rotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;subL->_right = parent;parent->_left = subLR;parent->_parent = subL;if (subLR)subLR->_parent = parent;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else if (parentParent->_right == parent){parentParent->_right = subL;}subL->_parent = parentParent;}}
};

?test.cpp:

#include <iostream>
#include <vector>
using namespace std;
#include "RBTree.h"
#include "AVL.h"void test1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrderPrint();cout << endl;cout << t.IsBalance() << endl;
}void test2()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();size_t begin1 = clock();for (auto e : v){t.Find(make_pair(e, e));}size_t end1 = clock();cout << "Find_time:" << end1 - begin1 << endl;cout << "Insert_time:" << end2 - begin2 << endl;cout << "是否平衡:" << t.IsBalance() << endl;
}void test3()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand()+i);}RBTree<int, int> rbt;AVLTree<int, int> avlt;for (auto e : v){rbt.Insert(make_pair(e, e));avlt.Insert(make_pair(e, e));}cout << "紅黑樹高度: " << rbt.Height()<<endl;cout << "AVL樹高度: " << avlt.Height() << endl;}
int main()
{test3();return 0;
}

?