閱讀目錄

• 1. 二叉樹
• 2. 二叉查找樹
• 3. 平衡二叉樹
• 3.1 平衡查找樹之AVL樹
• 3.2 平衡二叉樹之紅黑樹
• 4. B樹
• 5. B+樹
• 6. B*樹
• 7. Trie樹

　　數(shù)據(jù)結(jié)構(gòu)中有很多樹的結(jié)構(gòu)，其中包括二叉樹、二叉搜索樹、2-3樹、紅黑樹等等。本文中對數(shù)據(jù)結(jié)構(gòu)中常見的幾種樹的概念和用途進(jìn)行了匯總，不求嚴(yán)格精準(zhǔn)，但求簡單易懂。

1. 二叉樹

　　二叉樹是數(shù)據(jù)結(jié)構(gòu)中一種重要的數(shù)據(jù)結(jié)構(gòu)，也是樹表家族最為基礎(chǔ)的結(jié)構(gòu)。

　　二叉樹的定義：二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^i-1個結(jié)點；深度為k的二叉樹至多有2^k-1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n₀，度為2的結(jié)點數(shù)為n₂，則n₀=n₂+1。

　　二叉樹的示例：

　　滿二叉樹和完全二叉樹：

　　滿二叉樹：除最后一層無任何子節(jié)點外，每一層上的所有結(jié)點都有兩個子結(jié)點。也可以這樣理解，除葉子結(jié)點外的所有結(jié)點均有兩個子結(jié)點。節(jié)點數(shù)達(dá)到最大值，所有葉子結(jié)點必須在同一層上。

　　滿二叉樹的性質(zhì)：

　　1)?一顆樹深度為h，最大層數(shù)為k，深度與最大層數(shù)相同，k=h;

　　2) 葉子數(shù)為2^h;

　　3) 第k層的結(jié)點數(shù)是：2^k-1;

　　4) 總結(jié)點數(shù)是：2^k-1，且總節(jié)點數(shù)一定是奇數(shù)。

　　完全二叉樹：若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～(h-1)層) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第h層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。

　　注：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，堆是一種完全二叉樹或者近似完全二叉樹，所以效率極高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能優(yōu)化，二叉排序樹的效率也要借助平衡性來提高，而平衡性基于完全二叉樹。

　　二叉樹的性質(zhì)：

　　1) 在非空二叉樹中，第i層的結(jié)點總數(shù)不超過2^i-1, i>=1;

　　2) 深度為h的二叉樹最多有2^h-1個結(jié)點(h>=1)，最少有h個結(jié)點;

3) 對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為N₀，而度數(shù)為2的結(jié)點總數(shù)為N₂，則N₀=N₂+1; 4) 具有n個結(jié)點的完全二叉樹的深度為log₂(n+1); 5)有N個結(jié)點的完全二叉樹各結(jié)點如果用順序方式存儲，則結(jié)點之間有如下關(guān)系： 若I為結(jié)點編號則 如果I>1，則其父結(jié)點的編號為I/2； 如果2I<=N，則其左兒子（即左子樹的根結(jié)點）的編號為2I；若2I>N，則無左兒子； 如果2I+1<=N，則其右兒子的結(jié)點編號為2I+1；若2I+1>N，則無右兒子。 6)給定N個節(jié)點，能構(gòu)成h(N)種不同的二叉樹，其中h(N)為卡特蘭數(shù)的第N項，h(n)=C(2*n, n)/(n+1)。 7)設(shè)有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2ⁱ。

2. 二叉查找樹

二叉查找樹定義：又稱為是二叉排序樹（Binary Sort Tree）或二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 1) 若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值； 2) 若右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值； 3) 左、右子樹也分別為二叉排序樹； 4) 沒有鍵值相等的節(jié)點。 二叉查找樹的性質(zhì)：對二叉查找樹進(jìn)行中序遍歷，即可得到有序的數(shù)列。 　　二叉查找樹的時間復(fù)雜度：它和二分查找一樣，插入和查找的時間復(fù)雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間復(fù)雜度。原因在于插入和刪除元素的時候，樹沒有保持平衡（比如，我們查找上圖（b）中的“93”，我們需要進(jìn)行n次查找操作）。我們追求的是在最壞的情況下仍然有較好的時間復(fù)雜度，這就是平衡查找樹設(shè)計的初衷。 　　二叉查找樹的高度決定了二叉查找樹的查找效率。

　　二叉查找樹的插入過程如下：

　　1) 若當(dāng)前的二叉查找樹為空，則插入的元素為根節(jié)點;

　　2) 若插入的元素值小于根節(jié)點值，則將元素插入到左子樹中;

　　3) 若插入的元素值不小于根節(jié)點值，則將元素插入到右子樹中。

　　二叉查找樹的刪除，分三種情況進(jìn)行處理：

　　1) p為葉子節(jié)點，直接刪除該節(jié)點，再修改其父節(jié)點的指針（注意分是根節(jié)點和不是根節(jié)點），如圖a;

　　2) p為單支節(jié)點（即只有左子樹或右子樹）。讓p的子樹與p的父親節(jié)點相連，刪除p即可（注意分是根節(jié)點和不是根節(jié)點），如圖b;

　　3) p的左子樹和右子樹均不空。找到p的后繼y，因為y一定沒有左子樹，所以可以刪除y，并讓y的父親節(jié)點成為y的右子樹的父親節(jié)點，并用y的值代替p的值；或者方法二是找到p的前驅(qū)x，x一定沒有右子樹，所以可以刪除x，并讓x的父親節(jié)點成為y的左子樹的父親節(jié)點。如圖c。

　　二叉樹相關(guān)實現(xiàn)源碼：

　　插入操作：

