??? 這次的問題來自《數據結構與算法分析(C++描述)》的習題4.16,如下:

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

4.16? 重做二叉查找樹類以實現懶惰刪除.注意,這將影響所有的例程.特別具有挑戰性的是findMin和findMax,它們現在必須遞歸的完成.

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

??? 這題沒有參考答案,我也不敢保證自己寫的是對的,有不對的地方請指正,謝謝.先做一下說明,首先這只是一般的二叉查找樹,不是AVL樹.其次其中的printTree()函數只是將樹中的結點按升序打印出來,不是像樹的結構那樣打印(可以參見這里的print()函數).最后,我定義的數據結構是在有重復項的情況下使用的.也就是說,每一個結點有一個記錄數據出現次數的成員count(非負整數).當第一次插入某一數據時,count為1,以后每插入一次這一數據則它的count加1.而當某一數據沒有被實際刪除且它的count大于0時,對它的刪除操作就是將它的count減1.當邏輯上被刪除的結點(count值為0的結點)的數目達到實際上存在的總結點數目的一半時,就對二叉查找樹進行真正的刪除操作(delete).

??? 下面在課本中給出的一般二叉查找樹結構(參見書中圖4-16至圖4-28)的基礎上進行修改,得到我們所需要的結構.首先自然是結點的結構,如前所述,需要對結點BinaryNode類增加一個記錄數據出現次數的成員count.而在BSTree類中,我們需要兩個int型的私有成員分別統計樹的總結點數和其中在邏輯上已經被刪除的結點數.接下來是contains(),makeEmpty(),printTree()和insert(),這些都比較簡單.

? ? 我與課本上makeEmpty( BinaryNode * & t )(置空操作)的不同是,我沒有在最后將節點置為NULL,而是在調用這個函數之后將實參置為NULL,不知道這樣做會不會有什么錯誤.對于insert函數,我們可以看到這種結構的好處,對于那些僅在邏輯上被刪除的數據,重新插入它只需要將count加1并且將delSize減1.

1 template <typename Object>
2 class BSTree
3 {
4 public:
5 BSTree( ){theSize=delSize=0;root=NULL;}
6 ~BSTree( )
7 {
8 makeEmpty(root);
9 theSize=delSize=0;
10 }
11
12 bool contains( const Object & x ) const//是否包含某值
13 {return contains(x,root);}
14 bool isEmpty( ) const//是否為空
15 {return theSize-delSize==0;}
16 void printTree( ) const//打印樹
17 {printTree(root);}
18
19 void makeEmpty( )//置空
20 {
21 makeEmpty(root);
22 theSize=delSize=0;root=NULL;
23 }
24 void insert( const Object & x )//插入值
25 {insert(x,root);}
26
27 private:
28 struct BinaryNode
29 {
30 Object element;//Object類型的值
31 BinaryNode *left;//左子樹
32 BinaryNode *right;//右子樹
33 int count; //計數
34
35 BinaryNode( const Object & theElement, BinaryNode *lt, BinaryNode *rt ,int c=1)//第一次插入值為1
36 : element( theElement ), left( lt ), right( rt ), count(c) { }
37 };
38
39 BinaryNode *root;//根結點
40 int theSize;
41 int delSize;
42
43 void insert( const Object & x, BinaryNode * & t ) ;
44
45 bool contains( const Object & x, BinaryNode *t ) const;
46 void makeEmpty( BinaryNode * & t );
47 void printTree( BinaryNode *t ) const
48 {
49 if(t)
50 {
51 printTree(t->left);
52 if(t->count>0)std::cout<<t->element<<" ";
53 printTree(t->right);
54 }
55 }
56 }; 1 template <typename Object>
2 bool BSTree<Object>::contains( const Object & x, BinaryNode *t ) const
3 {
4 if(!t)return false;
5 if(x<t->element)
6 return contains(x,t->left);
7 else if(x>t->element)
8 return contains(x,t->right);
9 else if(t->count>0)
10 return true;
11 else
12 return false;
13 }
14
15 template <typename Object>
16 void BSTree<Object>::makeEmpty( BinaryNode * & t )
17 {
18 if(t)
19 {
20 makeEmpty(t->left);
21 makeEmpty(t->right);
22 delete t;
23 }
24 }
25
26 template <typename Object>
27 void BSTree<Object>::insert( const Object & x, BinaryNode * & t )
28 {
29 if(t==NULL)
30 {
31 ++theSize;
32 t=new BinaryNode(x,NULL,NULL);//count默認為1
33 }
34 else if(x<t->element)
35 insert(x,t->left);
36 else if(x>t->element)
37 insert(x,t->right);
38 else if(t->count++==0)
39 --delSize;//如果count的值原本為0,則將其加1的同時要將delSize減1.
40 }

? ? 接下來是remove操作,現在remove也顯得代價更小,當刪除某項數據時,只需要將它的count減1而不需要從樹真正刪除它.而當它的count為0時,則需要將delSize加1以表示又有一個結點在邏輯上已經被刪除.最后再檢查delSize是否達到了theSize的一半.如果達到,則執行真正的delete操作.

