數據結構與算法分析——C語言描述（第4章樹）

發布時間：9/19/2022 10:11:10 PM

4.1 預備知識
- 4.1.1 樹的實現
- 4.1.2 樹的遍歷及應用
4.2 二叉樹(binary tree)
- 4.2.1 實現
- 4.2.2 表達式樹(expression tree)
  - 構造一棵表達式樹
4.3 查找樹ADT——二叉查找樹
- 平均情形分析
4.4 AVL樹
- 4.4.1 單旋轉
- 4.4.2 雙旋轉
- 4.4.3 函數實現
4.5 伸展樹(splay tree)
- 4.5.1 一個簡單的想法
- 4.5.2 展開(splaying)
4.6 樹的遍歷
4.7 B樹(B-tree)

4.1 預備知識

一棵樹(tree)是一些節點的集合。這個集合可以是空集；若非空，則一棵樹由稱作根(root)的節點\(r\)以及0個或多個非空的（子）樹\(T_1\), …, \(T_k\)組成，這些子樹中每一棵的根都被來自根\(r\)的一條有向的邊(edge)所連接。
從遞歸的定義中可以發現，一棵樹是\(N\)個節點和\(N-1\)條邊的集合。

每一棵子樹的根叫作根\(r\)的兒子(child)，而\(r\)是每一棵子樹的根的父親(parent)。（同理有祖父(grandparent)和孫子(grandchild)關系）
沒有兒子的節點稱為樹葉(leaf)。
具有相同父親的節點稱為兄弟(sibling)。
節點到節點的路徑(path)定義為途徑節點的一個序列，這個路徑的長(length)為該路徑上面的邊的條數。
節點的深度(depth)定義為從根到節點的唯一路徑的長。（根的深度為0）
節點的高(height)定義為節點到一片樹葉的最長路徑的長。
如果存在從\(n_1\)到\(n_2\)的一條路徑，那么\(n_1\)是\(n_2\)的一位祖先(ancestor)，而\(n_2\)是\(n_1\)的一個后裔(descendant)。如果\(n_1≠n_2\)，那么\(n_1\)是\(n_2\)的一位真祖先(proper ancestor)，而\(n_2\)是\(n_1\)的一個真后裔(proper descendant)。

4.1.1 樹的實現

實現樹的一種方法可以是將每個節點的所有兒子都放在樹節點的鏈表中。
樹的節點聲明：

typedef struct TreeNode *PtrToNode;

struct TreeNode
{
	ElementType Element;
	PtrToNode FirstChild;
	PtrToNode NextSibling;
}

4.1.2 樹的遍歷及應用

典型應用——常用操作系統的目錄結構。

遍歷樹的策略：

先序遍歷(preorder traversal)

后序遍歷(postorder traversal)

中序遍歷(inorder traversal)

層序遍歷(level-order traversal)

具體的遍歷方式將在4.6詳細介紹。

4.2 二叉樹(binary tree)

特征：每個節點的兒子都不能多于兩個。
二叉樹的一個性質是平均二叉樹的深度要比\(N\)小的多，平均深度為\(O(\sqrt{N})\)；對于二叉查找樹(binary search tree)，平均深度為\(O(\log{N})\)。（最壞情況下為\(N-1\)）

4.2.1 實現

二叉樹節點聲明：

typedef struct TreeNode *PtrToNode;
typedef struct PtrToNode Tree;

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

特別地，當進行一次插入時，必須調用\(malloc\)創建一個節點。節點可以在調用\(free\)刪除后釋放。

二叉樹實際上就是圖(graph)。

二叉樹的主要用處之一是在編譯器的設計領域。

4.2.2 表達式樹(expression tree)

特征：樹葉是操作數(operand)，其他的節點為操作符(operator)。

中序遍歷：先通過遞歸產生一個帶括號的左表達式，然后打印出在根處的運算符，最后再遞歸地產生一個帶括號的右表達式而得到一個（對兩個括號整體進行運算的）中綴表達式(infix expression)。
后序遍歷：遞歸打印出左子樹、右子樹，然后打印運算符。對于上述例子輸出“a b c * + d e * f + g * +”。
先序遍歷：先打印出運算符，然后遞歸地打印出右子樹和左子樹。對于上述例子輸出“+ + a * b c * + * defg”。（不太常用的前綴(prefix)記法）

構造一棵表達式樹

一次一個符號地讀入表達式（利用棧）

如果符號是操作數，建立一個單節點樹并將一個指向它的指針推入棧中。
如果符號是操作符，從棧中彈出指向兩棵樹\(T_1\)和\(T_2\)的兩個指針（\(T_1\)的先彈出）并形成一棵新的樹，該樹的根就是操作符，它的左、右兒子分別指向\(T_2\)和\(T_1\)。然后將指向這棵新樹的指針壓入棧中。

4.3 查找樹ADT——二叉查找樹