struct node {int val;pnode lchild;pnode rchild; };pnode BT = NULL;//遞歸方法插入節(jié)點 pnode insert(pnode root, int x) {pnode p = (pnode)malloc(LEN);p->val = x;p->lchild = NULL;p->rchild = NULL;if(root == NULL){root = p; } else if(x < root->val){root->lchild = insert(root->lchild, x); }else{root->rchild = insert(root->rchild, x); }return root; }//非遞歸方法插入節(jié)點 void insert_BST(pnode q, int x) {pnode p = (pnode)malloc(LEN);p->val = x;p->lchild = NULL;p->rchild = NULL;if(q == NULL){BT = p;return ; } while(q->lchild != p && q->rchild != p){if(x < q->val){if(q->lchild){q = q->lchild; } else{q->lchild = p;} } else{if(q->rchild){q = q->rchild; } else{q->rchild = p; }}}return; }

?

?

　　刪除操作：

bool delete_BST(pnode p, int x) //返回一個標(biāo)志，表示是否找到被刪元素 {bool find = false;pnode q;p = BT;while(p && !find){ //尋找被刪元素 if(x == p->val){ //找到被刪元素 find = true; } else if(x < p->val){ //沿左子樹找 q = p;p = p->lchild; }else{ //沿右子樹找 q = p;p = p->rchild; }}if(p == NULL){ //沒找到 cout << "沒有找到" << x << endl; }if(p->lchild == NULL && p->rchild == NULL){ //p為葉子節(jié)點 if(p == BT){ //p為根節(jié)點 BT = NULL; }else if(q->lchild == p){ q->lchild = NULL;} else{q->rchild = NULL; }free(p); //釋放節(jié)點p }else if(p->lchild == NULL || p->rchild == NULL){ //p為單支子樹 if(p == BT){ //p為根節(jié)點 if(p->lchild == NULL){BT = p->rchild; } else{BT = p->lchild; }} else{if(q->lchild == p && p->lchild){ //p是q的左子樹且p有左子樹 q->lchild = p->lchild; //將p的左子樹鏈接到q的左指針上 } else if(q->lchild == p && p->rchild){q->lchild = p->rchild; }else if(q->rchild == p && p->lchild){q->rchild = p->lchild; }else{q->rchild = p->rchild;}}free(p);}else{ //p的左右子樹均不為空 pnode t = p;pnode s = p->lchild; //從p的左子節(jié)點開始 while(s->rchild){ //找到p的前驅(qū)，即p左子樹中值最大的節(jié)點 t = s; s = s->rchild; }p->val = s->val; //把節(jié)點s的值賦給p if(t == p){p->lchild = s->lchild; } else{t->rchild = s->lchild; }free(s); }return find; }

?

　　查找操作：

pnode search_BST(pnode p, int x) {bool solve = false;while(p && !solve){if(x == p->val){solve = true; } else if(x < p->val){p = p->lchild; }else{p = p->rchild; }}if(p == NULL){cout << "沒有找到" << x << endl; } return p; }

3. 平衡二叉樹

　　我們知道，對于一般的二叉搜索樹（Binary Search Tree），其期望高度（即為一棵平衡樹時）為log₂n，其各操作的時間復(fù)雜度O(log₂n)同時也由此而決定。但是，在某些極端的情況下（如在插入的序列是有序的時），二叉搜索樹將退化成近似鏈或鏈，此時，其操作的時間復(fù)雜度將退化成線性的，即O(n)。我們可以通過隨機(jī)化建立二叉搜索樹來盡量的避免這種情況，但是在進(jìn)行了多次的操作之后，由于在刪除時，我們總是選擇將待刪除節(jié)點的后繼代替它本身，這樣就會造成總是右邊的節(jié)點數(shù)目減少，以至于樹向左偏沉。這同時也會造成樹的平衡性受到破壞，提高它的操作的時間復(fù)雜度。于是就有了我們下邊介紹的平衡二叉樹。

　　平衡二叉樹定義：平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用算法有紅黑樹、AVL樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O(log₂n)，大大降低了操作的時間復(fù)雜度。

　　最小二叉平衡樹的節(jié)點的公式如下：

　　F(n)=F(n-1)+F(n-2)+1

　　這個類似于一個遞歸的數(shù)列，可以參考Fibonacci數(shù)列，1是根節(jié)點，F(n-1)是左子樹的節(jié)點數(shù)量，F(n-2)是右子樹的節(jié)點數(shù)量。

3.1 平衡查找樹之AVL樹

　　有關(guān)AVL樹的具體實現(xiàn)，可以參考C小加的博客《一步一步寫平衡二叉樹（AVL）》。

　　AVL樹定義：AVL樹是最先發(fā)明的自平衡二叉查找樹。AVL樹得名于它的發(fā)明者 G.M. Adelson-Velsky 和 E.M. Landis，他們在 1962 年的論文 "An algorithm for the organization of information" 中發(fā)表了它。在AVL中任何節(jié)點的兩個兒子子樹的高度最大差別為1，所以它也被稱為高度平衡樹，n個結(jié)點的AVL樹最大深度約1.44log₂n。查找、插入和刪除在平均和最壞情況下都是O(logn)。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時間復(fù)雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉(zhuǎn)會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩(wěn)定了很多。

　　AVL樹的自平衡操作——旋轉(zhuǎn)：

　　AVL樹最關(guān)鍵的也是最難的一步操作就是旋轉(zhuǎn)。旋轉(zhuǎn)主要是為了實現(xiàn)AVL樹在實施了插入和刪除操作以后，樹重新回到平衡的方法。下面我們重點研究一下AVL樹的旋轉(zhuǎn)。

　　對于一個平衡的節(jié)點，由于任意節(jié)點最多有兩個兒子，因此高度不平衡時，此節(jié)點的兩顆子樹的高度差2.容易看出，這種不平衡出現(xiàn)在下面四種情況：

　　1) 6節(jié)點的左子樹3節(jié)點高度比右子樹7節(jié)點大2，左子樹3節(jié)點的左子樹1節(jié)點高度大于右子樹4節(jié)點，這種情況成為左左。

　　2) 6節(jié)點的左子樹2節(jié)點高度比右子樹7節(jié)點大2，左子樹2節(jié)點的左子樹1節(jié)點高度小于右子樹4節(jié)點，這種情況成為左右。