1 template <typename Object>
2 void BSTree<Object>::remove( const Object & x, BinaryNode * & t )
3 {
4 if(t==NULL)return;
5 if(x<t->element)
6 remove(x,t->left);
7 else if(x>t->element)
8 remove(x,t->right);
9 else if(t->count>0&&--(t->count)==0&&(++delSize>=theSize-delSize))
10 //若count大于0,則減1;若減1后為0,則delSize加1;
11 //若delSize達到theSize的一半,則執行delete操作
12 {
13 delete_nodes(root);//真正的刪除操作
14 theSize-=delSize;//更新總結點數
15 delSize=0;//delSize歸零
16 }
17 }

? ? 現在的問題是delete_nodes( BinaryNode * & t )例程的實現,我們要刪除樹中所有count為0的結點.我這里使用了遞歸的方法,如果某個結點不必刪除,那么就繼續對它的左子樹和右子樹執行delete_nodes().回想一般二叉查找樹的刪除,對于葉子結點,直接刪除即可,這在delete_nodes()中也是一樣.而對于只有一個非空子樹的結點,直接刪除后將它的非空子樹"拼接"上即可,但這時需要對拼接上的子樹繼續執行delete_nodes().

? ? 最后就是刪除那些兩個子樹都非空的結點,我們還是在它的右子樹上找到一個值最小的結點(注意:要在count大于0的結點中找),我們假設這個點為min.然后將t的值和count值都替換成min相應的值,同時將min的count值修改為0以保證稍后刪除.最后,繼續對t的左子樹和右子樹執行delete_nodes()操作.這里面一個可能存在的情況是t的右子樹中所有結點的count值都為0,那么我們可以將它的右子樹置空,這樣t就變成了一個只有一個非空子樹的結點.

? ? 在實際的編程中,我覺得比較費腦筋的就是findMin()和findMax()例程.以findMin(BinaryNode *t)為例,首先要找到t中的最小值,然后再升序一步步往上尋找第一個count大于0的結點.我采用的遞歸的方法,這一例程返回bool值,false表示沒有找到最小值,也就意味著t為空或者t中所有結點的count均為0.而為了保存查找到的最小(最大)結點,我給BSTree類增加了兩個私有成員,兩個BinaryNode *類型的指針min和max.另外,我還提供了兩個公有的函數,分別返回整顆樹的最小和最大值,但是這兩個函數需要在保證整顆樹非空的情況下使用.

1 private:
2 BinaryNode *min;
3 BinaryNode *max;
4
5 template <typename Object>
6 bool BSTree<Object>::findMin( BinaryNode *t )
7 {
8 if(t)
9 {
10 if(findMin(t->left))return true;//在t的左子樹中找到count大于0的點,查找結束.
11 if(t->count>0){min=t;return true;}//找到count大于0的點,查找結束.
12 return findMin(t->right);//否則繼續查找右子樹
13 }
14 return false;//空結點則返回false
15 }
16
17 template <typename Object>
18 bool BSTree<Object>::findMax( BinaryNode *t)
19 {
20 if(t)
21 {
22 if(findMax(t->right))return true;
23 if(t->count>0){max=t;return true;}
24 return findMax(t->left);
25 }
26 return false;
27 }
28
29 template <typename Object>
30 void BSTree<Object>::delete_nodes(BinaryNode * & t )
31 {
32 if(t==NULL)return;//空子樹,do nothing
33 if(t->count==0)//t需要被刪除
34 {
35 if((t->left!=NULL)&&(t->right!=NULL)&&findMin(t->right))
36 //t的兩個子樹均非空,且在它的右子樹中找到了可用的最小結點
37 {
38 t->element=min->element;
39 t->count=min->count;
40 min->count=0;//右子樹中的最小結點即將被刪除
41 delete_nodes(t->left);
42 delete_nodes(t->right);
43 }
44 else
45 {
46 if((t->left!=NULL)&&(t->right!=NULL))
47 //t的右子樹中的所有結點的count均為0,則將其置空.
48 {makeEmpty(t->right);t->right=NULL;}
49 BinaryNode *oldnode=t;
50 t=t->left?t->left:t->right;
51 delete oldnode;
52 if(t!=NULL)delete_nodes(t);//若新的t非空,繼續對它執行刪除操作
53 }
54 }
55 else//t不需要被刪除,繼續在它的子樹中查找
56 {
57 delete_nodes(t->left);
58 delete_nodes(t->right);
59 }
60 }
61
62 public:
63 const Object & findMin( )//返回最小值
64 {
65 if(!findMin(root))
66 std::cerr<<"The tree is Empty!"<<std::endl;
67 return min->element;
68 }
69
70 const Object & findMax( )//返回最大值
71 {
72 if(!findMax(root))
73 std::cerr<<"The tree is Empty!"<<std::endl;
74 return max->element;
75 }

? ? 最后提供我的BSTree.h文件,有不對的地方請指正,謝謝.
? ??BSTree.h

轉載于:https://www.cnblogs.com/heqile/archive/2011/12/08/2280120.html

總結

以上是生活随笔為你收集整理的数据结构和算法分析学习笔记(三)--二叉查找树的懒惰删除(lazy deletion)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。