特征：對于樹中的每個節點\(X\)，它的左子樹中所有關鍵字值小于\(X\)的關鍵字值，而它的右子樹中所有關鍵字值大于\(X\)的關鍵字值。
二叉查找樹的類型聲明：

#ifndef _Tree_H

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty( SearchTree T );
Position Find( ElementType X, SearchTree T );
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
SearchTree Delete( ElementType X, SearchTree T );
ElementType Retrieve( Position P );

#endif /* _Tree_H */

/* Place in the implementation file */
struct TreeNode
{
	ElementType Element;
	SearchTree Left;
	SearchTree Right;
}

因為二叉查找樹的平均深度為\(O(\log{N})\)，所以一般不必擔心?？臻g被用盡。

具體函數實現：

 /* Make T empty */
SearchTree
MakeEmpty( SearchTree T )
{
	if( T != NULL )
	{
		MakeEmpty( T->Left );
		MakeEmpty( T->Right );
		free( T );
	}
	return NULL;
}

/* Find X's position in T */
Position
Find( ElementType X, SearchTree T)
{
	if( T == NULL )
		return NULL;
	if( X < T->Element )
		return Find( X, T->Left );
	else
	if( X > T->Element )
		return Find( X, T->Right );
	else
		return T;
}

/* Find min's position in T(recursion)*/
Position
FindMin( SearchTree T )
{
	if( T == NULL )
		return NULL;
	else
	if( T->Left == NULL)
		return T;
	else
		return FindMin( T->Left );
}

/* Find max's position in T(not recursion)*/
Position
FindMax( SearchTree T )
{
	if( T != NULL )
		while( T->Right != NULL )
			T = T->Right;
	return T;
}

/* Insert X in T */
SearchTree
Insert( ElementType X, SearchTree T )
{
	if( T == NULL )
	{
		/* Create and return a one-node tree */
		T = malloc( sizeof( struct TreeNode ) );
		if( T == NULL)
			FatalError( "Out of space!!!" );
		else
		{
			T->Element = X;
			T->Left = T->Right = NULL;
		}
	}
	else
	if( X < T->Element )
		T->Left = Insert( X, T->Left );
	else
	if( X > T->Element )
		T->Right = Insert( X, T->Right );
	/* Else X is in the tree already; we'll do nothing*/
	return T;
}

/* Delete X in T*/
/*
If X is a leaf, delete X directly.
If X has one child, make X's father point to X's child.
If X has two children, find min in right subtree, use it to replace X, and delete the min element.
*/
SearchTree
Delete( ElementType X, SearchTree T )
{
	Positon TmpCell;
	if( T == NULL )
		Error( "Element not found" );
	else
	if( X < T->Element ) /* Go left */
		T->Left = Delete( X, T->Left );
	else
	if( X > T->Element ) /* Go right */
		T->Right = Delete( X, T->Right );
	else /* Found element to be deleted */
	if( T->Left && T->Right ) /* Two children */
	{
		/* Replace with smallest in right subtree */
		TmpCell = FindMin( T->Right );
		T->Element = TmpCell->Element;
		T->Right = Delete( T->Element, T->Right );
	}
	else /* One or zero children*/
	{
		TmpCell = T;
		if( T->Left == NULL) /* Also handles 0 children */
			T = T->Right;
		else if( T->Right == NULL )
			T = T->Left;
		free( TmpCell );
	}
	return T;
}

如果刪除的次數不多，則通常使用的策略是懶惰刪除(lazy deletion)：當一個元素要被刪除時，它仍留在樹中，只是做了個被刪除的記號。

平均情形分析

除MakeEmpty外，所有的操作都是\(O(d)\)的，其中d是包含所訪問的關鍵字的節點的深度。
一棵樹的所有節點的深度的和稱為內部路徑長(internal path length)。
假設所有的樹出現的機會均等，則樹的所有節點的平均深度（平均內部路徑長）為\(O(\log{N})\)。

4.4 AVL樹

AVL(Adelson-Velskii 和 Landis)樹是帶有平衡條件的二叉查找樹。
這個平衡條件必須要容易保持，而且必須保證樹的深度是\(O(\log{N})\)?！笞笥易訕渚哂邢嗤母叨?要求每個節點都必須要有相同高度的左子樹和右子樹。
一棵AVL樹是其每個節點的左子樹和右子樹的高度最多差1的二叉查找樹。（空樹的高度定義為-1）
在AVL樹中插入一個節點可能會破壞AVL樹的特性，所以需要把性質恢復以后才認為這一步插入完成?！D(rotation)
出現不平衡的四種情況（將必須重新平衡的節點叫作\(α\)）：

對\(α\)的左兒子的左子樹進行一次插入。
對\(α\)的左兒子的右子樹進行一次插入。
對\(α\)的右兒子的左子樹進行一次插入。
對\(α\)的右兒子的右子樹進行一次插入。

對于情形1和4，采用單旋轉(single rotation)。
對于情形2和3，采用雙旋轉(double rotation)。