　　3) 2節(jié)點的左子樹1節(jié)點高度比右子樹5節(jié)點小2，右子樹5節(jié)點的左子樹3節(jié)點高度大于右子樹6節(jié)點，這種情況成為右左。

　　4) 2節(jié)點的左子樹1節(jié)點高度比右子樹4節(jié)點小2，右子樹4節(jié)點的左子樹3節(jié)點高度小于右子樹6節(jié)點，這種情況成為右右。

　　從圖2中可以可以看出，1和4兩種情況是對稱的，這兩種情況的旋轉(zhuǎn)算法是一致的，只需要經(jīng)過一次旋轉(zhuǎn)就可以達(dá)到目標(biāo)，我們稱之為單旋轉(zhuǎn)。2和3兩種情況也是對稱的，這兩種情況的旋轉(zhuǎn)算法也是一致的，需要進(jìn)行兩次旋轉(zhuǎn)，我們稱之為雙旋轉(zhuǎn)。

　　單旋轉(zhuǎn)

　　單旋轉(zhuǎn)是針對于左左和右右這兩種情況的解決方案，這兩種情況是對稱的，只要解決了左左這種情況，右右就很好辦了。圖3是左左情況的解決方案，節(jié)點k2不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的左子樹X子樹，所以屬于左左情況。

　　為使樹恢復(fù)平衡，我們把k2變成這棵樹的根節(jié)點，因為k2大于k1，把k2置于k1的右子樹上，而原本在k1右子樹的Y大于k1，小于k2，就把Y置于k2的左子樹上，這樣既滿足了二叉查找樹的性質(zhì)，又滿足了平衡二叉樹的性質(zhì)。

　　這樣的操作只需要一部分指針改變，結(jié)果我們得到另外一顆二叉查找樹，它是一棵AVL樹，因為X向上一移動了一層，Y還停留在原來的層面上，Z向下移動了一層。整棵樹的新高度和之前沒有在左子樹上插入的高度相同，插入操作使得X高度長高了。因此，由于這顆子樹高度沒有變化，所以通往根節(jié)點的路徑就不需要繼續(xù)旋轉(zhuǎn)了。

　　雙旋轉(zhuǎn)

　　對于左右和右左這兩種情況，單旋轉(zhuǎn)不能使它達(dá)到一個平衡狀態(tài)，要經(jīng)過兩次旋轉(zhuǎn)。雙旋轉(zhuǎn)是針對于這兩種情況的解決方案，同樣的，這樣兩種情況也是對稱的，只要解決了左右這種情況，右左就很好辦了。圖4是左右情況的解決方案，節(jié)點k3不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的右子樹k2子樹，所以屬于左右情況。

?

?

?　　為使樹恢復(fù)平衡，我們需要進(jìn)行兩步，第一步，把k1作為根，進(jìn)行一次右右旋轉(zhuǎn)，旋轉(zhuǎn)之后就變成了左左情況，所以第二步再進(jìn)行一次左左旋轉(zhuǎn)，最后得到了一棵以k2為根的平衡二叉樹。

　　AVL樹實現(xiàn)源碼：

