樹、二叉樹、二叉查找樹、AVL樹、伸展樹、B-樹

目錄

1.一般的樹（tree）

定義：

實作：

樹的周遊：

2.二叉樹（binary tree）

定義：

實作：

應用：

3.查找樹--二叉查找樹（binary search tree）

定義：

操作：

4.AVL樹（Adelson-Velsky-Landis Tree ）

定義：

單旋轉（single rotation）：

雙旋轉（double rotation）：

5.伸展樹（splay tree）

定義：

展開：

6.樹的周遊

7.B-樹（B-tree）

定義：

應用：

1.一般的樹（tree）

定義：

一棵樹是是N個節點和N-1條邊的集合，其中的一個節點叫做根。

任意節點的深度為從跟到該節點的唯一路徑的長。一棵樹的深度等于它的最深的樹葉的深度。

任意節點的高是從該節點到一片樹葉的最長路徑的長。一棵樹的高等于它的根的高。樹的深度等于樹的高。

實作：

每個節點除資料外，有一個指針指向該節點的第一個兒子，另一個指針指向該節點的下一個兄弟。

typedef struct ThreeNode *PtrToNode;
struct TreeNode
{
	ElementType Element;
	PtrToNode FirstChild;
	PtrToNode NextSibling;
}
           

樹的周遊：

先序周遊(preorder traversal)：先處理根節點，然後處理左右兒子。（使用：作業系統的目錄結構）

中序周遊(Inorder traversal)：先處理左兒子，在處理根節點，最後處理右兒子。（使用：計算表達式樹）

後續周遊(postorder traversal)：先處理左右左右兒子，然後處理根節點。（使用：計算檔案目錄的大小）

注：先序，中序，後續中的先、中、後是對于根而言的。

2.二叉樹（binary tree）

定義：

二叉樹是一棵樹，其中每個節點都不能有多于兩個的兒子。

實作：

節點由資料，和兩個指向左右兒子的指針構成。

typedef struct ThreeNode *PtrToNode;
typedef struct ThreeNode *Tree;

struct TreeNode
{
	ElementType Element;
	Tree Left;
	Tree Right;
}
           

應用：

表達式樹：樹葉是操作數（常量和變量），其他節點是操作符（+-*/）。

3.查找樹--二叉查找樹（binary search tree）

定義：

對于樹中的每個節點X，它的左子樹中所有關鍵字小于X的關鍵字，它的右子樹中所有關鍵字大于X的關鍵字。

操作：

MakeEmpty()

Find()

FindMin()

FindMax()

Insert()

Delete()

二叉查找樹，任意節點的期望深度為O(logN)

上述操作的平均運作時間都是O(logN)

4.AVL樹（Adelson-Velsky-Landis Tree ）

定義：

AVL樹是帶有平衡條件的二叉查找樹，其每個節點的左子樹和右子樹的高度最多差1。

單旋轉（single rotation）：

對X節點的左兒子的左子樹進行一次插入；

對X節點的右兒子的右子樹進行一次插入。

雙旋轉（double rotation）：

對X節點的左兒子的右子樹進行一次插入；（先右旋轉再左旋轉）

對X節點的右兒子的左子樹進行一次插入。（先左旋轉再右旋轉）

5.伸展樹（splay tree）

定義：

一種放棄平衡條件，允許樹有任意深度的自調整(self-adjusting)樹。

當一個節點被通路後，它就要經過一系列AVL樹的旋轉被放到根上。

它保證從空樹開始任意連續M次對樹的操作最多花費O(MlogN)時間。一棵伸展樹每次操作的攤還代價是O(logN)

展開：

• 之字形(zig-zag):

     雙旋轉

• 一字型(zig-zig):

    左右樹變換。

6.樹的周遊

• 按照排序的順序列出所有的關鍵字（中序周遊）：

void PrintTree(SearchTree T)
{
	if(T!=NULL)
	{
	PrintTree(T->Left);
	PrintElement(T->Element);
	PrintTree(T->Right);
	}
}
           

• 計算一個節點的高度（後續周遊）：

int Height(Tree T)
{
	if(T==NULL)
	   return -1;
	else
	    return 1+Max(Height(T->Left),Height(T->Right));   

}
           

• 先序周遊：

利用節點深度标志每一個節點。

• 層序周遊(level-order tracersal):

所有深度為D的節點要再深度為D+1的節點之前處理。（使用隊列實作）

7.B-樹（B-tree）

定義：

階為M的B-樹，

樹的根或者是一片樹葉，或者其兒子數再2和M之間。

除根外，所有非樹葉節點的兒子數在[M/2]和M之間。

所有的樹葉都在相同的深度上。

所有的資料存儲在樹葉上。

在每一個内部節點上皆含有指向該節點各兒子指針P1，P2.....PM

在每一個内部節點上皆含有代表子樹P1，P2.....PM中發現的最小關鍵字的值k1,k2......km

對于每一節點，其子樹P1中所有關鍵字都小于子樹P2的關鍵字，依次類推。

在非根數葉中關鍵字的個數也在[M/2]和M之間。

應用：

資料庫系統。