树学习总结
樹
樹狀圖是一種數據結構，它是由n（n>=1）個有限節(jié)點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：
每個節(jié)點有零個或多個子節(jié)點；沒有父節(jié)點的節(jié)點稱為根節(jié)點；每一個非根節(jié)點有且只有一個父節(jié)點；
除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹；[1]?
中文名 樹 外文名 tree 數據結構 基本數據結構的一種
目錄
1 定義
2 相關術語
3 種類
4 深度
5 表示方法
? 圖像表達法
? 符號表達法
? 遍歷表達法
6 其他
7 父節(jié)點表示法
? 存儲結勾
? 基本操作
? 構造空樹
? 構造樹
? 判斷樹是否為空
? 獲取樹的深度
? 獲取第i個節(jié)點的值
? 改變節(jié)點的值
? 獲取節(jié)點的父節(jié)點
? 獲取節(jié)點的最左孩子節(jié)點
? 獲取節(jié)點的右兄弟節(jié)點
? 輸出樹
? 向樹中插入另一棵樹
? 刪除子樹
? 層序遍歷樹
8 孩子鏈表表示法
定義
樹
樹 (7張)
樹（tree）是包含n（n>0）個結點的有窮集，其中：
（1）每個元素稱為結點（node）；
（2）有一個特定的結點被稱為根結點或樹根（root）。
（3）除根結點之外的其余數據元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個
集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹也可以這樣定義：樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關
系構成的。集合中的元素稱為樹的結點，所定義的關系稱為父子關系。父子關系在樹的結點之間建立了
一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹
根。
我們可以形式地給出樹的遞歸定義如下:
單個結點是一棵樹，樹根就是該結點本身。
設T1,T2,..,Tk是樹，它們的根結點分別為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親，則得
到一棵新樹，結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點。我們
還稱T1,T2,..,Tk為結點n的子樹。
空集合也是樹，稱為空樹。空樹中沒有結點。
相關術語
節(jié)點的度：一個節(jié)點含有的子樹的個數稱為該節(jié)點的度；
葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點；
非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點；
雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；
孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；
樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；
節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；
樹的高度或深度：樹中節(jié)點的最大層次；
堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟；
節(jié)點的祖先：從根到該節(jié)點所經分支上的所有節(jié)點；
子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。
森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
種類
無序樹：樹中任意節(jié)點的子結點之間沒有順序關系，這種樹稱為無序樹,也稱為自由樹;
有序樹：樹中任意節(jié)點的子結點之間有順序關系，這種樹稱為有序樹；
二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹；
完全二叉樹
滿二叉樹
霍夫曼樹：帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；
深度
定義一棵樹的根結點層次為1，其他節(jié)點的層次是其父結點層次加1。一棵樹中所有結點的層次的最大值
稱為這棵樹的深度。
表示方法
圖像表達法
樹的表示方法有很多種，最常用的是圖像表示法。
一下是一個普通的樹（非二叉樹）：
符號表達法
用括號先將根結點放入一對圓括號中，然后把它的子樹由左至右的順序放入括號中，而對子樹也采用同
樣的方法處理；同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起
來。如前文樹形表示法可以表示為：（1（2（5（9，10）），3（6，7），4（8）））
遍歷表達法
遍歷表達法有3種方法：先序遍歷、中序遍歷、后序遍歷[2]?
例如右圖：
其先序遍歷為ABDECF
其中序遍歷為DBEAFC
其后序遍歷為DEBFCA
具體請參照參考資料
其他
關于二叉樹的其他知識請參照參考資料。
父節(jié)點表示法
存儲結勾
/* 樹節(jié)點的定義 */
#define MAX_TREE_SIZE 100
?
typedef struct{
? ? TElemType data;
? ? int parent; /* 父節(jié)點位置域 */
} PTNode;
?
typedef struct{
? ? PTNode nodes[MAX_TREE_SIZE];
? ? int n; /* 節(jié)點數 */
} PTree;
基本操作
設已有鏈隊列類型LinkQueue的定義及基本操作（參見隊列）。[3]?
構造空樹
清空或銷毀一個樹也是同樣的操作
void ClearTree(PTree *T){
? ? T->n = 0;
}
構造樹
void CreateTree(PTree *T){
? ? LinkQueue q;
? ? QElemType p,qq;
? ? int i=1,j,l;
? ? char c[MAX_TREE_SIZE]; /* 臨時存放孩子節(jié)點數組 */?
? ? InitQueue(&q); /* 初始化隊列 */
? ? printf("請輸入根節(jié)點(字符型，空格為空): ");
? ? scanf("%c%*c",&T->nodes[0].data); /* 根節(jié)點序號為0，%*c吃掉回車符 */
? ? if(T->nodes[0].data!=Nil) /* 非空樹 */ ?{
? ? ? ? T->nodes[0].parent=-1; /* 根節(jié)點無父節(jié)點 */
? ? ? ? qq.name=T->nodes[0].data;?
? ? ? ? qq.num=0;
? ? ? ? EnQueue(&q,qq); /* 入隊此節(jié)點 */
? ? ? ? while(i<MAX_TREE_SIZE&&!QueueEmpty(q)) /* 數組未滿且隊不空 */ ? ?{
? ? ? ? ? ? DeQueue(&q,&qq); /* 節(jié)點加入隊列 */
? ? ? ? ? ? printf("請按長幼順序輸入節(jié)點%c的所有孩子: ",qq.name);
? ? ? ? ? ? gets(c);
? ? ? ? ? ? l=strlen(c);
? ? ? ? ? ? for(j=0;j<l;j++){
? ? ? ? ? ? ? ? T->nodes[i].data=c[j];
? ? ? ? ? ? ? ? T->nodes[i].parent=qq.num;
? ? ? ? ? ? ? ? p.name=c[j];?
? ? ? ? ? ? ? ? p.num=i;
? ? ? ? ? ? ? ? EnQueue(&q,p); /* 入隊此節(jié)點 */
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? if(i>MAX_TREE_SIZE){
? ? ? ? ? ? ? printf("節(jié)點數超過數組容量\n");
? ? ? ? ? ? ? exit(OVERFLOW);
? ? ? ? ? }
? ? ? ? ? T->n=i;
? ? ? }
? ? ? else
? ? ? ? ? T->n=0;
?}
判斷樹是否為空
Status TreeEmpty(PTree *T){
? ? /* 初始條件：樹T存在。操作結果：若T為空樹，則返回TRUE，否則返回FALSE */ ?
? ? return T->n==0;
}
獲取樹的深度
int TreeDepth(PTree *T){
? ? /* 初始條件：樹T存在。操作結果：返回T的深度 */
? ? int k,m,def,max=0;
? ? for(k=0;k<T->n;++k){
? ? ? ? def=1; /* 初始化本節(jié)點的深度 */
? ? ? ? m=T->nodes[k].parent;
? ? ? ? while(m!=-1){
? ? ? ? ? ? m=T->nodes[m].parent;
? ? ? ? ? ? def++;
? ? ? ? }
? ? ? ? if(max<def)
? ? ? ? ? ? max=def;
? ? }
? ? return max; /* 最大深度 */
}
獲取根節(jié)點
TElemType Root(PTree *T){
? ? /* 初始條件：樹T存在。操作結果：返回T的根 */
? ? int i;
? ? for(i=0;i<T->n;i++)
? ? ? if(T->nodes[i].parent<0)
? ? ? ? return T->nodes[i].data;
? ? return Nil;
}
獲取第i個節(jié)點的值
TElemType Value(PTree *T,int i){
? ? /* 初始條件：樹T存在，i是樹T中節(jié)點的序號。操作結果：返回第i個節(jié)點的值 */
? ? if(i<T->n)
? ? ? ? return T->nodes[i].data;
? ? else
? ? ? ? return Nil;
}
改變節(jié)點的值
[4]?
1
Status Assign(PTree *T,TElemType cur_e,TElemType value){ /* 初始條件：樹T存在，cur_e是樹T中
節(jié)點的值。操作結果：改cur_e為value */ ?int j; ?for(j=0;j<T->n;j++) ?{ ? ?if(T->nodes
[j].data==cur_e) ? ?{ ? ? ?T->nodes[j].data=value; ? ? ?return OK; ? ?} ?} ?return ERROR;}
獲取節(jié)點的父節(jié)點
1
TElemType Parent(PTree *T,TElemType cur_e){ /* 初始條件：樹T存在，cur_e是T中某個節(jié)點 */ ?/*?
操作結果：若cur_e是T的非根節(jié)點，則返回它的父節(jié)點，否則函數值為"空"*/ ?int j; ?for(j=1;j<T-
>n;j++) /* 根節(jié)點序號為0 */ ? ?if(T->nodes[j].data==cur_e) ? ? ?return T->nodes[T->nodes
[j].parent].data; ?return Nil;}
獲取節(jié)點的最左孩子節(jié)點
1
TElemType LeftChild(PTree *T,TElemType cur_e){ /* 初始條件：樹T存在，cur_e是T中某個節(jié)點 */ ?
/* 操作結果：若cur_e是T的非葉子節(jié)點，則返回它的最左孩子，否則返回"空"*/ ?int i,j; ?for
(i=0;i<T->n;i++) ? ?if(T->nodes[i].data==cur_e) /* 找到cur_e，其序號為i */ ? ? ?break; ?
for(j=i+1;j<T->n;j++) /* 根據樹的構造函數，孩子的序號>其父節(jié)點的序號 */ ? ?if(T->nodes
[j].parent==i) /* 根據樹的構造函數，最左孩子(長子)的序號<其它孩子的序號 */ ? ? ?return T-
>nodes[j].data; ?return Nil;}
獲取節(jié)點的右兄弟節(jié)點
1
TElemType RightSibling(PTree *T,TElemType cur_e){ /* 初始條件：樹T存在，cur_e是T中某個節(jié)點?
*/ ?/* 操作結果：若cur_e有右(下一個)兄弟，則返回它的右兄弟，否則返回"空"*/ ?int i; ?for
(i=0;i<T->n;i++) ? ?if(T->nodes[i].data==cur_e) /* 找到cur_e，其序號為i */ ? ? ?break; ?if
(T->nodes[i+1].parent==T->nodes[i].parent) ?/* 根據樹的構造函數，若cur_e有右兄弟的話則右兄
弟緊接其后 */ ? ?return T->nodes[i+1].data; ?return Nil;}
輸出樹
1
void Print(PTree *T){ /* 輸出樹T。加 */ ?int i; ?printf("節(jié)點個數=%d\n",T->n); ?printf(" 節(jié)
點 父節(jié)點\n"); ?for(i=0;i<T->n;i++) ?{ ? ?printf(" ? ?%c",Value(T,i)); /* 節(jié)點 */ ? ?if(T-
>nodes[i].parent>=0) /* 有父節(jié)點 */ ? ? ?printf(" ? ?%c",Value(T,T->nodes[i].parent)); /*?
父節(jié)點 */ ? ?printf("\n"); ?}}
向樹中插入另一棵樹
1
Status InsertChild(PTree *T,TElemType p,int i,PTree c){ /* 初始條件：樹T存在，p是T中某個節(jié)
點，1≤i≤p所指節(jié)點的度+1，非空樹c與T不相交 */ ?/* 操作結果：插入c為T中p節(jié)點的第i棵子樹 */ ?
int j,k,l,f=1,n=0; /* 設交換標志f的初值為1，p的孩子數n的初值為0 */ ?PTNode t; ?if(!
TreeEmpty(T)) /* T不空 */ ?{ ? ?for(j=0;j<T->n;j++) /* 在T中找p的序號 */ ? ? ?if(T->nodes
[j].data==p) /* p的序號為j */ ? ? ? ?break; ? ?l=j+1; /* 如果c是p的第1棵子樹，則插在j+1處?
*/ ? ?if(i>1) /* c不是p的第1棵子樹 */ ? ?{ ? ? ?for(k=j+1;k<T->n;k++) /* 從j+1開始找p的前
i-1個孩子 */ ? ? ? ?if(T->nodes[k].parent==j) /* 當前節(jié)點是p的孩子 */ ? ? ? ?{ ? ? ? ? ?n+
+; /* 孩子數加1 */ ? ? ? ? ?if(n==i-1) /* 找到p的第i-1個孩子，其序號為k1 */ ? ? ? ? ? ?
break; ? ? ? ?} ? ? ?l=k+1; /* c插在k+1處 */ ? ?} /* p的序號為j，c插在l處 */ ? ?if(l<T->n)?
/* 插入點l不在最后 */ ? ? ?for(k=T->n-1;k>=l;k--) /* 依次將序號l以后的節(jié)點向后移c.n個位置?
*/ ? ? ?{ ? ? ? ?T->nodes[k+c.n]=T->nodes[k]; ? ? ? ?if(T->nodes[k].parent>=l) ? ? ? ? ?T-
>nodes[k+c.n].parent+=c.n; ? ? ?} ? ?for(k=0;k<c.n;k++) ? ?{ ? ? ?T->nodes[l
+k].data=c.nodes[k].data; /* 依次將樹c的所有節(jié)點插于此處 */ ? ? ?T->nodes[l
+k].parent=c.nodes[k].parent+l; ? ?} ? ?T->nodes[l].parent=j; /* 樹c的根節(jié)點的父節(jié)點為p */ ?
? T->n+=c.n; /* 樹T的節(jié)點數加c.n個 */ ? ?while(f) ? ?{ /* 從插入點之后，將節(jié)點仍按層序排列?
*/ ? ? ?f=0; /* 交換標志置0 */ ? ? ?for(j=l;j<T->n-1;j++) ? ? ? ?if(T->nodes[j].parent>T-
>nodes[j+1].parent) ? ? ? ?{/* 如果節(jié)點j的父節(jié)點排在節(jié)點j+1的父節(jié)點之后（樹沒有按層序排列）
，交換兩節(jié)點*/ ? ? ? ? ?t=T->nodes[j]; ? ? ? ? ?T->nodes[j]=T->nodes[j+1]; ? ? ? ? ?T-
>nodes[j+1]=t; ? ? ? ? ?f=1; /* 交換標志置1 */ ? ? ? ? ?for(k=j;k<T->n;k++) /* 改變父節(jié)點序
號 */ ? ? ? ? ? ?if(T->nodes[k].parent==j) ? ? ? ? ? ? ?T->nodes[k].parent++; /* 父節(jié)點序號
改為j+1 */ ? ? ? ? ? ?else if(T->nodes[k].parent==j+1) ? ? ? ? ? ? ?T->nodes[k].parent--;?
/* 父節(jié)點序號改為j */ ? ? ? ?} ? ?} ? ?return OK; ?} ?else /* 樹T不存在 */ ? ?return?
ERROR;}
刪除子樹
1
Status deleted[MAX_TREE_SIZE+1]; /* 刪除標志數組(全局量) */void DeleteChild(PTree?
*T,TElemType p,int i){ /* 初始條件：樹T存在，p是T中某個節(jié)點，1≤i≤p所指節(jié)點的度 */ ?/* 操
作結果：刪除T中節(jié)點p的第i棵子樹 */ ?int j,k,n=0; ?LinkQueue q; ?QElemType pq,qq; ?for
(j=0;j<=T->n;j++) ? ?deleted[j]=0; /* 置初值為0(不刪除標記) */ ?pq.name='a'; /* 此成員不用?
*/ ?InitQueue(&q); /* 初始化隊列 */ ?for(j=0;j<T->n;j++) ? ?if(T->nodes[j].data==p) ? ? ?
break; /* j為節(jié)點p的序號 */ ?for(k=j+1;k<T->n;k++) ?{ ? ?if(T->nodes[k].parent==j) ? ? ?n+
+; ? ?if(n==i) ? ? ?break; /* k為p的第i棵子樹節(jié)點的序號 */ ?} ?if(k<T->n) /* p的第i棵子樹節(jié)
點存在 */ ?{ ? ?n=0; ? ?pq.num=k; ? ?deleted[k]=1; /* 置刪除標記 */ ? ?n++; ? ?EnQueue
(&q,pq); ? ?while(!QueueEmpty(q)) ? ?{ ? ? ?DeQueue(&q,&qq); ? ? ?for(j=qq.num+1;j<T->n;j+
+) ? ? ? ?if(T->nodes[j].parent==qq.num) ? ? ? ?{ ? ? ? ? ?pq.num=j; ? ? ? ? ?deleted[j]=1;?
/* 置刪除標記 */ ? ? ? ? ?n++; ? ? ? ? ?EnQueue(&q,pq); ? ? ? ?} ? ?} ? ?for(j=0;j<T->n;j+
+) ? ? ?if(deleted[j]==1) ? ? ?{ ? ? ? ?for(k=j+1;k<=T->n;k++) ? ? ? ?{ ? ? ? ? ?deleted
[k-1]=deleted[k]; ? ? ? ? ?T->nodes[k-1]=T->nodes[k]; ? ? ? ? ?if(T->nodes[k].parent>j) ? ??
? ? ? ?T->nodes[k-1].parent--; ? ? ? ?} ? ? ? ?j--; ? ? ?} ? ?T->n-=n; /* n為待刪除節(jié)點數?
*/ ?}}
層序遍歷樹
1
void TraverseTree(PTree *T,void(*Visit)(TElemType)){ /* 初始條件：二叉樹T存在,Visit是對節(jié)點
操作的應用函數 */ ?/* 操作結果：層序遍歷樹T,對每個節(jié)點調用函數Visit一次且僅一次 */ ?int i; ?
for(i=0;i<T->n;i++) ? ?Visit(T->nodes[i].data); ?printf("\n");}
1
?
孩子鏈表表示法
存儲結構[5]?
1
/*樹的孩子鏈表存儲表示*/typedef struct CTNode { // 孩子節(jié)點 ? int child; ? struct CTNode?
*next;} *ChildPtr;typedef struct { ? ElemType data； // 節(jié)點的數據元素 ? ChildPtr?
firstchild； // 孩子鏈表頭指針} CTBox;typedef struct { ? CTBox nodes[MAX_TREE_SIZE]； ?int?
n, r； // 節(jié)點數和根節(jié)點的位置} CTree;
========
B樹、B-樹、B+樹、B*樹
B樹? ? ? ?即二叉搜索樹：
? ? ? ?1.所有非葉子結點至多擁有兩個兒子（Left和Right）；
? ? ? ?2.所有結點存儲一個關鍵字；
? ? ? ?3.非葉子結點的左指針指向小于其關鍵字的子樹，右指針指向大于其關鍵字的子樹；
? ? ? ?如：
? ? ? ?B樹的搜索，從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那么就命中；
否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入
右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字；
? ? ? ?如果B樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那么B樹
的搜索性能逼近二分查找；但它比連續(xù)內存空間的二分查找的優(yōu)點是，改變B樹結構
（插入與刪除結點）不需要移動大段的內存數據，甚至通常是常數開銷；
? ? ? ?如：
? ?但B樹在經過多次插入與刪除后，有可能導致不同的結構：
? ?右邊也是一個B樹，但它的搜索性能已經是線性的了；同樣的關鍵字集合有可能導致不同的
樹結構索引；所以，使用B樹還要考慮盡可能讓B樹保持左圖的結構，和避免右圖的結構，也就
是所謂的“平衡”問題； ? ? ?
? ? ? ?實際使用的B樹都是在原B樹的基礎上加上平衡算法，即“平衡二叉樹”；如何保持B樹
結點分布均勻的平衡算法是平衡二叉樹的關鍵；平衡算法是一種在B樹中插入和刪除結點的
策略；
B-樹
? ? ? ?是一種多路搜索樹（并不是二叉的）：
? ? ? ?1.定義任意非葉子結點最多只有M個兒子；且M>2；
? ? ? ?2.根結點的兒子數為[2, M]；
? ? ? ?3.除根結點以外的非葉子結點的兒子數為[M/2, M]；
? ? ? ?4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
? ? ? ?5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；
? ? ? ?6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
? ? ? ?7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的
子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
? ? ? ?8.所有葉子結點位于同一層；
? ? ? ?如：（M=3）
? ? ? ?B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果
命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為
空，或已經是葉子結點；
B-樹的特性：
? ? ? ?1.關鍵字集合分布在整顆樹中；
? ? ? ?2.任何一個關鍵字出現且只出現在一個結點中；
? ? ? ?3.搜索有可能在非葉子結點結束；
? ? ? ?4.其搜索性能等價于在關鍵字全集內做一次二分查找；
? ? ? ?5.自動層次控制；
? ? ? ?由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少
利用率，其最底搜索性能為：
? ? ? ?其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；
? ? ? ?所以B-樹的性能總是等價于二分查找（與M值無關），也就沒有B樹平衡的問題；
? ? ? ?由于M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各占
M/2的結點；刪除結點時，需將兩個不足M/2的兄弟結點合并；
B+樹
? ? ? ?B+樹是B-樹的變體，也是一種多路搜索樹：
? ? ? ?1.其定義基本與B-樹同，除了：
? ? ? ?2.非葉子結點的子樹指針與關鍵字個數相同；
? ? ? ?3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹
（B-樹是開區(qū)間）；
? ? ? ?5.為所有葉子結點增加一個鏈指針；
? ? ? ?6.所有關鍵字都在葉子結點出現；
? ? ? ?如：（M=3）
? ?B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達到葉子結點才命中（B-樹可以在
非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；
? ? ? ?B+的特性：
? ? ? ?1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好
是有序的；
? ? ? ?2.不可能在非葉子結點命中；
? ? ? ?3.非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲
（關鍵字）數據的數據層；
? ? ? ?4.更適合文件索引系統(tǒng)；
B*樹
? ? ? ?是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；
? ?B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3
（代替B+樹的1/2）；
? ? ? ?B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數據
復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父
結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針；
? ? ? ?B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那么將一部分
數據移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字
（因為兄弟結點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之
間增加新結點，并各復制1/3的數據到新結點，最后在父結點增加新結點的指針；
? ? ? ?所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高；
小結
? ? ? ?B樹：二叉樹，每個結點只存儲一個關鍵字，等于則命中，小于走左結點，大于
走右結點；
? ? ? ?B-樹：多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵
字范圍的子結點；
? ? ? ?所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中；
? ? ? ?B+樹：在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點
中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；
? ? ? ?B*樹：在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率
從1/2提高到2/3；
========
R樹
R樹是GUTTMAN于1984年提出的最早支持有序擴展的對象存取方法之一，也是目前應用最為廣泛的一種空間索引結構。許多商用空間數據庫系統(tǒng)，如MapInfo SpatialWaro和Oracle Spatial等均提供對R樹的支
持，開放源碼系統(tǒng)PostgreSQL也實現了R樹。近二十多年來，許多學者致力于R樹的研究，在R樹的基礎上
衍生出了許多變種。比較典型的有R+樹、R*樹、壓縮R樹等。
中文名 R樹 外文名 R-Tree 提出者 Antonin Guttman 提出時間 1984年 應用學科 計算機 適用領域范
圍 軟件，數據結構 適用領域范圍 多維索引
目錄
1 定義
2 特點
3 操作
? 搜索
? 插入
? 刪除
定義編輯
一棵R樹滿足如下的性質：
1.除根結點之外，所有非根結點包含有m至M個記錄索引（條目）。根結點的記錄個數可以少于m。通常，
m=M/2。
2.對于所有葉子中存儲的記錄（條目），I是最小的可以在空間中完全覆蓋這些記錄所代表的點的矩形（
注意：此處所說的“矩形”是可以擴展到高維空間的）。
3.對于所有非葉子結點上的記錄（條目），i是最小的可以在空間上完全覆蓋這些條目所代表的點的矩形
（同性質2）。
4.所有葉子結點都位于同一層，因此R樹為平衡樹。
特點編輯
R樹是一個高度平衡樹，它是B樹在k維上的自然擴展，用空間對象的MBR來近似表達空間對象，根據地物
的MBR建立R樹，可以直接對空間中占據一定范圍的空間對象進行索引。R樹的每一個結點都對應著磁盤頁
D和區(qū)域I，如果結點不是葉結點，則該結點的所有子結點的區(qū)域都在區(qū)域I的范圍之內，而且存儲在磁盤
頁D中。如果結點是葉結點，那么磁盤頁D中存儲的將是區(qū)域I范圍內的一系列子區(qū)域，子區(qū)域緊緊圍繞空
間對象，一般為空間對象的外接矩形。
R樹中每個結點所能擁有的子結點數目是有上下限的。下限保證索引對磁盤空間的有效利用，子結點的數
目小于下限的結點將被刪除，該結點的子結點將被分配到其他的結點中；設立上限是因為每一個結點只
對應一個磁盤頁，如果某個結點要求的空間大于一個磁盤頁，那么該結點就要被劃分為兩個新的結點，
原來結點的所有子結點將被分配到這兩個新的結點中。令M為一個結點中記錄數目的最大值，mSM/2為一
參數，說明一個節(jié)點記錄的最小值，m可作為調節(jié)樹結構的一個可變參數，R樹滿足如下幾項特點：
1．根節(jié)點若非葉子節(jié)點，則至少有兩個子節(jié)點；
2．每個非根葉節(jié)點和非葉節(jié)點包含的實體個數均介于m和M之間；
3．所有葉子節(jié)點在同一層次；
R樹兄弟結點對應的空間區(qū)域可以重疊，可以較容易地進行插入和刪除操作。但正因為區(qū)域之間有重疊，
空間索引可能要對多條路徑進行搜索后才能得到最后的結果。當查找與給定的查詢窗口相交的所有空間
對象時，空間搜索算法是從根結點開始，向下搜索相應的子樹．算法遞歸遍歷所有約束矩形與查詢窗口
相交的子樹，當到達葉結點時，邊界矩形中的元素被取出并測試其是否與查詢矩形相交，所有與查詢窗
口相交的葉結點即為要查找的空間對象。R樹的查詢效率會因重疊區(qū)域的增大而大大減弱，在最壞情況下
，其時間復雜度甚至會由對數搜索退化成線性搜索。正是這個原因促使了R+樹的產生。
在R+樹中，兄弟結點對應的空間區(qū)域沒有重疊，而沒有重疊的區(qū)域劃分可以使空間索引搜索的速度大大
提高，克服了R樹中多路查詢的問題，但同時它也存在著一些缺陷，如對某個最小約束矩形的劃分，可能
會引起相關子樹上其他結點也需要重新劃分，向下分裂操作可能使得已經劃分好了的結點被重新劃分，
空間對象在R+樹的葉結點中被重復標記，完成刪除運算后，必須對R+樹進行重建等，同時由于在插入和
刪除空間對象時要保證兄弟結點對應的空間區(qū)域不重疊，而使插入和刪除操作的效率降低。
R*樹是最有效的R樹變種，它能對覆蓋區(qū)域、重疊面積和邊界周長進行啟發(fā)式地優(yōu)化，并通過重新插入節(jié)
點重建R．樹以提高其性能，但重新插入這個過程相當繁瑣，其實現過程太過漫長。壓縮R樹的空間數據
集是預先己知的，通過預先對數據進行合理有效的組織，可以保證其具有很高的空間利用率和良好的查
詢效率，但由于其不能進行動態(tài)插入和刪除，因而其應用受到了很大限制。
R樹是B樹在多維空間的擴展，是一種平衡的樹結構。R樹結構采用平行于數據空間軸的最小的邊界矩形來
近似復雜的空間對象，其主要優(yōu)點是用一定數量的字節(jié)來表示一個復雜的對象。盡管這樣會丟失很多的
信息，但是空間物體的最小邊界矩形保留了物體的最重要的幾何特性，即空間物體的位置和其在整個坐
標軸上的范圍。
操作編輯
搜索
R樹的搜索操作很簡單，跟B樹上的搜索十分相似。它返回的結果是所有符合查找信息的記錄條目。而輸
入是什么？就我個人的理解，輸入不僅僅是一個范圍了，它更可以看成是一個空間中的矩形。也就是說
，我們輸入的是一個搜索矩形。
先給出偽代碼：
Function：Search
描述：假設T為一棵R樹的根結點，查找所有搜索矩形S覆蓋的記錄條目。
S1:[查找子樹]如果T是非葉子結點，如果T所對應的矩形與S有重合，那么檢查所有T中存儲的條目，對于
所有這些條目，使用Search操作作用在每一個條目所指向的子樹的根結點上（即T結點的孩子結點）。
S2:[查找葉子結點]如果T是葉子結點，如果T所對應的矩形與S有重合，那么直接檢查S所指向的所有記錄
條目。返回符合條件的記錄。
插入
R樹的插入操作也同B樹的插入操作類似。當新的數據記錄需要被添加入葉子結點時，若葉子結點溢出，
那么我們需要對葉子結點進行分裂操作。顯然，葉子結點的插入操作會比搜索操作要復雜。插入操作需
要一些輔助方法才能夠完成。
來看一下偽代碼：
Function：Insert
描述：將新的記錄條目E插入給定的R樹中。
I1：[為新記錄找到合適插入的葉子結點]開始ChooseLeaf方法選擇葉子結點L以放置記錄E。
I2：[添加新記錄至葉子結點]如果L有足夠的空間來放置新的記錄條目，則向L中添加E。如果沒有足夠的
空間，則進行SplitNode方法以獲得兩個結點L與LL，這兩個結點包含了所有原來葉子結點L中的條目與新
條目E。
I3：[將變換向上傳遞]開始對結點L進行AdjustTree操作，如果進行了分裂操作，那么同時需要對LL進行
AdjustTree操作。
I4：[對樹進行增高操作]如果結點分裂，且該分裂向上傳播導致了根結點的分裂，那么需要創(chuàng)建一個新
的根結點，并且讓它的兩個孩子結點分別為原來那個根結點分裂后的兩個結點。
Function：ChooseLeaf
描述：選擇葉子結點以放置新條目E。
CL1：[Initialize]設置N為根結點。
CL2：[葉子結點的檢查]如果N為葉子結點，則直接返回N。
CL3：[選擇子樹]如果N不是葉子結點，則遍歷N中的結點，找出添加E.I時擴張最小的結點，并把該結點
定義為F。如果有多個這樣的結點，那么選擇面積最小的結點。
CL4：[下降至葉子結點]將N設為F，從CL2開始重復操作。
Function：AdjustTree
描述：葉子結點的改變向上傳遞至根結點以改變各個矩陣。在傳遞變換的過程中可能會產生結點的分裂
。
AT1：[初始化]將N設為L。
AT2：[檢驗是否完成]如果N為根結點，則停止操作。
AT3：[調整父結點條目的最小邊界矩形]設P為N的父節(jié)點，EN為指向在父節(jié)點P中指向N的條目。調整EN.I
以保證所有在N中的矩形都被恰好包圍。
AT4：[向上傳遞結點分裂]如果N有一個剛剛被分裂產生的結點NN，則創(chuàng)建一個指向NN的條目ENN。如果P
有空間來存放ENN，則將ENN添加到P中。如果沒有，則對P進行SplitNode操作以得到P和PP。
AT5：[升高至下一級]如果N等于L且發(fā)生了分裂，則把NN置為PP。從AT2開始重復操作。
刪除
R樹的刪除操作與B樹的刪除操作會有所不同，不過同B樹一樣，會涉及到壓縮等操作。相信讀者看完以下
的偽代碼之后會有所體會。R樹的刪除同樣是比較復雜的，需要用到一些輔助函數來完成整個操作。
偽代碼如下：
Function：Delete
描述：將一條記錄E從指定的R樹中刪除。
D1：[找到含有記錄的葉子結點]使用FindLeaf方法找到包含有記錄E的葉子結點L。如果搜索失敗，則直
接終止。
D2：[刪除記錄]將E從L中刪除。
D3：[傳遞記錄]對L使用CondenseTree操作
D4：[縮減樹]當經過以上調整后，如果根結點只包含有一個孩子結點，則將這個唯一的孩子結點設為根
結點。
Function：FindLeaf
描述：根結點為T，期望找到包含有記錄E的葉子結點。
FL1：[搜索子樹]如果T不是葉子結點，則檢查每一條T中的條目F，找出與E所對應的矩形相重合的F（不
必完全覆蓋）。對于所有滿足條件的F，對其指向的孩子結點進行FindLeaf操作，直到尋找到E或者所有
條目均以被檢查過。
FL2：[搜索葉子結點以找到記錄]如果T是葉子結點，那么檢查每一個條目是否有E存在，如果有則返回T
。
Function：CondenseTree
描述：L為包含有被刪除條目的葉子結點。如果L的條目數過少（小于要求的最小值m），則必須將該葉子
結點L從樹中刪除。經過這一刪除操作，L中的剩余條目必須重新插入樹中。此操作將一直重復直至到達
根結點。同樣，調整在此修改樹的過程所經過的路徑上的所有結點對應的矩形大小。
CT1：[初始化]令N為L。初始化一個用于存儲被刪除結點包含的條目的鏈表Q。
CT2：[找到父條目]如果N為根結點，那么直接跳轉至CT6。否則令P為N的父結點，令EN為P結點中存儲的
指向N的條目。
CT3：[刪除下溢結點]如果N含有條目數少于m，則從P中刪除EN，并把結點N中的條目添加入鏈表Q中。
CT4：[調整覆蓋矩形]如果N沒有被刪除，則調整EN.I使得其對應矩形能夠恰好覆蓋N中的所有條目所對應
的矩形。
CT5：[向上一層結點進行操作]令N等于P，從CT2開始重復操作。
CT6：[重新插入孤立的條目]所有在Q中的結點中的條目需要被重新插入。原來屬于葉子結點的條目可以
使用Insert操作進行重新插入，而那些屬于非葉子結點的條目必須插入刪除之前所在層的結點，以確保
它們所指向的子樹還處于相同的層。
========
紅黑樹
之前看了很多寫紅黑樹的博客，但是感覺都講的不太清楚！沒說這樣操作如何使他保持平衡的，于是疑
惑重重，就看不下去了，一次不經意看到一個人說維基百科的紅黑樹講的好，我就隨便點了一下一看—
—這下瘋了~，怎么講的這么好！可以說是把一個復雜的問題，講得簡單化！這太幸福了！ 于是我就慢
慢學會了！強烈推薦維基的這個講解，再也找不到比這還好的講解了！
下面將是我對紅黑樹的總結，里面的性感的圖片都是維基百科紅黑樹上的^_^！我討論的紅黑樹需建立在
會平衡二叉樹的基礎上去學，即若不懂“旋轉”操作，請看平衡二叉樹的旋轉操作。
紅黑樹（RBT）的定義：它或者是一顆空樹，或者是具有一下性質的二叉查找樹：
1.節(jié)點非紅即黑。
2.根節(jié)點是黑色。
3.所有NULL結點稱為葉子節(jié)點，且認為顏色為黑。
4.所有紅節(jié)點的子節(jié)點都為黑色。
5.從任一節(jié)點到其葉子節(jié)點的所有路徑上都包含相同數目的黑節(jié)點。
看完紅黑樹的定義是不是可暈？怎么這么多要求！！這怎么約束啊？我剛看到這5條約束，直接無語了，
1-3、4還好說，第5點是怎么回事啊？怎么約束？整這么復雜的條件好干啥啊？我來簡單說說呵：第3條
，顯然這里的葉子節(jié)點不是平常我們所說的葉子節(jié)點，如圖標有NIL的為葉子節(jié)點，為什么不按常規(guī)出牌
，因為按一般的葉子節(jié)點也行，但會使算法更復雜；第4條，即該樹上決不允許存在兩個連續(xù)的紅節(jié)點；
第5條，比如圖中紅8到1左邊的葉子節(jié)點的路徑包含2個黑節(jié)點，到6下的葉子節(jié)點的路徑也包含2個黑節(jié)
點。所有性質1-5合起來約束了該樹的平衡性能--即該樹上的最長路徑不可能會大于2倍最短路徑。為什
么？因為第1條該樹上的節(jié)點非紅即黑，由于第4條該樹上不允許存在兩個連續(xù)的紅節(jié)點，那么對于從一
個節(jié)點到其葉子節(jié)點的一條最長的路徑一定是紅黑交錯的，那么最短路徑一定是純黑色的節(jié)點；而又第5
條從任一節(jié)點到其葉子節(jié)點的所有路徑上都包含相同數目的黑節(jié)點，這么來說最長路徑上的黑節(jié)點的數
目和最短路徑上的黑節(jié)點的數目相等！而又第2條根結點為黑、第3條葉子節(jié)點是黑，那么可知：最長路
徑<=2*最短路徑。一顆二叉樹的平衡性能越好，那么它的效率越高！顯然紅黑樹的平衡性能比AVL的略差
些，但是經過大量試驗證明，實際上紅黑樹的效率還是很不錯了，仍能達到O(logN)，這個我不知道，我
現在不可能做過大量試驗，只是聽人家這樣說，O(∩_∩)O哈哈~但你至少知道他的時間復雜度一定小于
2O(logN)!
上邊的性質看個10遍，看懂看透徹再看操作！
插入操作
由于性質的約束：插入點不能為黑節(jié)點，應插入紅節(jié)點。因為你插入黑節(jié)點將破壞性質5，所以每次插入
的點都是紅結點，但是若他的父節(jié)點也為紅，那豈不是破壞了性質4？對啊，所以要做一些“旋轉”和一
些節(jié)點的變色！另為敘述方便我們給要插入的節(jié)點標為N（紅色），父節(jié)點為P，祖父節(jié)點為G，叔節(jié)點為
U。下邊將一一列出所有插入時遇到的情況：
情形1：該樹為空樹，直接插入根結點的位置，違反性質1，把節(jié)點顏色有紅改為黑即可。
情形2：插入節(jié)點N的父節(jié)點P為黑色，不違反任何性質，無需做任何修改。
?情形1很簡單，情形2中P為黑色，一切安然無事，但P為紅就不一樣了，下邊是P為紅的各種情況，也是
真正要學的地方！
情形3：N為紅，P為紅，（祖節(jié)點一定存在，且為黑，下邊同理）U也為紅，這里不論P是G的左孩子，還
是右孩子；不論N是P的左孩子，還是右孩子。
操作：如圖把P、U改為黑色，G改為紅色，未結束。
解析：N、P都為紅，違反性質4；若把P改為黑，符合性質4，顯然左邊少了一個黑節(jié)點，違反性質5；所
以我們把G，U都改為相反色，這樣一來通過G的路徑的黑節(jié)點數目沒變，即符合4、5，但是G變紅了，若G
的父節(jié)點又是紅的不就有違反了4，是這樣，所以經過上邊操作后未結束，需把G作為起始點，即把G看做
一個插入的紅節(jié)點繼續(xù)向上檢索----屬于哪種情況，按那種情況操作~要么中間就結束，要么知道根結點
（此時根結點變紅，一根結點向上檢索，那木有了，那就把他變?yōu)楹谏?#xff09;。
情形4：N為紅，P為紅，U為黑，P為G的左孩子，N為P的左孩子（或者P為G的右孩子，N為P的左孩子；反
正就是同向的）。
操作：如圖P、G變色，P、G變換即左左單旋（或者右右單旋），結束。
解析：要知道經過P、G變換（旋轉），變換后P的位置就是當年G的位置，所以紅P變?yōu)楹?#xff0c;而黑G變?yōu)榧t
都是為了不違反性質5，而維持到達葉節(jié)點所包含的黑節(jié)點的數目不變！還可以理解為：也就是相當于（
只是相當于，并不是實事，只是為了更好理解；）把紅N頭上的紅節(jié)點移到對面黑U的頭上；這樣即符合
了性質4也不違反性質5，這樣就結束了。
情形5：N為紅，P為紅，U為黑，P為G的左孩子，N為P的右孩子（或者P為G的右孩子，N為P的左孩子；反
正兩方向相反）。
操作：需要進行兩次變換（旋轉），圖中只顯示了一次變換-----首先P、N變換，顏色不變；然后就變成
了情形4的情況，按照情況4操作，即結束。
解析：由于P、N都為紅，經變換，不違反性質5；然后就變成4的情形，此時G與G現在的左孩子變色，并
變換，結束。
?
刪除操作
我們知道刪除需先找到“替代點”來替代刪除點而被刪除，也就是刪除的是替代點，而替代點N的至少有
一個子節(jié)點為NULL，那么，若N為紅色，則兩個子節(jié)點一定都為NULL（必須地），那么直接把N刪了，不
違反任何性質，ok，結束了；若N為黑色，另一個節(jié)點M不為NULL，則另一個節(jié)點M一定是紅色的，且M的
子節(jié)點都為NULL（按性質來的，不明白，自己分析一下）那么把N刪掉，M占到N的位置，并改為黑色，不
違反任何性質，ok，結束了；若N為黑色，另一個節(jié)點也為NULL，則把N刪掉，該位置置為NULL，顯然這
個黑節(jié)點被刪除了，破壞了性質5，那么要以N節(jié)點為起始點檢索看看屬于那種情況，并作相應的操作，
另還需說明N為黑點（也許是NULL，也許不是，都一樣），P為父節(jié)點，S為兄弟節(jié)點（這個我真想給兄弟
節(jié)點叫B（brother）多好啊，不過人家圖就是S我也不能改，在重畫圖，太浪費時間了！S也行呵呵，就
當是sister也行，哈哈）分為以下5中情況：
情形1：S為紅色（那么父節(jié)點P一定是黑，子節(jié)點一定是黑），N是P的左孩子（或者N是P的右孩子）。
操作：P、S變色，并交換----相當于AVL中的右右中旋轉即以P為中心S向左旋（或者是AVL中的左左中的
旋轉），未結束。
解析：我們知道P的左邊少了一個黑節(jié)點，這樣操作相當于在N頭上又加了一個紅節(jié)點----不違反任何性
質，但是到通過N的路徑仍少了一個黑節(jié)點，需要再把對N進行一次檢索，并作相應的操作才可以平衡（
暫且不管往下看）。
情形2：P、S及S的孩子們都為黑。
操作：S改為紅色，未結束。
解析：S變?yōu)榧t色后經過S節(jié)點的路徑的黑節(jié)點數目也減少了1，那個從P出發(fā)到其葉子節(jié)點到所有路徑所
包含的黑節(jié)點數目（記為num）相等了。但是這個num比之前少了1，因為左右子樹中的黑節(jié)點數目都減少
了！一般地，P是他父節(jié)點G的一個孩子，那么由G到其葉子節(jié)點的黑節(jié)點數目就不相等了，所以說沒有結
束，需把P當做新的起始點開始向上檢索。
情形3：P為紅（S一定為黑），S的孩子們都為黑。
操作：P該為黑，S改為紅，結束。
解析：這種情況最簡單了，既然N這邊少了一個黑節(jié)點，那么S這邊就拿出了一個黑節(jié)點來共享一下，這
樣一來，S這邊沒少一個黑節(jié)點，而N這邊便多了一個黑節(jié)點，這樣就恢復了平衡，多么美好的事情哈！
情形4：P任意色，S為黑，N是P的左孩子，S的右孩子SR為紅，S的左孩子任意（或者是N是P的右孩子，S
的左孩子為紅，S的右孩子任意）。
操作：SR（SL）改為黑，P改為黑，S改為P的顏色，P、S變換--這里相對應于AVL中的右右中的旋轉（或
者是AVL中的左左旋轉），結束。
解析：P、S旋轉有變色，等于給N這邊加了一個黑節(jié)點，P位置（是位置而不是P）的顏色不變，S這邊少
了一個黑節(jié)點；SR有紅變黑，S這邊又增加了一個黑節(jié)點；這樣一來又恢復了平衡，結束。
情形5：P任意色，S為黑，N是P的左孩子，S的左孩子SL為紅，S的右孩子SR為黑（或者N是P的有孩子，S
的右孩子為紅，S的左孩子為黑）。
操作：SL（或SR）改為黑，S改為紅，SL（SR）、S變換；此時就回到了情形4，SL（SR）變成了黑S，S變
成了紅SR（SL），做情形4的操作即可，這兩次變換，其實就是對應AVL的右左的兩次旋轉（或者是AVL的
左右的兩次旋轉）。
解析：這種情況如果你按情形4的操作的話，由于SR本來就是黑色，你無法彌補由于P、S的變換（旋轉）
給S這邊造成的損失！所以我沒先對S、SL進行變換之后就變?yōu)榍樾?的情況了，何樂而不為呢？
好了，這五種情況都討論完了，我想強調的是：注意哪些分方向的情況，每個分方向的情形就兩種情況
，不要搞迷了！下邊我寫的代碼，不用關心是什么方向，我主要是用一個指針數組即child[2]，0代表左
，1代表右，進行兩個節(jié)點的變換（旋轉）的時候只需向conversion(&T,direction);傳入父節(jié)點指針的
地址及子節(jié)點在父節(jié)點的方位（0或1）；有興趣可以看代碼.
歡迎大家留言指正哦^_^
下邊貼上我的C代碼：
簡介：主要是用遞歸實現插入、刪除，回溯時檢索并恢復平衡。
復制代碼
? 1 #include <stdio.h>
? 2 #include <stdlib.h>
? 3?
? 4 #define RED 0
? 5 #define BACK 1
? 6?
? 7 typedef int Elemtype;
? 8?
? 9 //定義一個紅黑樹的結點
?10 typedef struct Red_Back_Tree
?11 {
?12 ? ? Elemtype e;
?13 ? ? int color;
?14 ? ? struct Red_Back_Tree * child[2];
?15 }* RBT;
?16?
?17 // ? ?兩個節(jié)點變換函數
?18 void conversion(RBT *T,int direction);
?19?
?20 // ? ?刪除一個節(jié)點的所用函數
?21 int DeleteRBT(RBT *T,Elemtype e); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// ? ?刪除主(接口)函數
?22 int find_replace_point(RBT gogal,RBT *l); ? ? ? ? ? ? ? ? ? ? ? ?// ? ?尋找替代點
?23 int keep_balance_for_delete(RBT *T,int direction); ? ? ? ? ? ? ? ?// ? ?刪除的平衡操作
?24 int do_with_start_point(RBT gogal,RBT *T,int direction); ? ? ? ? ? ? ? ? ? ?// ? ?處理
第一個起始點
?25?
?26 // ? ?插入一個節(jié)點的所用函數
?27 int InsertRBT(RBT *T,Elemtype e); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// ? ?插入接口函數
?28 int _InsertRBT(RBT *T,Elemtype e); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// ? ?插入主函數
?29 int keep_balance_for_insert(RBT *T,int firdirection,Elemtype e);// ? ?插入的平衡操作
?30 RBT create_one_node(Elemtype e); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// ? ?新建一個節(jié)點
?31?
?32?
?33?
?34 void conversion(RBT *T,int direction)
?35 {
?36 ? ? RBT f=(*T),s=f->child[direction],ss=s->child[!direction];
?37?
?38 ? ? f->child[direction]=ss;
?39 ? ? s->child[!direction]=f;
?40 ? ? *T=s;
?41 }
?42?
?43 //★★★★★★★★★★★★★★★★★刪除操作★★★★★★★★★★★★★★★★★★★★★
★★★★★★
?44?
?45 int do_with_start_point(RBT gogal,RBT *T,int direction)
?46 {
?47 ? ? gogal->e=(*T)->e;
?48 ? ? if(BACK==((*T)->color))
?49 ? ? {
?50 ? ? ? ? if(NULL!=(*T)->child[direction])
?51 ? ? ? ? {
?52 ? ? ? ? ? ? (*T)->e=(*T)->child[direction]->e;
?53 ? ? ? ? ? ? free((*T)->child[direction]);
?54 ? ? ? ? ? ? (*T)->child[direction]=NULL;
?55 ? ? ? ? ? ? return 1;
?56 ? ? ? ? }
?57 ? ? ? ? else
?58 ? ? ? ? {
?59 ? ? ? ? ? ? free((*T));
?60 ? ? ? ? ? ? *T=NULL;
?61 ? ? ? ? ? ? return 0;
?62 ? ? ? ? }
?63 ? ? }
?64 ? ? else
?65 ? ? {
?66 ? ? ? ? free((*T));
?67 ? ? ? ? (*T)=NULL;
?68 ? ? ? ? return 1;
?69 ? ? }
?70 }
?71?
?72 int keep_balance_for_delete(RBT *T,int direction)
?73 {
?74 ? ? RBT p=(*T),b=p->child[!direction];
?75 ? ??
?76 ? ? if(RED==b->color)
?77 ? ? {
?78 ? ? ? ? p->color=RED;
?79 ? ? ? ? b->color=BACK;
?80 // ? ? ? ?conversion(&p,!direction);//很恐怖的一個寫法，偶然中發(fā)現：這里傳的地址是假的!
不是T!!
?81 // ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?考我怎么這么傻逼!!如果不是及時發(fā)現，到調試時將是
無限恐怖
?82 // ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?將是一個巨大的隱藏的BUG!!!將會帶來巨大的麻煩!!!
?83 ? ? ? ? conversion(T,!direction);
?84 ? ? ? ? return keep_balance_for_delete(&((*T)->child[direction]),direction);
?85 ? ? }
?86 ? ? else if(BACK==p->color && BACK==b->color &&?
?87 ? ? ? ? (NULL==b->child[0] || BACK==b->child[0]->color) &&?
?88 ? ? ? ? (NULL==b->child[1] || BACK==b->child[1]->color)) ? ?//這里感覺不美，就一次為
NULL卻每次要
?89 ? ? { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//判斷是否為NULL，不美……
?90 ? ? ? ? b->color=RED;
?91 ? ? ? ? return ? ?0;?
?92 ? ? }
?93 ? ? else if(RED==p->color &&?
?94 ? ? ? ? (NULL==b->child[0] || BACK==b->child[0]->color) &&
?95 ? ? ? ? (NULL==b->child[1] || BACK==b->child[1]->color))
?96 ? ? {
?97 ? ? ? ? p->color=BACK;
?98 ? ? ? ? b->color=RED;
?99 ? ? ? ? return 1;
100 ? ? }
101 // ? ?第一次調試
102 // ? ?調試原因：由于刪除0點未按預料的操作應該是情況④，卻按⑤操作
103 // ? ?錯誤的地方：RED==b->child[!direction] ! 丟了->color 這個錯誤我上邊錯了幾次，不過
編譯器報錯改了過來
104 // ? ?這次的編譯器不報錯，看代碼也看不錯來，最后追究到這里，一一對照才發(fā)現!!!
105 // ? ?else if(BACK==b->color && (NULL!=b->child[!direction] && RED==b->child[!
direction]))
106 ? ? else if(BACK==b->color && (NULL!=b->child[!direction] && RED==b->child[!
direction]->color))
107 ? ? {
108 ? ? ? ? b->color=p->color;
109 ? ? ? ? p->color=BACK;
110 ? ? ? ? b->child[!direction]->color=BACK;
111 ? ? ? ? conversion(T,!direction);
112 ? ? ? ? return 1;
113 ? ? }
114 ? ? else
115 ? ? {
116 ? ? ? ? b->child[direction]->color=p->color;
117 ? ? ? ? p->color=BACK;
118 ? ? ? ? conversion(&(p->child[!direction]),direction);//這里的p寫的才算不錯!即p也(*T)都
行，一樣!
119 ? ? ? ? conversion(T,!direction);
120 ? ? ? ? return 1;
121 ? ? }
122?
123 }
124?
125 int find_replace_point(RBT gogal,RBT *l)
126 {
127 ? ? if(NULL!=(*l)->child[0])
128 ? ? {
129 ? ? ? ? if(find_replace_point(gogal,&(*l)->child[0])) ? ?return 1;
130 ? ? ? ? return keep_balance_for_delete(l,0);
131 ? ? ? ? //...
132 ? ? }
133 // ? ?第二次調試---其實沒F5,F10,F11，根據結果猜測，到這里看看還真是的!
134 // ? ?調試原因：刪除0好了，刪除1又錯了---2不見了，1還在
135 // ? ?錯誤的地方：就在這里，找到替代點，卻沒有“替代”，這等于把替代點刪了...
136 // ? ? ? ? ? ? ? ?這里很明顯，gogal這個刪除點指針根本就沒用...我當時忘了吧!!修改如下!
137 // ? ?else ? ?//替代點為起始點
138 // ? ?{
139 // ? ? ? ?return do_with_start_point(l,1);
140 // ? ?}
141 ? ? else
142 ? ? {
143 ? ? ? ? return do_with_start_point(gogal,l,1);
144 ? ? }
145 }
146?
147 int DeleteRBT(RBT *T,Elemtype e)
148 {
149 ? ? if(!(*T)) ? ?return -1;
150 ? ? else if(e>(*T)->e)
151 ? ? {
152 ? ? ? ? if(DeleteRBT(&((*T)->child[1]),e)) ? ?return 1;
153 ? ? ? ? return keep_balance_for_delete(T,1);
154 ? ? ? ? //...
155 ? ? }
156 ? ? else if(e<(*T)->e)
157 ? ? {
158 ? ? ? ? if(DeleteRBT(&((*T)->child[0]),e)) ? ?return 1;
159 ? ? ? ? return keep_balance_for_delete(T,0);
160 ? ? ? ? //...
161 ? ? }
162 ? ? else
163 ? ? {
164 ? ? ? ? if(NULL!=(*T)->child[1]) ? ?//真正的刪除點不是起始點，需找替代點
165 ? ? ? ? {
166 ? ? ? ? ? ? if(find_replace_point((*T),&((*T)->child[1]))) ? ?return 1;
167 ? ? ? ? ? ? return keep_balance_for_delete(T,1);
168 ? ? ? ? ? ? //...
169 ? ? ? ? }
170 ? ? ? ? else ? ?//真正的刪除點就是起始點
171 ? ? ? ? {
172 ? ? ? ? ? ? return do_with_start_point((*T),T,0);
173 ? ? ? ? }
174 ? ? }
175 }
176 //★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
★★★★★★
177?
178?
179 //★★★★★★★★★★★★★★★★★★★插入操作★★★★★★★★★★★★★★★★★★★
★★★★★★
180?
181 RBT create_one_node(Elemtype e)
182 {
183 ? ? RBT p=(RBT)malloc(sizeof(struct Red_Back_Tree));
184 ? ? p->e=e; ? ?p->color=RED;
185 ? ? p->child[0]=p->child[1]=NULL;
186 ? ? return p;
187 }
188?
189 int keep_balance_for_insert(RBT *T,int firdirection,Elemtype e)
190 {
191 ? ? RBT p=(*T)->child[firdirection],u=(*T)->child[!firdirection];
192 ? ? int secdirection=( (e>p->e) ? 1 : 0 ); ? ?// ? ?查處第二個方向
193 ? ??
194 ? ? if(NULL!=u && RED==u->color) ? ?/*****③叔節(jié)點為紅色*****/ ? ?
195 ? ? {
196 ? ? ? ? p->color=BACK;
197 ? ? ? ? u->color=BACK;
198 ? ? ? ? (*T)->color=RED;
199 ? ? ? ? return 1; ? ?//繼續(xù)...
200 ? ? }
201 ? ? else ? ? ? ? ? ? ? ? ? ? ? ? ? ?/*****④叔節(jié)點為黑色*****/ ? ?
202 ? ? {
203 ? ? ? ? if(firdirection!=secdirection) ? ?conversion(&((*T)->child
[firdirection]),secdirection);
204 ? ? ? ? (*T)->color=RED; ? ?(*T)->child[firdirection]->color=BACK;
205 ? ? ? ? conversion(T,firdirection);
206 ? ? ? ? return 0;
207 ? ? }
208 }
209?
210 int _InsertRBT(RBT *T,Elemtype e)
211 {
212 ? ? int info=0;
213 ? ? if(NULL==(*T)) ? ? ? ? ? ? ? ? ? ?/*****①插入到根節(jié)點*****/ ? ? ? ?//這里只是包含
這種情況
214 ? ? {
215 ? ? ? ? *T=create_one_node(e);
216 ? ? ? ? (*T)->color=RED;
217 ? ? ? ? info=1;
218 ? ? }
219 ? ? else if(e>((*T)->e))
220 ? ? {
221 ? ? ? ? info=_InsertRBT(&(*T)->child[1],e);
222 ? ? ? ? if(info<1) ? ?return info;
223 ? ? ? ? else if(info==1) ? ? ? ? ? ?/*****②父節(jié)點為黑******/
224 ? ? ? ? {
225 ? ? ? ? ? ? if(BACK==((*T)->color)) ? ?info--;
226 ? ? ? ? ? ? else ? ?info++;
227 ? ? ? ? }
228 ? ? ? ? else
229 ? ? ? ? {
230 ? ? ? ? ? ? info=keep_balance_for_insert(T,1,e);
231 ? ? ? ? }
232 ? ? ? ??
233 ? ? }
234 ? ? else if(e<((*T)->e))
235 ? ? {
236 ? ? ? ? info=_InsertRBT(&((*T)->child[0]),e);
237 ? ? ? ? if(info<1) ? ?return info;
238 ? ? ? ? else if(info==1) ? ?
239 ? ? ? ? {
240 ? ? ? ? ? ? if(BACK==((*T)->color)) ? ?info--;
241 ? ? ? ? ? ? else ? ?info++;
242 ? ? ? ? }
243 ? ? ? ? else
244 ? ? ? ? {
245 ? ? ? ? ? ? info=keep_balance_for_insert(T,0,e);
246 ? ? ? ? }
247 ? ? ? ??
248 ? ? }
249 ? ? else ? ?return info=-1;
250 ? ??
251 ? ? return info;
252 }
253?
254 int InsertRBT(RBT *T,Elemtype e) ? ?//插入節(jié)點函數返回值： -1->改點已存在 ?0->成功插入
255 {
256 ? ? int info=0; ? ? ? ?// ? ?info: ?-1->已存在 0->結束 1->回溯到父節(jié)點 2->回溯到祖節(jié)點
257 ? ??
258 //2011年11月30日9:13:47 昨天晚上最后又想來這里這個if可以不要即可，也就是把它也放到
_InsertRBT
259 //內處理，在InsertRBT中有個判斷即可!即改成下邊的寫法!
260 // ? ?if(NULL==(*T)) ? ? ? ? ? ? ? ? ? ?/*****①插入到根節(jié)點*****/
261 // ? ?{
262 // ? ? ? ?*T=create_one_node(e);
263 // ? ? ? ?(*T)->color=BACK;
264 // ? ?}
265 // ? ?else ? ? ? ? ? ?
266 // ? ?{
267 // ? ? ? ?info=_InsertRBT(T,e); ? ?// ? ?經過再三思考，這里info的返回值只可能為：-1 ?0 ?
1
268 // ? ? ? ?if(info>0) ? ?(*T)->color=BACK,info=0; ? ?// ? ?查看根節(jié)點是否為紅
269 // ? ?}
270?
271 ? ? info=_InsertRBT(T,e);
272 ? ? if(info==1) ? ?(*T)->color=BACK,info=0; ? ?
273 ? ? // ? ?為了防止根結點變?yōu)榧t，它其實是處理了兩種情況的后遺癥
274 // ? ?分別是：③情況回溯上來，根節(jié)點變紅 ?①情況插入點即為根節(jié)點，為紅
275 // ? ?這里沒有直接把根結點變黑，主要是為了與_InsertRBT保持一致的寫法，其實都行!
276 ? ? return info;
277 }
278 //★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
★★★★★★
279?
280?
281 //******************JUST FOR TEST********************//
282 RBT queue[1000];
283 void print(RBT cur)
284 {
285 ? ? int front=0,rear=0;
286 ? ? int count=1,temp=0;
287?
288 ? ? if(NULL==cur) ? ?
289 ? ? {
290 ? ? ? ? printf("NULL\n");
291 ? ? ? ? return ;
292 ? ? }
293?
294 ? ? queue[rear]=cur;
295 ? ? while(front<=rear)
296 ? ? {
297 ? ? ? ? cur=queue[front++]; ? ?count--;
298 ? ? ? ? if(NULL!=cur->child[0]) ? ?queue[++rear]=cur->child[0],temp++;
299 ? ? ? ? if(NULL!=cur->child[1]) ? ?queue[++rear]=cur->child[1],temp++;
300?
301 ? ? ? ? printf("%d color->",cur->e);
302 ? ? ? ? if(BACK==cur->color) ? ?printf("BACK |");
303 ? ? ? ? else ? ?printf("RED ?|");
304 ? ? ? ??
305 ? ? ? ? if(0==count)
306 ? ? ? ? {
307 ? ? ? ? ? ? count=temp;
308 ? ? ? ? ? ? temp=0;
309 ? ? ? ? ? ? printf("\n");
310 ? ? ? ? }
311 ? ? }
312 }
313 //*****************************************************//
314?
315 //*****************DEAR MAIN***************************//
316 int main()
317 {
318 ? ? RBT T=NULL;
319 ? ? int i,nodenum=100;
320 ? ??
321 ? ? print(T);
322 ? ? printf("\n");
323?
324 ? ? printf("\n插入操作\n");
325 ? ? for(i=0;i<nodenum;i++)
326 ? ? {
327 ? ? ? ? InsertRBT(&T,i);
328 ? ? ? ? printf("插入%d\n",i);
329 ? ? ? ? print(T);
330 ? ? ? ? printf("\n");
331 ? ? }
332?
333 // ? ?print(T);
334 ? ? printf("\n刪除操作:\n");
335?
336 ? ? for(i=0;i<nodenum;i++)
337 ? ? {
338 ? ? ? ? DeleteRBT(&T,i);
339 ? ? ? ? printf("刪除%d\n",i);
340 ? ? ? ? print(T);
341 ? ? ? ? printf("\n");
342 ? ? }
343?
344 ? ? return 0;
345 }
========
總結
- 上一篇： 图解Oracle dump 命令初步
- 下一篇： java异常处理学习总结