//AVL樹節(jié)點信息 template<class T> class TreeNode {public:TreeNode():lson(NULL),rson(NULL),freq(1),hgt(0){}T data;//值int hgt;//高度unsigned int freq;//頻率TreeNode* lson;//指向左兒子的地址TreeNode* rson;//指向右兒子的地址 }; //AVL樹類的屬性和方法聲明 template<class T> class AVLTree {private:TreeNode<T>* root;//根節(jié)點void insertpri(TreeNode<T>* &node,T x);//插入TreeNode<T>* findpri(TreeNode<T>* node,T x);//查找void insubtree(TreeNode<T>* node);//中序遍歷void Deletepri(TreeNode<T>* &node,T x);//刪除int height(TreeNode<T>* node);//求樹的高度void SingRotateLeft(TreeNode<T>* &k2);//左左情況下的旋轉(zhuǎn)void SingRotateRight(TreeNode<T>* &k2);//右右情況下的旋轉(zhuǎn)void DoubleRotateLR(TreeNode<T>* &k3);//左右情況下的旋轉(zhuǎn)void DoubleRotateRL(TreeNode<T>* &k3);//右左情況下的旋轉(zhuǎn)int Max(int cmpa,int cmpb);//求最大值public:AVLTree():root(NULL){}void insert(T x);//插入接口TreeNode<T>* find(T x);//查找接口void Delete(T x);//刪除接口void traversal();//遍歷接口 }; //計算節(jié)點的高度 template<class T> int AVLTree<T>::height(TreeNode<T>* node) {if(node!=NULL)return node->hgt;return -1; } //求最大值 template<class T> int AVLTree<T>::Max(int cmpa,int cmpb) {return cmpa>cmpb?cmpa:cmpb; } //左左情況下的旋轉(zhuǎn) template<class T> void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2) {TreeNode<T>* k1;k1=k2->lson;k2->lson=k1->rson;k1->rson=k2;k2->hgt=Max(height(k2->lson),height(k2->rson))+1;k1->hgt=Max(height(k1->lson),k2->hgt)+1; } //右右情況下的旋轉(zhuǎn) template<class T> void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2) {TreeNode<T>* k1;k1=k2->rson;k2->rson=k1->lson;k1->lson=k2;k2->hgt=Max(height(k2->lson),height(k2->rson))+1;k1->hgt=Max(height(k1->rson),k2->hgt)+1; } //左右情況的旋轉(zhuǎn) template<class T> void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3) {SingRotateRight(k3->lson);SingRotateLeft(k3); } //右左情況的旋轉(zhuǎn) template<class T> void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3) {SingRotateLeft(k3->rson);SingRotateRight(k3); } //插入 template<class T> void AVLTree<T>::insertpri(TreeNode<T>* &node,T x) {if(node==NULL)//如果節(jié)點為空,就在此節(jié)點處加入x信息 {node=new TreeNode<T>();node->data=x;return;}if(node->data>x)//如果x小于節(jié)點的值,就繼續(xù)在節(jié)點的左子樹中插入x {insertpri(node->lson,x);if(2==height(node->lson)-height(node->rson))if(x<node->lson->data)SingRotateLeft(node);elseDoubleRotateLR(node);}else if(node->data<x)//如果x大于節(jié)點的值,就繼續(xù)在節(jié)點的右子樹中插入x {insertpri(node->rson,x);if(2==height(node->rson)-height(node->lson))//如果高度之差為2的話就失去了平衡,需要旋轉(zhuǎn)if(x>node->rson->data)SingRotateRight(node);elseDoubleRotateRL(node);}else ++(node->freq);//如果相等,就把頻率加1node->hgt=Max(height(node->lson),height(node->rson)); } //插入接口 template<class T> void AVLTree<T>::insert(T x) {insertpri(root,x); } //查找 template<class T> TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node,T x) {if(node==NULL)//如果節(jié)點為空說明沒找到,返回NULL {return NULL;}if(node->data>x)//如果x小于節(jié)點的值,就繼續(xù)在節(jié)點的左子樹中查找x {return findpri(node->lson,x);}else if(node->data<x)//如果x大于節(jié)點的值,就繼續(xù)在節(jié)點的左子樹中查找x {return findpri(node->rson,x);}else return node;//如果相等,就找到了此節(jié)點 } //查找接口 template<class T> TreeNode<T>* AVLTree<T>::find(T x) {return findpri(root,x); } //刪除 template<class T> void AVLTree<T>::Deletepri(TreeNode<T>* &node,T x) {if(node==NULL) return ;//沒有找到值是x的節(jié)點if(x < node->data){Deletepri(node->lson,x);//如果x小于節(jié)點的值,就繼續(xù)在節(jié)點的左子樹中刪除xif(2==height(node->rson)-height(node->lson))if(node->rson->lson!=NULL&&(height(node->rson->lson)>height(node->rson->rson)) )DoubleRotateRL(node);elseSingRotateRight(node);}else if(x > node->data){Deletepri(node->rson,x);//如果x大于節(jié)點的值,就繼續(xù)在節(jié)點的右子樹中刪除xif(2==height(node->lson)-height(node->rson))if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))DoubleRotateLR(node);elseSingRotateLeft(node);}else//如果相等,此節(jié)點就是要刪除的節(jié)點 {if(node->lson&&node->rson)//此節(jié)點有兩個兒子 {TreeNode<T>* temp=node->rson;//temp指向節(jié)點的右兒子while(temp->lson!=NULL) temp=temp->lson;//找到右子樹中值最小的節(jié)點//把右子樹中最小節(jié)點的值賦值給本節(jié)點node->data=temp->data;node->freq=temp->freq;Deletepri(node->rson,temp->data);//刪除右子樹中最小值的節(jié)點if(2==height(node->lson)-height(node->rson)){if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))DoubleRotateLR(node);elseSingRotateLeft(node);}}else//此節(jié)點有1個或0個兒子 {TreeNode<T>* temp=node;if(node->lson==NULL)//有右兒子或者沒有兒子node=node->rson;else if(node->rson==NULL)//有左兒子node=node->lson;delete(temp);temp=NULL;}}if(node==NULL) return;node->hgt=Max(height(node->lson),height(node->rson))+1;return; } //刪除接口 template<class T> void AVLTree<T>::Delete(T x) {Deletepri(root,x); } //中序遍歷函數(shù) template<class T> void AVLTree<T>::insubtree(TreeNode<T>* node) {if(node==NULL) return;insubtree(node->lson);//先遍歷左子樹cout<<node->data<<" ";//輸出根節(jié)點insubtree(node->rson);//再遍歷右子樹 } //中序遍歷接口 template<class T> void AVLTree<T>::traversal() {insubtree(root); }

?

3.2 平衡二叉樹之紅黑樹

　　紅黑樹的定義：紅黑樹是一種自平衡二叉查找樹，是在計算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由魯?shù)婪颉へ悹柊l(fā)明的，稱之為"對稱二叉B樹"，它現(xiàn)代的名字是在 Leo J. Guibas 和?Robert Sedgewick?于1978年寫的一篇論文中獲得的。它是復(fù)雜的，但它的操作有著良好的最壞情況運(yùn)行時間，并且在實踐中是高效的: 它可以在O(logn)時間內(nèi)做查找，插入和刪除，這里的n是樹中元素的數(shù)目。

　　紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔(dān)保。這不只是使它們在時間敏感的應(yīng)用如實時應(yīng)用（real time application）中有價值，而且使它們有在提供最壞情況擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中作為建造板塊的價值；例如，在計算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)都可以基于紅黑樹。此外，紅黑樹還是2-3-4樹的一種等同，它們的思想是一樣的，只不過紅黑樹是2-3-4樹用二叉樹的形式表示的。

　　紅黑樹的性質(zhì)：

　　紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強(qiáng)制的一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

　　性質(zhì)1. 節(jié)點是紅色或黑色。

　　性質(zhì)2. 根是黑色。

　　性質(zhì)3. 所有葉子都是黑色（葉子是NIL節(jié)點）。

　　性質(zhì)4. 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。)

　　性質(zhì)5. 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。

　　下面是一個具體的紅黑樹的圖例：

　　這些約束確保了紅黑樹的關(guān)鍵特性: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。

　　要知道為什么這些性質(zhì)確保了這個結(jié)果，注意到性質(zhì)4導(dǎo)致了路徑不能有兩個毗連的紅色節(jié)點就足夠了。最短的可能路徑都是黑色節(jié)點，最長的可能路徑有交替的紅色和黑色節(jié)點。因為根據(jù)性質(zhì)5所有最長的路徑都有相同數(shù)目的黑色節(jié)點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。

　　以下內(nèi)容整理自wiki百科之紅黑樹。

　　紅黑樹的自平衡操作：

