摘要:
本章介紹了二叉查找樹的概念及操作。主要内容包括二叉查找樹的性質,如何在二叉查找樹中查找最大值、最小值和給定的值,如何找出某一個元素的前驅和後繼,如何在二叉查找樹中進行插入和删除操作。在二叉查找樹上執行這些基本操作的時間與樹的高度成正比,一棵随機構造的二叉查找樹的期望高度為O(lgn),進而基本動态集合的操作平均時間為θ(lgn)。
1、二叉查找樹
二叉查找樹是按照二叉樹結構來組織的,是以可以用二叉連結清單結構表示。二叉查找樹中的關鍵字的存儲方式滿足的特征是:設x為二叉查找樹中的一個結點。如果y是x的左子樹中的一個結點,則key[y]≤key[x]。如果y是x的右子樹中的一個結點,則key[x]≤key[y]。根據二叉查找樹的特征可知,采用中根周遊一棵二叉查找樹,可以得到樹中關鍵字有小到大的序列。一棵二叉樹查找及其中根周遊結果如下圖所示:
書中給出了一個定理:如果x是一棵包含n個結點的子樹的根,則其中根周遊運作時間為θ(n)。
問題:二叉查找樹性質與最小堆之間有什麼差別?能否利用最小堆的性質在O(n)時間内,按序輸出含有n個結點的樹中的所有關鍵字?
2、查詢二叉查找樹
二叉查找樹中最常見的操作是查找樹中的某個關鍵字,除了基本的查詢,還支援最大值、最小值、前驅和後繼查詢操作,書中就每種查詢進行了詳細的講解。
(1)查找SEARCH
在二叉查找樹中查找一個給定的關鍵字k的過程與二分查找很類似,根據二叉查找樹在的關鍵字存放的特征,很容易得出查找過程:首先是關鍵字k與樹根的關鍵字進行比較,如果k大比根的關鍵字大,則在根的右子樹中查找,否則在根的左子樹中查找,重複此過程,直到找到與遇到空結點為止。例如下圖所示的查找關鍵字13的過程:(查找過程每次在左右子樹中做出選擇,減少一半的工作量)
書中給出了查找過程的遞歸和非遞歸形式的僞代碼:
TREE_SEARCH(x,k)
if x=NULL or k=key[x]
then return x
if(k then return TREE_SEARCH(left[x],k)
else
then return TREE_SEARCH(right[x],k)
View Code
ITERATIVE_TREE_SEARCH(x,k)
while x!=NULL and k!=key[x]
do if k then x=left[x]
else
then x=right[x]
return x
View Code
(2)查找最大關鍵字和最小關鍵字
根據二叉查找樹的特征,很容易查找出最大和最小關鍵字。查找二叉樹中的最小關鍵字:從根結點開始,沿着各個節點的left指針查找下去,直到遇到NULL時結束。如果一個結點x無左子樹,則以x為根的子樹中,最小關鍵字就是key[x]。查找二叉樹中的最大關鍵字:從根結點開始,沿着各個結點的right指針查找下去,直到遇到NULL時結束。書中給出了查找最大最小關鍵字的僞代碼:
TREE_MINMUM(x)
while left[x] != NULL
do x=left[x]
return x
TREE_MAXMUM(x)
while right[x] != NULL
do x= right[x]
return x
View Code
(3)前驅和後繼
給定一個二叉查找樹中的結點,找出在中序周遊順序下某個節點的前驅和後繼。如果樹中所有關鍵字都不相同,則某一結點x的前驅就是小于key[x]的所有關鍵字中最大的那個結點,後繼即是大于key[x]中的所有關鍵字中最小的那個結點。根據二叉查找樹的結構和性質,不用對關鍵字做任何比較,就可以找到某個結點的前驅和後繼。
查找前驅步驟:先判斷x是否有左子樹,如果有則在left[x]中查找關鍵字最大的結點,即是x的前驅。如果沒有左子樹,則從x繼續向上執行此操作,直到遇到某個結點是其父節點的右孩子結點。例如下圖查找結點7的前驅結點6過程:
查找後繼步驟:先判斷x是否有右子樹,如果有則在right[x]中查找關鍵字最小的結點,即使x的後繼。如果沒有右子樹,則從x的父節點開始向上查找,直到遇到某個結點是其父結點的左兒子的結點時為止。例如下圖查找結點13的後繼結點15的過程:
書中給出了求x結點後繼結點的僞代碼:
TREE_PROCESSOR(x)
if right[x] != NULL
then return TREE_MINMUM(right(x))
y=parent[x]
while y!= NULL and x ==right[y]
do x = y
y=parent[y]
return y
View Code
定理:對一棵高度為h的二叉查找,動态集合操作SEARCH、MINMUM、MAXMUM、SUCCESSOR、PROCESSOR等的運作時間均為O(h)。
3、插入和删除
插入和删除會引起二叉查找表示的動态集合的變化,難點在在插入和删除的過程中要保持二叉查找樹的性質。插入過程相當來說要簡單一些,删除結點比較複雜。
(1)插入
插入結點的位置對應着查找過程中查找不成功時候的結點位置,是以需要從根結點開始查找帶插入結點位置,找到位置後插入即可。下圖所示插入結點過程:
書中給出了插入過程的僞代碼:
TREE_INSERT(T,z)
y = NULL;
x =root[T]
while x != NULL
do y =x
if key[z] < key[x]
then x=left[x]
else x=right[x]
parent[z] =y
if y=NULL
then root[T] =z
else if key[z]>key[y]
then keft[y] = z
else right[y] =z
View Code
插入過程運作時間為O(h),h為樹的高度。
(2)删除
從二叉查找樹中删除給定的結點z,分三種情況讨論:
<1>結點z沒有左右子樹,則修改其父節點p[z],使其為NULL。删除過程如下圖所示:
<2>如果結點z隻有一個子樹(左子樹或者右子樹),通過在其子結點與父節點建立一條鍊來删除z。删除過程如下圖所示:
<3>如果z有兩個子女,則先删除z的後繼y(y沒有左孩子),在用y的内容來替代z的内容。
書中給出了删除過程的僞代碼:
TREE_DELETE(T,z)
if left[z] ==NULL or right[z] == NULL
then y=z
else y=TREE_SUCCESSOR(z)
if left[y] != NULL
then x=left[y]
else x=right[y]
if x!= NULL
then parent[x] = parent[y]
if p[y] ==NULL
then root[T] =x
else if y = left[[prarnt[y]]
then left[parent[y]] = x
else right[parent[y]] =x
if y!=z
then key[z] = key[y]
copy y's data into z
return y
View Code
定理:對高度為h的二叉查找樹,動态集合操作INSERT和DELETE的運作時間為O(h)。
4、随機構造二叉查找樹
二叉查找上各種基本操作的運作時間都是O(h),h為樹的高度。但是在元素插入和删除過程中,樹的高度會發生改變。如果n個元素按照嚴格增長的順序插入,那個構造出的二叉查找樹的高度為n-1。例如按照先後順序插入7、15、18、20、34、46、59元素構造二叉查找樹,二叉查找樹結構如下所示:
1、前言:
接着學習動态規劃方法,最優二叉查找樹問題。如果在二叉樹中查找元素不考慮機率及查找不成功的情況下,可以采用紅黑樹或者平衡二叉樹來搜尋,這樣可以在O(lgn)時間内完成。而現實生活中,查找的關鍵字是有一定的機率的,就是說有的關鍵字可能經常被搜尋,而有的很少被搜尋,而且搜尋的關鍵字可能不存在,為此需要根據關鍵字出現的機率建構一個二叉樹。比如中文輸入法字庫中各詞條(單字、詞組等)的先驗機率,針對使用者習慣可以自動調整詞頻——所謂動态調頻、高頻先現原則,以減少使用者翻查次數,使得經常用的詞彙被放置在前面,這樣就能有效地加快查找速度。這就是最優二叉樹所要解決的問題。
2、問題描述
給定一個由n個互異的關鍵字組成的有序序列K={k1<k2<k3<,……,<kn}和它們被查詢的機率P={p1,p2,p3,……,pn},要求構造一棵二叉查找樹T,使得查詢所有元素的總的代價最小。對于一個搜尋樹,當搜尋的元素在樹内時,表示搜尋成功。當不在樹内時,表示搜尋失敗,用一個“虛葉子節點”來标示搜尋失敗的情況,是以需要n+1個虛葉子節點{d0<d1<……<dn},對于應di的機率序列是Q={q0,q1,……,qn}。其中d0表示搜尋元素小于k1的失敗結果,dn表示搜尋元素大于kn的失敗情況。di(0<i<n)表示搜尋節點在ki和k(i+1)之間時的失敗情況。是以有如下公式:
由每個關鍵字和每個虛拟鍵被搜尋的機率,可以确定在一棵給定的二叉查找樹T内一次搜尋的期望代價。設一次搜尋的實際代價為檢查的節點個數,即在T内搜尋所發現的節點的深度加上1。是以在T内一次搜尋的期望代價為:
需要注意的是:一棵最優二叉查找樹不一定是一棵整體高度最小的樹,也不一定總是把最大機率的關鍵字放在根部。
(3)動态規劃求解過程
1)最優二叉查找樹的結構
如果一棵最優二叉查找樹T有一棵包含關鍵字ki,……,kj的子樹T',那麼這棵子樹T’對于對于關鍵字ki,……kj和虛拟鍵di-1,……,dj的子問題也必定是最優的。
2)一個遞歸解
定義e[i,j]為搜尋一棵包含關鍵字ki,……,kj的最優二叉查找樹的期望代價,則分類讨論如下:
當j=i-1時,說明此時隻有虛拟鍵di-1,故e[i,i-1] = qi-1
當j≥i時,需要從ki,……,kj中選擇一個跟kr,然後用關鍵字ki,……,kr-1來構造一棵最優二叉查找樹作為左子樹,用關鍵字kr+1,……,kj來構造一棵最優二叉查找樹作為右子樹。定義一棵有關鍵字ki,……,kj的子樹,定義機率的總和為:
是以如果kr是一棵包含關鍵字ki,……,kj的最優子樹的根,則有:
故e[i,j]重寫為:
最終的遞歸式如下:
3)計算一棵最優二叉查找樹的期望搜尋代價
将e[i,j]的值儲存到一個二維數組e[1..1+n,0..n]中,用root[i,j]來記錄關鍵字ki,……,kj的子樹的根,采用二維數組root[1..n,1..n]來表示。為了提高效率,防止重複計算,需要個二維數組w[1..n+1,0...n]來儲存w(i,j)的值,其中w[i,j] = w[i,j-1]+pj+qj。數組給出了計算過程的僞代碼:
OPTIMAL_BST(p,q,n)
for i=1 to n+1 //初始化e和w的值
do e[i,i-1] = qi-1;
w[i,i-1] = qi-1;
for l=1 to n
do for i=1 to n-l+1
do j=i+l-1;
e[i,j] = MAX;
w[i,j] = w[i,j-1]+pj+qj;
for r=i to j
do t=e[i,r-1]+e[r+1,j]+w[i,j]
if t then e[i,j] = t;
root[i,j] = r;
return e and root;
View Code
4)構造一棵最優二叉查找樹
根據地第三步中得到的root表,可以遞推出各個子樹的根,進而可以建構出一棵最優二叉查找樹。從root[1,n]開始向下遞推,一次找出樹根,及左子樹和右子樹。
4、程式設計實作
針對一個具體的執行個體程式設計實作,現在有5個關鍵字,其出現的機率P={0.15,0.10,0.05,0.10,0.20},查找虛拟鍵的機率q={0.05,0.10,0.05,0.05,0.05,0.10}。采用C++語言是實作如下:
#include
using namespace std;
const int N=5;
const int MAX=9999999;
float p[N+1]={0,0.15,0.10,0.05,0.1,0.20};
float q[N+1]={0.05,0.10,0.05,0.05,0.05,0.10};
float e[N+2][N+1];
int root[N+1][N+1];
float w[N+2][N+1];
void optimal_bst_search_tree(float p[],float q[],int n)
{
int i;
for(i=1;i<=n+1;i++)
{
e[i][i-1]=q[i-1];
w[i][i-1]=q[i-1];
}
int l,j,r;
for(l=1;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
{
j=i+l-1;
e[i][j]=MAX;
w[i][j]=w[i][j-1]+p[j]+q[j];
for(r=i;r<=j;r++)
{
double t=e[i][r-1]+e[r+1][j]+w[i][j];
if(t {
e[i][j]=t;
root[i][j]=r;
}
}
}
}
}
void print_root()
{
int i,j;
cout<<"各子樹的根:"< for(i=1;i<=N;i++)
{
for(j=1;j<=N;j++)
cout< cout< }
}
void construct_optimal_bst(int i,int j)
{
if(i<=j)
{
int r=root[i][j];
cout< construct_optimal_bst(i,r-1);
construct_optimal_bst(r+1,j);
}
}
void print_bst(int i,int j)
{
if(i==1&&j==N)
cout<<"root is "< if(i {
int r=root[i][j];
if(i!=r)
cout<<"left child root "< print_bst(i,root[i][j]-1);
if(j!=r)
cout<<"right child root "< print_bst(root[i][j]+1,j);
}
}
int main()
{
optimal_bst_search_tree(p,q,N);
print_root();
cout<<"構造的最優二叉樹:"< construct_optimal_bst(1,5);
cout< print_bst(1,5);
}
View Code