4.4.1 單旋轉

4.4.2 雙旋轉

4.4.3 函數實現

AVL樹的節點聲明：

#ifndef _AvlTree_H

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty( AvlTree T );
Position Find( ElementType X, AvlTree T );
Position FindMin( AvlTree T );
Position FindMax( AvlTree T );
AvlTree Insert( ElementType X, AvlTree T );
AvlTree Delete( ElementType X, AvlTree T );

#endif /* _AvlTree_H */

/* Place in the implementation file */
struct AvlNode
{
	ElementType Element;
	AvlTree Left;
	AvlTree Right;
	int Height;
}

AVL樹本質上還是二叉查找樹，具體函數實現其實大同小異。

具體函數實現：

/* Return one node's height */
static int
Height( Position P )
{
	if( P == NULL )
		return -1;
	else
		return P->Height;
}

/* Insert X in T */
AvlTree
Insert( ElementType X, AvlTree T )
{
	if( T == NULL )
	{
		/* Create and return a one-node tree */
		T = malloc( sizeof( struct AvlNode ) );
		if( T == NULL )
			FatalError( "Out of space!!!");
		else
		{
			T->Element = X; T->Height = 0;
			T->Left = T->Right = NULL;
		}
	}
	else
	if( X < T->Element )
	{
		T->Left = Insert( X, T->Left );
		if( Height( T->Left ) - Height( T->Right ) == 2 )
			if( X < T->Left->Element )
				T = SingleRotateWithLeft( T );
			else
				T = DoubleRotateWithLeft( T );
	}
	else
	if( X > T->Element )
	{
		T->Right = Insert( X, T->Right );
		if( Height( T->Right ) - Height( T->Left ) == 2 )
			if( X > T->Right->Element )
				T = SingleRotateWithRight( T );
			else
				T = DoubleRotateWithRight( T );
	}
	/* Else X is in the tree already; we'll do nothing */
	T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
	return T;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
static Position
SingleRotateWithLeft( Position K2 )
{
	Position K1;
	K1 = K2->Left;
	K2->Left = K1->Right;
	K1->Right = K2;
	K2->Height = Max( Height( K2->Left ), Height( K2->Right ) ) + 1;
	K1->Height = Max( Height( K1->Left ), K2->Right ) + 1;
	return K1; /* New root */
}

/* This function can be called only if K3 has a left child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
static Position
DoubleRotationWithLeft( Position K3 )
{
	/* Rotate between K1 and K2 */
	K3->Left = SingleRotateWithRight( K3->Left );
	/* Rotate between K3 and K2 */
	return SingleRotateWithLeft( K3 );
}

4.5 伸展樹(splay tree)

伸展樹保證從空樹開始任意連續M次對樹的操作最多花費\(O(M\log{N})\)時間。
一般說來，當M次操作的序列總的最壞情形運行時間為\(O(MF(N))\)時，我們就說它的攤還(amortized)運行時間為\(O(F(N))\)。
因此，一棵伸展樹每次操作的攤還代價是\(O(\log{N})\)。

如果任意特定操作可以有最壞時間界\(O(N)\)，而我們仍然要求一個\(O(\log{N})\)的攤還時間界，那么很清楚，只要一個節點被訪問，它就必須被移動，否則，一旦我們發現一個深層的節點，我們家有可能不斷對它進行Find操作。如果這個節點不改變位而每次訪問又花費\(O(N)\)，那么M次訪問將花費\(O(M·N)\)的時間。

伸展樹的基本想法是，當一個節點被訪問后，它就要經過一系列AVL樹的旋轉后放到根上。如果節點過深，那么我們還要求重新構造應具有平衡這棵樹（到某種程度）的作用。

4.5.1 一個簡單的想法

4.5.2 展開(splaying)

4.6 樹的遍歷

中序遍歷(inorder traversal)
后序遍歷(postorder traversal)
先序遍歷(preorder traversal)
層序遍歷(level-order traversal)

4.7 B樹(B-tree)

階為\(M\)的B樹是一棵具有下列結構特性的樹：

樹的根或者是一片樹葉，或者其兒子數在\(2\)和\(M\)之間。
除根外，所有非樹葉節點的兒子數在\(?M/2?\)和\(M\)之間。
所有的樹葉都在相同的深度上。

4階B樹常被稱作2-3-4樹，3階B樹常被稱作2-3樹。
下面舉一棵2-3樹的例子：

B樹的深度最多是\(?\log_{?M/2?}{N}?\)。
B樹實際用于數據庫系統，在那里樹被存儲在物理的磁盤上而不是主存中。
分析指出，一棵B樹將被占滿\(\ln{2}\) = \(69\)%。當一棵樹得到它的第\((M + 1)\)項時，例程不是總去分裂節點，而是搜索能夠接納新兒子的兄弟，此時我們能夠更好地利用空間。

查看全文