　　因為每一個紅黑樹也是一個特化的二叉查找樹，因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同。然而，在紅黑樹上進(jìn)行插入操作和刪除操作會導(dǎo)致不再符合紅黑樹的性質(zhì)。恢復(fù)紅黑樹的性質(zhì)需要少量(O(logn))的顏色變更(實際是非常快速的)和不超過三次樹旋轉(zhuǎn)(對于插入操作是兩次)。雖然插入和刪除很復(fù)雜，但操作時間仍可以保持為O(logn) 次。

　　我們首先以二叉查找樹的方法增加節(jié)點并標(biāo)記它為紅色。如果設(shè)為黑色，就會導(dǎo)致根到葉子的路徑上有一條路上，多一個額外的黑節(jié)點，這個是很難調(diào)整的（違背性質(zhì)5）。但是設(shè)為紅色節(jié)點后，可能會導(dǎo)致出現(xiàn)兩個連續(xù)紅色節(jié)點的沖突，那么可以通過顏色調(diào)換（color flips）和樹旋轉(zhuǎn)來調(diào)整。下面要進(jìn)行什么操作取決于其他臨近節(jié)點的顏色。同人類的家族樹中一樣，我們將使用術(shù)語叔父節(jié)點來指一個節(jié)點的父節(jié)點的兄弟節(jié)點。注意:

• 性質(zhì)1和性質(zhì)3總是保持著。
• 性質(zhì)4只在增加紅色節(jié)點、重繪黑色節(jié)點為紅色，或做旋轉(zhuǎn)時受到威脅。
• 性質(zhì)5只在增加黑色節(jié)點、重繪紅色節(jié)點為黑色，或做旋轉(zhuǎn)時受到威脅。

　　插入操作：

　　假設(shè)，將要插入的節(jié)點標(biāo)為N，N的父節(jié)點標(biāo)為P，N的祖父節(jié)點標(biāo)為G，N的叔父節(jié)點標(biāo)為U。在圖中展示的任何顏色要么是由它所處情形這些所作的假定，要么是假定所暗含的。

　　情形1:?該樹為空樹，直接插入根結(jié)點的位置，違反性質(zhì)1，把節(jié)點顏色有紅改為黑即可。

　　情形2:?插入節(jié)點N的父節(jié)點P為黑色，不違反任何性質(zhì)，無需做任何修改。在這種情形下，樹仍是有效的。性質(zhì)5也未受到威脅，盡管新節(jié)點N有兩個黑色葉子子節(jié)點；但由于新節(jié)點N是紅色，通過它的每個子節(jié)點的路徑就都有同通過它所取代的黑色的葉子的路徑同樣數(shù)目的黑色節(jié)點，所以依然滿足這個性質(zhì)。

　　注：?情形1很簡單，情形2中P為黑色，一切安然無事，但P為紅就不一樣了，下邊是P為紅的各種情況，也是真正難懂的地方。

　　情形3:?如果父節(jié)點P和叔父節(jié)點U二者都是紅色，(此時新插入節(jié)點N做為P的左子節(jié)點或右子節(jié)點都屬于情形3,這里右圖僅顯示N做為P左子的情形)則我們可以將它們兩個重繪為黑色并重繪祖父節(jié)點G為紅色(用來保持性質(zhì)4)。現(xiàn)在我們的新節(jié)點N有了一個黑色的父節(jié)點P。因為通過父節(jié)點P或叔父節(jié)點U的任何路徑都必定通過祖父節(jié)點G，在這些路徑上的黑節(jié)點數(shù)目沒有改變。但是，紅色的祖父節(jié)點G的父節(jié)點也有可能是紅色的，這就違反了性質(zhì)4。為了解決這個問題，我們在祖父節(jié)點G上遞歸地進(jìn)行上述情形的整個過程（把G當(dāng)成是新加入的節(jié)點進(jìn)行各種情形的檢查）。比如，G為根節(jié)點，那我們就直接將G變?yōu)楹谏?#xff08;情形1）；如果G不是根節(jié)點，而它的父節(jié)點為黑色，那符合所有的性質(zhì)，直接插入即可（情形2）；如果G不是根節(jié)點，而它的父節(jié)點為紅色，則遞歸上述過程（情形3）。

?

　　情形4:?父節(jié)點P是紅色而叔父節(jié)點U是黑色或缺少，新節(jié)點N是其父節(jié)點的左子節(jié)點，而父節(jié)點P又是其父節(jié)點G的左子節(jié)點。在這種情形下，我們進(jìn)行針對祖父節(jié)點G的一次右旋轉(zhuǎn); 在旋轉(zhuǎn)產(chǎn)生的樹中，以前的父節(jié)點P現(xiàn)在是新節(jié)點N和以前的祖父節(jié)點G的父節(jié)點。我們知道以前的祖父節(jié)點G是黑色，否則父節(jié)點P就不可能是紅色(如果P和G都是紅色就違反了性質(zhì)4，所以G必須是黑色)。我們切換以前的父節(jié)點P和祖父節(jié)點G的顏色，結(jié)果的樹滿足性質(zhì)4。性質(zhì)5也仍然保持滿足，因為通過這三個節(jié)點中任何一個的所有路徑以前都通過祖父節(jié)點G，現(xiàn)在它們都通過以前的父節(jié)點P。在各自的情形下，這都是三個節(jié)點中唯一的黑色節(jié)點。

　　情形5:?父節(jié)點P是紅色而叔父節(jié)點U是黑色或缺少，并且新節(jié)點N是其父節(jié)點P的右子節(jié)點而父節(jié)點P又是其父節(jié)點的左子節(jié)點。在這種情形下，我們進(jìn)行一次左旋轉(zhuǎn)調(diào)換新節(jié)點和其父節(jié)點的角色; 接著，我們按情形4處理以前的父節(jié)點P以解決仍然失效的性質(zhì)4。注意這個改變會導(dǎo)致某些路徑通過它們以前不通過的新節(jié)點N（比如圖中1號葉子節(jié)點）或不通過節(jié)點P（比如圖中3號葉子節(jié)點），但由于這兩個節(jié)點都是紅色的，所以性質(zhì)5仍有效。

　　注: 插入實際上是原地算法，因為上述所有調(diào)用都使用了尾部遞歸。

　　刪除操作：

　　如果需要刪除的節(jié)點有兩個兒子，那么問題可以被轉(zhuǎn)化成刪除另一個只有一個兒子的節(jié)點的問題。對于二叉查找樹，在刪除帶有兩個非葉子兒子的節(jié)點的時候，我們找到要么在它的左子樹中的最大元素、要么在它的右子樹中的最小元素，并把它的值轉(zhuǎn)移到要刪除的節(jié)點中。我們接著刪除我們從中復(fù)制出值的那個節(jié)點，它必定有少于兩個非葉子的兒子。因為只是復(fù)制了一個值，不違反任何性質(zhì)，這就把問題簡化為如何刪除最多有一個兒子的節(jié)點的問題。它不關(guān)心這個節(jié)點是最初要刪除的節(jié)點還是我們從中復(fù)制出值的那個節(jié)點。

　　我們只需要討論刪除只有一個兒子的節(jié)點(如果它兩個兒子都為空，即均為葉子，我們?nèi)我鈱⑵渲幸粋€看作它的兒子)。如果我們刪除一個紅色節(jié)點（此時該節(jié)點的兒子將都為葉子節(jié)點），它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它，并不會破壞性質(zhì)3和性質(zhì)4。通過被刪除節(jié)點的所有路徑只是少了一個紅色節(jié)點，這樣可以繼續(xù)保證性質(zhì)5。另一種簡單情況是在被刪除節(jié)點是黑色而它的兒子是紅色的時候。如果只是去除這個黑色節(jié)點，用它的紅色兒子頂替上來的話，會破壞性質(zhì)5，但是如果我們重繪它的兒子為黑色，則曾經(jīng)通過它的所有路徑將通過它的黑色兒子，這樣可以繼續(xù)保持性質(zhì)5。

　　需要進(jìn)一步討論的是在要刪除的節(jié)點和它的兒子二者都是黑色的時候，這是一種復(fù)雜的情況。我們首先把要刪除的節(jié)點替換為它的兒子。出于方便，稱呼這個兒子為N(在新的位置上)，稱呼它的兄弟(它父親的另一個兒子)為S。在下面的示意圖中，我們還是使用P稱呼N的父親，S_L稱呼S的左兒子，S_R稱呼S的右兒子。

　　如果N和它初始的父親是黑色，則刪除它的父親導(dǎo)致通過N的路徑都比不通過它的路徑少了一個黑色節(jié)點。因為這違反了性質(zhì)5，樹需要被重新平衡。有幾種情形需要考慮:

　　情形1:?N是新的根。在這種情形下，我們就做完了。我們從所有路徑去除了一個黑色節(jié)點，而新根是黑色的，所以性質(zhì)都保持著。

　　注意: 在情形2、5和6下，我們假定N是它父親的左兒子。如果它是右兒子，則在這些情形下的左和右應(yīng)當(dāng)對調(diào)。

　　情形2:?S是紅色。在這種情形下我們在N的父親上做左旋轉(zhuǎn)，把紅色兄弟轉(zhuǎn)換成N的祖父，我們接著對調(diào)N的父親和祖父的顏色。完成這兩個操作后，盡管所有路徑上黑色節(jié)點的數(shù)目沒有改變，但現(xiàn)在N有了一個黑色的兄弟和一個紅色的父親（它的新兄弟是黑色因為它是紅色S的一個兒子），所以我們可以接下去按情形4、情形5或情形6來處理。

?

　　情形3:?N的父親、S和S的兒子都是黑色的。在這種情形下，我們簡單的重繪S為紅色。結(jié)果是通過S的所有路徑，它們就是以前不通過N的那些路徑，都少了一個黑色節(jié)點。因為刪除N的初始的父親使通過N的所有路徑少了一個黑色節(jié)點，這使事情都平衡了起來。但是，通過P的所有路徑現(xiàn)在比不通過P的路徑少了一個黑色節(jié)點，所以仍然違反性質(zhì)5。要修正這個問題，我們要從情形1開始，在P上做重新平衡處理。

?

　　情形4:?S和S的兒子都是黑色，但是N的父親是紅色。在這種情形下，我們簡單的交換N的兄弟和父親的顏色。這不影響不通過N的路徑的黑色節(jié)點的數(shù)目，但是它在通過N的路徑上對黑色節(jié)點數(shù)目增加了一，添補(bǔ)了在這些路徑上刪除的黑色節(jié)點。

?

　　情形5:?S是黑色，S的左兒子是紅色，S的右兒子是黑色，而N是它父親的左兒子。在這種情形下我們在S上做右旋轉(zhuǎn)，這樣S的左兒子成為S的父親和N的新兄弟。我們接著交換S和它的新父親的顏色。所有路徑仍有同樣數(shù)目的黑色節(jié)點，但是現(xiàn)在N有了一個黑色兄弟，他的右兒子是紅色的，所以我們進(jìn)入了情形6。N和它的父親都不受這個變換的影響。

　　情形6:?S是黑色，S的右兒子是紅色，而N是它父親的左兒子。在這種情形下我們在N的父親上做左旋轉(zhuǎn)，這樣S成為N的父親（P）和S的右兒子的父親。我們接著交換N的父親和S的顏色，并使S的右兒子為黑色。子樹在它的根上的仍是同樣的顏色，所以性質(zhì)3沒有被違反。但是，N現(xiàn)在增加了一個黑色祖先: 要么N的父親變成黑色，要么它是黑色而S被增加為一個黑色祖父。所以，通過N的路徑都增加了一個黑色節(jié)點。

　　此時，如果一個路徑不通過N，則有兩種可能性:

• 它通過N的新兄弟。那么它以前和現(xiàn)在都必定通過S和N的父親，而它們只是交換了顏色。所以路徑保持了同樣數(shù)目的黑色節(jié)點。
• 它通過N的新叔父，S的右兒子。那么它以前通過S、S的父親和S的右兒子，但是現(xiàn)在只通過S，它被假定為它以前的父親的顏色，和S的右兒子，它被從紅色改變?yōu)楹谏：铣尚Ч沁@個路徑通過了同樣數(shù)目的黑色節(jié)點。

　　在任何情況下，在這些路徑上的黑色節(jié)點數(shù)目都沒有改變。所以我們恢復(fù)了性質(zhì)4。在示意圖中的白色節(jié)點可以是紅色或黑色，但是在變換前后都必須指定相同的顏色。

?

　　紅黑樹實現(xiàn)源碼：

#define BLACK 1 #define RED 0using namespace std;class bst { private:struct Node {int value;bool color;Node *leftTree, *rightTree, *parent;Node() {color = RED;leftTree = NULL;rightTree = NULL;parent = NULL;value = 0;}Node* grandparent() {if (parent == NULL) {return NULL;}return parent->parent;}Node* uncle() {if (grandparent() == NULL) {return NULL;}if (parent == grandparent()->rightTree)return grandparent()->leftTree;elsereturn grandparent()->rightTree;}Node* sibling() {if (parent->leftTree == this)return parent->rightTree;elsereturn parent->leftTree;}};void rotate_right(Node *p) {Node *gp = p->grandparent();Node *fa = p->parent;Node *y = p->rightTree;fa->leftTree = y;if (y != NIL)y->parent = fa;p->rightTree = fa;fa->parent = p;if (root == fa)root = p;p->parent = gp;if (gp != NULL) {if (gp->leftTree == fa)gp->leftTree = p;elsegp->rightTree = p;}}void rotate_left(Node *p) {if (p->parent == NULL) {root = p;return;}Node *gp = p->grandparent();Node *fa = p->parent;Node *y = p->leftTree;fa->rightTree = y;if (y != NIL)y->parent = fa;p->leftTree = fa;fa->parent = p;if (root == fa)root = p;p->parent = gp;if (gp != NULL) {if (gp->leftTree == fa)gp->leftTree = p;elsegp->rightTree = p;}}void inorder(Node *p) {if (p == NIL)return;if (p->leftTree)inorder(p->leftTree);cout << p->value << " ";if (p->rightTree)inorder(p->rightTree);}string outputColor(bool color) {return color ? "BLACK" : "RED";}Node* getSmallestChild(Node *p) {if (p->leftTree == NIL)return p;return getSmallestChild(p->leftTree);}bool delete_child(Node *p, int data) {if (p->value > data) {if (p->leftTree == NIL) {return false;}return delete_child(p->leftTree, data);} else if (p->value < data) {if (p->rightTree == NIL) {return false;}return delete_child(p->rightTree, data);} else if (p->value == data) {if (p->rightTree == NIL) {delete_one_child(p);return true;}Node *smallest = getSmallestChild(p->rightTree);swap(p->value, smallest->value);delete_one_child(smallest);return true;}}void delete_one_child(Node *p) {Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) {p = NULL;root = p;return;}if (p->parent == NULL) {delete p;child->parent = NULL;root = child;root->color = BLACK;return;}if (p->parent->leftTree == p) {p->parent->leftTree = child;} else {p->parent->rightTree = child;}child->parent = p->parent;if (p->color == BLACK) {if (child->color == RED) {child->color = BLACK;} elsedelete_case(child);}delete p;}void delete_case(Node *p) {if (p->parent == NULL) {p->color = BLACK;return;}if (p->sibling()->color == RED) {p->parent->color = RED;p->sibling()->color = BLACK;if (p == p->parent->leftTree)rotate_left(p->sibling());elserotate_right(p->sibling());}if (p->parent->color == BLACK && p->sibling()->color == BLACK&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {p->sibling()->color = RED;delete_case(p->parent);} else if (p->parent->color == RED && p->sibling()->color == BLACK&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {p->sibling()->color = RED;p->parent->color = BLACK;} else {if (p->sibling()->color == BLACK) {if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED&& p->sibling()->rightTree->color == BLACK) {p->sibling()->color = RED;p->sibling()->leftTree->color = BLACK;rotate_right(p->sibling()->leftTree);} else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK&& p->sibling()->rightTree->color == RED) {p->sibling()->color = RED;p->sibling()->rightTree->color = BLACK;rotate_left(p->sibling()->rightTree);}}p->sibling()->color = p->parent->color;p->parent->color = BLACK;if (p == p->parent->leftTree) {p->sibling()->rightTree->color = BLACK;rotate_left(p->sibling());} else {p->sibling()->leftTree->color = BLACK;rotate_right(p->sibling());}}}void insert(Node *p, int data) {if (p->value >= data) {if (p->leftTree != NIL)insert(p->leftTree, data);else {Node *tmp = new Node();tmp->value = data;tmp->leftTree = tmp->rightTree = NIL;tmp->parent = p;p->leftTree = tmp;insert_case(tmp);}} else {if (p->rightTree != NIL)insert(p->rightTree, data);else {Node *tmp = new Node();tmp->value = data;tmp->leftTree = tmp->rightTree = NIL;tmp->parent = p;p->rightTree = tmp;insert_case(tmp);}}}void insert_case(Node *p) {if (p->parent == NULL) {root = p;p->color = BLACK;return;}if (p->parent->color == RED) {if (p->uncle()->color == RED) {p->parent->color = p->uncle()->color = BLACK;p->grandparent()->color = RED;insert_case(p->grandparent());} else {if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {rotate_left(p);rotate_right(p);p->color = BLACK;p->leftTree->color = p->rightTree->color = RED;} else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {rotate_right(p);rotate_left(p);p->color = BLACK;p->leftTree->color = p->rightTree->color = RED;} else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {p->parent->color = BLACK;p->grandparent()->color = RED;rotate_right(p->parent);} else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {p->parent->color = BLACK;p->grandparent()->color = RED;rotate_left(p->parent);}}}}void DeleteTree(Node *p) {if (!p || p == NIL) {return;}DeleteTree(p->leftTree);DeleteTree(p->rightTree);delete p;} public:bst() {NIL = new Node();NIL->color = BLACK;root = NULL;}~bst() {if (root)DeleteTree(root);delete NIL;}void inorder() {if (root == NULL)return;inorder(root);cout << endl;}void insert(int x) {if (root == NULL) {root = new Node();root->color = BLACK;root->leftTree = root->rightTree = NIL;root->value = x;} else {insert(root, x);}}bool delete_value(int data) {return delete_child(root, data);} private:Node *root, *NIL; };

?

4. B樹

　　B樹也是一種用于查找的平衡樹，但是它不是二叉樹。

　　B樹的定義：B樹（B-tree）是一種樹狀數(shù)據(jù)結(jié)構(gòu)，能夠用來存儲排序后的數(shù)據(jù)。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、循序存取、插入數(shù)據(jù)及刪除的動作，都在對數(shù)時間內(nèi)完成。B樹，概括來說是一個一般化的二叉查找樹，可以擁有多于2個子節(jié)點。與自平衡二叉查找樹不同，B-樹為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時所經(jīng)歷的中間過程，從而加快存取速度。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫和文件系統(tǒng)的實作上。

　　在B樹中查找給定關(guān)鍵字的方法是，首先把根結(jié)點取來，在根結(jié)點所包含的關(guān)鍵字K1,…,Kn查找給定的關(guān)鍵字（可用順序查找或二分查找法），若找到等于給定值的關(guān)鍵字，則查找成功；否則，一定可以確定要查找的關(guān)鍵字在Ki與Ki+1之間，Pi為指向子樹根節(jié)點的指針，此時取指針Pi所指的結(jié)點繼續(xù)查找，直至找到，或指針Pi為空時查找失敗。

　　B樹作為一種多路搜索樹（并不是二叉的）：

　　1) 定義任意非葉子結(jié)點最多只有M個兒子；且M>2；

　　2)?根結(jié)點的兒子數(shù)為[2, M]；

　　3)?除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M]；

　　4)?每個結(jié)點存放至少M(fèi)/2-1（取上整）和至多M-1個關(guān)鍵字；（至少2個關(guān)鍵字）

　　5)?非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1；

　　6)?非葉子結(jié)點的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

　　7)?非葉子結(jié)點的指針：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的子樹，P[M]指向關(guān)鍵字大于K[M-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹；

　　8)?所有葉子結(jié)點位于同一層；

???????如下圖為一個M=3的B樹示例：

　　B樹創(chuàng)建的示意圖：

5. B+樹

　　B+樹是B樹的變體，也是一種多路搜索樹：

　　1) 其定義基本與B-樹相同，除了：

　　2) 非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同；

　　3) 非葉子結(jié)點的子樹指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）；

　　4) 為所有葉子結(jié)點增加一個鏈指針；

　　5) 所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)；

　　下圖為M=3的B+樹的示意圖：

　　B+樹的搜索與B樹也基本相同，區(qū)別是B+樹只有達(dá)到葉子結(jié)點才命中（B樹可以在非葉子結(jié)點命中），其性能也等價于在關(guān)鍵字全集做一次二分查找；

　　B+的性質(zhì)：

　　1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；

　　2.不可能在非葉子結(jié)點命中；

　　3.非葉子結(jié)點相當(dāng)于是葉子結(jié)點的索引（稀疏索引），葉子結(jié)點相當(dāng)于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；

　　4.更適合文件索引系統(tǒng)。

　　下面為一個B+樹創(chuàng)建的示意圖：

6. B*樹

　　B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針，將結(jié)點的最低利用率從1/2提高到2/3。

　　B*樹如下圖所示：

　　B*樹定義了非葉子結(jié)點關(guān)鍵字個數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）；

　　B+樹的分裂：當(dāng)一個結(jié)點滿時，分配一個新的結(jié)點，并將原結(jié)點中1/2的數(shù)據(jù)復(fù)制到新結(jié)點，最后在父結(jié)點中增加新結(jié)點的指針；B+樹的分裂只影響原結(jié)點和父結(jié)點，而不會影響兄弟結(jié)點，所以它不需要指向兄弟的指針；

　　B*樹的分裂：當(dāng)一個結(jié)點滿時，如果它的下一個兄弟結(jié)點未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點中，再在原結(jié)點插入關(guān)鍵字，最后修改父結(jié)點中兄弟結(jié)點的關(guān)鍵字（因為兄弟結(jié)點的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點，最后在父結(jié)點增加新結(jié)點的指針；

　　所以，B*樹分配新結(jié)點的概率比B+樹要低，空間使用率更高。

7. Trie樹

　　Tire樹稱為字典樹，又稱單詞查找樹，Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。　

Tire樹的三個基本性質(zhì)： 1)?根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符； 2) 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串； 3) 每個節(jié)點的所有子節(jié)點包含的字符都不相同。

　　Tire樹的應(yīng)用：

　　1)?串的快速檢索

　　給出N個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞。

在這道題中，我們可以用數(shù)組枚舉，用哈希，用字典樹，先把熟詞建一棵樹，然后讀入文章進(jìn)行比較，這種方法效率是比較高的。

　　2)?“串”排序

　　給定N個互不相同的僅由一個單詞構(gòu)成的英文名，讓你將他們按字典序從小到大輸出。用字典樹進(jìn)行排序，采用數(shù)組的方式創(chuàng)建字典樹，這棵樹的每個結(jié)點的所有兒子很顯然地按照其字母大小排序。對這棵樹進(jìn)行先序遍歷即可。

　　3) 最長公共前綴

　　對所有串建立字典樹，對于兩個串的最長公共前綴的長度即他們所在的結(jié)點的公共祖先個數(shù)，于是，問題就轉(zhuǎn)化為求公共祖先的問題。

?

----------------

作者：Poll的筆記?
博客出處：http://www.cnblogs.com/maybe2030/?
本文版權(quán)歸作者和博客園所有，歡迎轉(zhuǎn)載，轉(zhuǎn)載請標(biāo)明出處。?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/-oreo/articles/9952910.html

總結(jié)

以上是生活随笔為你收集整理的[数据结构]数据结构中各种树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。