这次的问题来自《数据结构与算法分析(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的点,保存在min中,查找结束.
12 //否则继续查找右子树
13         return findMin(t->right);
14     }
15     return false;//空结点则返回false
16 }
17 
18 template <typename Object>
19 bool BSTree<Object>::findMax( BinaryNode *t)
20 {
21     if(t)
22     {
23         if(findMax(t->right))return true;
24         if(t->count>0){max=t;return true;}
25         return findMax(t->left);
26     }
27     return false;
28 }
29 
30 public:
31     const Object & findMin( )//返回最小值
32     {
33         if(!findMin(root))
34             std::cerr<<"The tree is Empty!"<<std::endl;
35         return min->element;
36     }
37 
38     const Object & findMax( )//返回最大值
39     {
40         if(!findMax(root))
41             std::cerr<<"The tree is Empty!"<<std::endl;
42         return max->element;
43     }

    最后提供我的BSTree.h文件,有不对的地方请指正,谢谢.
    BSTree.h

作者: Barryhe 发表于 2011-12-08 14:39 原文链接

评论: 1　查看评论　发表评论

最新新闻：
· 关于无人驾驶汽车的一些“天方夜谭”式思考(2011-12-08 15:26)
· 苹果iPhone5新参数曝光：四核处理器720p屏(2011-12-08 15:24)
· 社交网络危险论？(2011-12-08 15:19)
· 传诺基亚考虑出售奢侈手机品牌Vertu(2011-12-08 15:14)
· 视频：国外黑客演示完美破解WP7主题(2011-12-08 15:13)

编辑推荐：基于Socket实现的最简单的Web服务器

网站导航：博客园首页  我的园子  新闻  闪存  博问  知识库

题目来自《数据结构题集(C语言版)》,如下:

6.37 试利用栈的基本操作写出先序遍历(二叉树)的非递归算法.

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

先序遍历,就是以结点,左子树,右子树的顺序遍历二叉树.观察并仿照其递归算法执行过程中的状态变化情况.因为是先序遍历,我们在将结点入栈前就可以访问它.如果它不是树叶,那么就优先将非空的左孩子入栈,否则入右孩子.而如果它是树叶,我们甚至不用将它入栈了.但我们要判断它是不是栈顶元素的左孩子并且这个栈顶元素还有个右孩子,如果是这样的话,我们就要将这个右孩子入栈,以保证不拉下每一个孩子:)  自己的算法如下:

接下来

6.38 同6.37题条件,写出后序遍历的非递归算法(提示:为分辨后序遍历时两次进栈的不同返回点,需在指针进栈时同时将一个标志进栈).

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

括号里面的提示搞的我的头很大,首先不知道它什么意思,然后自己想到一个没用什么标志的算法又害怕会不会是错的啊,半天不敢动笔,对自己很不自信啊,小悲剧.写完之后测试没什么错才放心,后来看了别的参考答案才知道那个使用标志的算法,确实很有用,那就是真正的”仿照其递归算法执行过程中的状态变化情况”,是很有意义的.以后如果遇到需要将递归转换为非递归的情况,可以认真观察递归算法的执行流程再加以仿照,也许效率会高一些.

后序遍历,就是以左子树,右子树,结点的顺序遍历二叉树.因为是后序遍历,所以我们在栈顶元素出栈的时候访问它.那么和先序遍历一样,如果栈顶元素不是树叶,那么就优先将其非空的左孩子入栈,否则入右孩子.而如果栈顶元素是树叶,那么它肯定要出栈了.同时,如果它是新的栈顶元素的左孩子,那么说明我们左子树已经访问完了,该访问右子树了(将新的栈顶元素的右孩子入栈);如果它是新的栈顶元素的右孩子,那我们右子树也访问完了,可以访问结点了(将新的栈顶元素出栈并访问它,继续这样判断).自己的算法如下:

写完之后,用C++实现了一下:

View Code

  1 // ds_c_ex_6.37.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include <iostream>
  6 #include <vector>
  7 using namespace std;
  8 
  9 struct node
 10 {
 11     char data;
 12     node *left;
 13     node *right;
 14     node(char c=0,node *l=NULL,node *r=NULL):data(c),left(l),right(r){}
 15 };
 16 
 17 typedef node * BitTree;
 18 
 19 char ch;
 20 
 21 void CreateTree(BitTree &T)//构造二叉树(按先序次序输入)
 22 {
 23     ch=cin.get();
 24     if(ch==' ')T=NULL;//空结点输入空格
 25     else
 26     {
 27         T=new node(ch);
 28         CreateTree(T->left);
 29         CreateTree(T->right);
 30     }
 31     return;
 32 }
 33 
 34 void PreOrder_Nonrecursive(BitTree t)//非递归的先序遍历
 35 {
 36     if(!t)return;
 37     vector<BitTree> S;
 38     do
 39     {
 40         cout<<t->data<<" ";
 41         if(!t->left&&!t->right)//->的优先级高于!高于&&
 42         {
 43             while(!S.empty())
 44             {
 45                 if(S.back()->right&&S.back()->right!=t)
 46                 {
 47                     t=S.back()->right;
 48                     break;
 49                 }
 50                 t=S.back();
 51                 S.pop_back();
 52             }
 53         }
 54         else
 55         {
 56             S.push_back(t);
 57             t=(t->left)?t->left:t->right;
 58         }
 59     }while(!S.empty());
 60     cout<<endl;
 61 }
 62 
 63 void postorder_traversal(BitTree t)//非递归的后序遍历
 64 {
 65     if(!t)return;
 66     vector<BitTree> S;
 67     S.push_back(t);
 68     while(!S.empty())
 69     {
 70         if(!S.back()->left&&!S.back()->right)
 71         {
 72             t=S.back();
 73             cout<<t->data<<" ";
 74             S.pop_back();
 75             while(!S.empty())
 76             {
 77                 if(t==S.back()->left&&S.back()->right)
 78                 {
 79                     S.push_back(S.back()->right);
 80                     break;
 81                 }
 82                 else
 83                 {
 84                     t=S.back();
 85                     cout<<t->data<<" ";
 86                     S.pop_back();
 87                 }
 88             }
 89         }
 90         else
 91         {
 92             t=(S.back()->left)?S.back()->left:S.back()->right;
 93             S.push_back(t);
 94         }
 95     }
 96     cout<<endl;
 97 }
 98 
 99 
100 
101 int _tmain(int argc, _TCHAR* argv[])
102 {
103     BitTree root=new node;
104     CreateTree(root);
105     PreOrder_Nonrecursive(root);
106     postorder_traversal(root);
107     system("PAUSE");
108     return 0;
109 }

作者: Barryhe 发表于 2011-11-16 00:30 原文链接

评论: 0　查看评论　发表评论

最新新闻：
· Google雅虎等呼吁欧盟勿制订过于严格隐私法律(2011-11-28 21:06)
· 强龙难压地头蛇 微软WP7俄罗斯忍痛割Bing(2011-11-28 20:27)
· 奇艺启动新域名背后：解决视听许可证遗留问题(2011-11-28 20:25)
· Kindle“黑色星期五”销量达去年同期四倍(2011-11-28 20:24)
· 维基解密本周将启动新在线系统(2011-11-28 20:21)

编辑推荐：如何快速成为Javascript高手的思考

网站导航：博客园首页  我的园子  新闻  闪存  博问  知识库

    关于AVL树的分析,请见:数据结构与算法分析学习笔记(二)--AVL树的算法思路整理

    这里给出AVL树的结构定义以及insert,remove和print三种操作的例程:

作者: Barryhe 发表于 2011-11-28 16:30 原文链接

评论: 0　查看评论　发表评论

最新新闻：
· Google雅虎等呼吁欧盟勿制订过于严格隐私法律(2011-11-28 21:06)
· 强龙难压地头蛇 微软WP7俄罗斯忍痛割Bing(2011-11-28 20:27)
· 奇艺启动新域名背后：解决视听许可证遗留问题(2011-11-28 20:25)
· Kindle“黑色星期五”销量达去年同期四倍(2011-11-28 20:24)
· 维基解密本周将启动新在线系统(2011-11-28 20:21)

编辑推荐：如何快速成为Javascript高手的思考

网站导航：博客园首页  我的园子  新闻  闪存  博问  知识库

看完了《数据结构与算法分析(C++描述)》的4.4节AVL树,做一个总结,整理一下自己实现删除算法的思路.(注:本文中图片均来自《数据结构与算法分析(C++描述)》)

    AVL(Adelson-Velskii and Landis,由阿德尔森一维尔斯和兰迪斯在1962年提出,因此得名)树是带有平衡条件(balance condition)的二叉查找树.

    我们知道空子树的高度通常被定义为-1,叶子结点的高度为0,其它结点的高度为其左右子树中的最大高度加1.一颗AVL树中的每一个结点的左子树和右子树的高度差不超过1.由此,我们可以考察一下一颗高度为h的AVL树的最少结点数S(h).显然S(0)=1,S(1)=2,而S(2)=S(0)+S(1)+1=3.由数学归纳法可以证明S(h)=S(h-1)+S(h-2)+1.

    AVL树的优势显而易见,它能更快的进行查找.那么怎样形成并保持一颗AVL树呢?首先我们来看insert(插入)操作.假设我们向一颗空的AVL树中按顺序插入1,2,3这3个数.1是根,2是1的右子树,3是2的右子树,这时我们发现1已经不满足平衡条件了,它的左子树高度为-1,而右子树高度为1.当遇到这种情况时,我们要立即进行某种操作使得不满足平衡条件的结点重新满足平衡条件.通过画图分析,可得在insert操作中,出现一个结点t不满足平衡条件可能出现在下面4种情况中:

(1)在t的左儿子的左子树中进行一次插入.(例如:3,2,1)

(2)在t的左儿子的右子树中进行一次插入.(例如:3,1,2)

(3)在t的右儿子的左子树中进行一次插入.(例如:1,3,2)

(4)在t的右儿子的右子树中进行一次插入.(例如:1,2,3)

    注意,上面举得例子只是最简单的的例子,我们应该多插入一些结点需找规律.这种寻找”测试数据”的能力也是必不可少的,以后自己要多加注意.课本上给出了一个不长但很有价值的例子.从初始为空的AVL树开始插入项3,2和1,然后依序插入4到7.

    当插入1时,根结点3不满足平衡条件,这时情况比较简单,我们自然会想到让2作为根,而1和3分别作为2的左右子树.那么继续插入,当插入5时,结点3出现了不平衡,同样我们想到让4取代3的位置,而3和5分别作为4的左右子树.

    当插入6时,我们发现2不满足平衡条件,这时我们按照刚才的思路,试着让4取代2的位置,而2作为4的左儿子,2的左子树和4的右子树不变.最后我们注意到4的左子树中结点的值一定大于2且小于4,因此将原来4的左子树移到新的2结点的右子树.

 

    由以上分析,我们可以得到情况(1)和(4)的解决方法.以情况(1)为例,如下图的左边部分,k1是k2的左儿子,在k1的左子树插入一个结点后使得k2不满足平衡条件.可以这样推理:

k2出现不平衡

     ->k2的左子树比右子树高2

          ->k1的高度本就比Z高1,现在又提高了1;又k1在其左子树X中插入结点后依然满足平衡条件的且其高度增加了1

               ->X,Y,Z原本一样高;在X中插入结点使得X本身高度加1.

得到这些子树的高度关系后,我们就可以通过”旋转”使得k2重新满足平衡条件.我们将Y先拿掉,将k1和k2对调(k1的左子树X和k2的右子树Z依然跟着它们),最后再根据查找树的性质,将Y作为k2的右子树,这样k1和k2就都满足了平衡条件.这种操作可以叫做左单旋转.注意,这样一来,这整个一颗树的高度在插入前和插入并旋转后没有发生变化,因此必然不会影响它的父节点(如果存在的话)的平衡情况.也就是说,对于情况(1)和(4),一次insert操作最多只需要一次的旋转操作就可以使整颗AVL树保持平衡.事实上,我们将看到情况(2)和(3)也是这样.

 

    接下来,我们来看情况(2).如下图,k1的右子树Y在进行一次插入操作后比X高1使得k2不满足平衡条件.这时如果我们按照上面的方法进行旋转会发现只是从情况(2)变成情况(3).

 

    继续在纸上画图,既然k1的右子树Y进行了一次插入操作,那么它必定不会为空.使用课本上的图,重新给这几个关键结点命名将Y的根设为k2,如下图:

 

    我们不知道B和C是否一样高或者谁高,我们也不需要知道,但我们知道k1和k2都是满足平衡条件的并且k2的高度比A高1也就是说B和C中至少有1个和A一样高,至多有一个比A矮1;类似上面情况(1)的推理,我们还能推得A和D一样高.这样一来,我们就可以放心的开始使一切变得平衡了.根据查找树的性质和我们得出的A,B,C,D四颗子树高度的关系,如图4-38的右边部分,我们将k2作为新的根,k1和k3分别为它的左右子树,A和D的相对位置没有变,而B和C被移动到了合适的位置.这种操作可以叫做左双旋转.注意到,和情况(1)一样,这样一来这整个一颗树的高度在插入前和插入并旋转后没有发生变化,因此必然不会影响它的父节点(如果存在的话)的平衡情况.

    知道怎样使AVL树保持平衡之后,就可以得出insert的算法.像一般的二叉查找树那样找到结点应该被插入的位置.然后从被插入点的父亲向上开始检查它的每个祖先,如果发现了一个不满足平衡条件的结点,立即进行”旋转”操作.如前所述,插入结点后,只要最多一次旋转就可以AVL树依然是平衡的.

    下面给出两种旋转和insert操作的C++代码,这里给出情况(1)和(2)的代码,完整的代码在这里.至于insert的代码,基本就是课本上图4-42中代码,只是做了一个小小的改进.

 

1 void leftSingleRotation(AVLnode * &t)//左单旋转
2 {
3     AVLnode *s=t->left;
4     t->left=s->right;
5     s->right=t;
6     t->height=max(height(t->left),height(t->right))+1;//重新计算s和t的高度
7     s->height=max(height(s->left),t->height)+1;
8     t=s;
9 }

 

 1 void leftDoubleRotation(AVLnode * &t)//左双旋转
 2 {
 3     AVLnode *p=t->left;
 4     AVLnode *q=p->right;
 5     t->left=q->right;
 6     p->right=q->left;
 7     q->left=p;
 8     q->right=t;
 9     t->height=max(height(t->left),height(t->right))+1;//重新计算3个结点的高度
10     p->height=max(height(p->left),height(p->right))+1;
11     q->height=max(p->height,t->height)+1;
12     t=q;
13 }

 

 1 void insert(const Object &x,AVLnode * &t)
 2 {
 3     if(!t)
 4         t=new AVLnode(x,NULL,NULL);
 5     else if(x<t->data)
 6     {
 7         insert(x,t->left);
 8         if(height(t->left)-height(t->right)==2)//在左子树插入结点后,不可能右子树比左子树高2
 9             if(x<t->left->data)
10                 leftSingleRotation(t);//左单旋转
11             else
12                 leftDoubleRotation(t);//左双旋转
13         else//不需要调整就满足平衡条件的话,只需要重新计算其高度就好
14             t->height=max(height(t->left),height(t->right))+1;
15     }
16     else if(x>t->data)
17     {
18         insert(x,t->right);
19         if(height(t->right)-height(t->left)==2)
20             if(x>t->right->data)
21                 rightSingleRotation(t);//右单旋转
22             else
23                 rightDoubleRotation(t);//右双旋转
24         else
25             t->height=max(height(t->left),height(t->right))+1;
26     }
27     else;//不考虑重复的值
28 }

    继续,我们来看remove(删除)操作.首先,回顾一下对于一般的二叉查找树是怎样进行remove操作的.先根据二叉树的性质找到应该删除的结点t(如果有的话);如果t是个叶子结点,直接delete就好;如果它只有一颗非空的子树,那么就让这颗子树继承被删除结点的位子;而如果它有两颗非空的子树,就在右子树X中找到值最小的结点s,将s的data(值)写到t中,再在X中删除s(因为s的左子树一定为空,否则它就不是X中最小的了.另外,当然也可以在左子树中找值最大的结点.)

    接下来,我们得仔细分析删除的时候会发生什么,在什么情况下会出现怎样的不平衡.这里我使用的是课本上在讲解insert时用到的一颗树,如右图.由于我比较懒,就不在这里画出删除结点之后的各种图形了,大家可以在纸上画,也许画着画着就想出比我的解法更好的解法了.

    假设删除结点10,再删除结点12,这时候结点11就不满足平衡条件了,出现了类似情况(1)的情形.

    再假设先删除结点8,再删除结点12,这时候还是结点11不平衡,但这时类似情况(2).

    再假设直接删除结点12,这时依然是结点11不平衡,这时虽然和情况(1),(2)都不相同,但我们可以像图4-34那样经过一次单旋转使结点11变得平衡.(只不过这时图4-34中的Y和X一样高而不是比X矮1.)

    这里特别需要注意的是,不管上上面3中情况中的哪一种情况,通过旋转使结点11平衡之后,它的高度都从2变成了1.这意味着,它的父亲的高度可能发生变化并且可能不再满足平衡条件.所以我们要从被删除点的父亲向上开始检查它的每个祖先,平衡每一个不满足平衡条件的祖先,直到找到了一个高度没有发生变化的祖先.

    另外,而对于删除有一个或者两个非空子树的结点,实际上都只是删除一个叶子结点.这样一来,我们得到了remove操作可能引发不平衡的4种情况.我们假设第一个不满足平衡条件的结点为t,t的左子树为X,右子树为Y.

(1)在Y中删除了一个结点,而X的右子树不高于X的左子树.

(2)在Y中删除了一个结点,而X的右子树高于X的左子树.

(3)在X中删除了一个结点,而Y的左子树不高于Y的右子树.

(4)在X中删除了一个结点,而Y的左子树高于Y的右子树.

对于情况(1),我们可以通过一次左单旋转使t平衡;而对于情况(1),我们可以通过一次左双旋转使t平衡;而情况(3)和(4)就可能分别需要进行右单旋转和右双旋转.下面给出我的remove操作代码:

 1 void AVLTree<Object>::remove(const Object &x,AVLnode *&t)
 2 {
 3     if(!t)return;//没有找到要删除的值,do nothing
 4     if(x<t->data)
 5     {
 6         remove(x,t->left);
 7         if(height(t->right)-height(t->left)==2)
 8         {
 9             //右子树比左子树高2,那么在删除操作之前右子树比左子树高1,
10             //也就是说t的右子树必然不为空,甚至必然有非空子树(高度至少为1).
11             AVLnode *s=t->right;
12             if(height(s->left)>height(s->right))
13                 rightDoubleRotation(t);//右双旋转
14             else
15                 rightSingleRotation(t);//右单旋转
16         }
17         else
18             //不需要调整就满足平衡条件的话,只需要重新计算其高度就好
19             t->height=max(height(t->left),height(t->right))+1;
20     }
21     else if(x>t->data)
22     {
23         remove(x,t->right);
24         if(height(t->left)-height(t->right)==2)
25         {
26             AVLnode *s=t->left;
27             if(height(s->right)>height(s->left))
28                 leftDoubleRotation(t);//左双旋转
29             else
30                 leftSingleRotation(t);//左单旋转
31         }
32         else
33             t->height=max(height(t->left),height(t->right))+1;
34     }
35     else
36     {
37         if(t->left&&t->right)
38         //t的左右子树都非空,把remove操作转移到只有一个非空子树的结点或者叶子结点上去
39         {
40             if(height(t->left)>height(t->right))
41             //把remove操作往更高的那颗子树上转移
42             {
43                 //左子树中的最大值
44                 t->data=max_node(t->left)->data;
45                 remove(t->data,t->left);
46             }
47             else
48             {
49                 //右子树中的最小值
50                 t->data=min_node(t->right)->data;
51                 remove(t->data,t->right);
52             }
53         }
54         else
55         {
56             AVLnode *oldnode=t;
57             t=t->left?t->left:t->right;
58             delete oldnode;
59         }
60     }
61 }

 

    这里是我写的一个AVL的简单实现: C++实践笔记(四)----AVL树的简单实现

    其中有一个粗糙的使用队列进行层次遍历打印树的代码,现在看起来如果想使对齐更完美,可以设置一个字符串最大长度的值.如果数据的长度比这个值小,就用空格补齐.

作者: Barryhe 发表于 2011-11-28 16:34 原文链接

评论: 0　查看评论　发表评论

最新新闻：
· Google雅虎等呼吁欧盟勿制订过于严格隐私法律(2011-11-28 21:06)
· 强龙难压地头蛇 微软WP7俄罗斯忍痛割Bing(2011-11-28 20:27)
· 奇艺启动新域名背后：解决视听许可证遗留问题(2011-11-28 20:25)
· Kindle“黑色星期五”销量达去年同期四倍(2011-11-28 20:24)
· 维基解密本周将启动新在线系统(2011-11-28 20:21)

编辑推荐：如何快速成为Javascript高手的思考

网站导航：博客园首页  我的园子  新闻  闪存  博问  知识库

接下来,我们根据《数据结构和算法分析 C++描述》中图3-12至3-20的代码,继续回顾类的有关知识.

代码如下:

    1.我们看到在第4行,Node类作为List的成员被标记为private,所以它就不能被List之外的类访问,它对用户(类的使用者)来说是隐藏的.同时,定义Node时使用了struct关键字,Node中的成员会默认为是公有的,使我们能在List及其派生类的成员函数中使用.

    2.看两个构造函数,分别在第12行和89行.Node()的形参列表中有两个默认值为NULL的指针,接着通过初始化列表,next和prev成员被安全的初始化了.而在List()中,我们没有看到形参也没有看到初始化列表.这样,在List()的初始化阶段,head和tail是危险的,他们没有被初始化;但是函数体中的new语句保证了构造函数的正确性,new语句返回的地址被赋值给head和tail.

    3.const_iterator类有两个构造函数,分别在第19行和第49行,其中const_iterator()是公有的,而const_iterator(Node *p)如果也被标记为public是不合适的,因为Node类对用户是隐藏的.而事实上定义这样一个构造函数就只是在List类范围内使用的.

    4.关于派生类的构造函数.当系统调用第60行的默认构造函数iterator()时,会自动调用其基类的默认构造函数,用来初始化从const_iterator继承而来的成员current.如果执行下面这句代码:

List<int> lis;

List<int>::iterator iter=lis.begin();

第2句的执行过程是这样的:首先调用117行的begin()函数,然后调用其函数体中的iterator( Node *p )函数(定义在第82行),接着调用其初始化列表中的const_iterator( Node *p )函数(定义在第49行).这样构造了一个构造了一个iterator类型的临时对象,该对象的current成员的值是复制了lis的头结点的next成员的值.最后使用编译器合成的iterator类的复制构造函数将这个临时对象复制给iter.

可以同样想一想并且测试下面的语句:

List<int>::iterator iter;

是怎样执行的.

    5.第25行至第36行是const_iterator类对"++"操作符的重载,我们知道"++"操作符有两个版本,分别是前缀和后缀版本,这两个版本是根据形参表中是否有一个匿名的int参数来区分的.如果形参表为空,则为前缀版本(++itr);而后缀版本(itr++)调用单参数operator++.这个int参数实际是不使用的,仅仅作为一个标识而存在.

    设计const_iterator是希望有一种"自以为"指向const对象的指针,这种指针不能修改其所指向的对象,但是这种指针本身的值是可以改变的.我们看到对"++"的重载版本不是const函数,而且这个函数返回的是一般引用.似乎iterator类也可以继承这对函数,但是由于返回值类型不同,所以在iterator类的定义中我们得重新提供operator++的实现.

    6.为了实现设计"const_”类的目的,我们在第22行重载”*”操作符时,返回的是const引用,这就保证了无法使用const_iterator类对象修改其所指向对象的值.

进一步探究这个函数,它是一个const函数,因为我们不打算通过它修改const_iterator类对象本身的值,所以函数体内的retrieve( )函数(定义在第46行)也必须是const函数.这是因为:const成员函数不能访问非const成员函数,反之则可以.

    显然,在定义iterator类时,我们要重写operator*函数(第63行),这个函数返回一般引用,因此可以用来修改iterator对象所指向的对象的值.函数体中同样调用了retrieve()函数,如前所述,非const成员函数可以访问const成员函数,所以这是合法的.

    那么为什么还要写第65,66行的代码呢?因为对于iterator类来说,由于有了修改版本的operator*函数(第63,64行),其基类中的operator*函数(第22,23行)就会被隐藏掉.这时,如果我们对一个由const关键字修饰的iterator对象解引用,编译器就会找不到可用的operator*函数.因此,第65,66行的代码是必须的.

作者: Barryhe 发表于 2011-11-02 22:24 原文链接

评论: 0　查看评论　发表评论

最新新闻：
· 调研称超1/3年轻人视网络如空气：离开无法生存(2011-11-04 14:09)
· 社交旅游网站Gogobot融资1500万美元，打造旅游爱好者的全能助手(2011-11-04 13:54)
· Digg创始人Kevin Rose新项目Oink上线，让你为周围的任何东西打分(2011-11-04 13:53)
· Dark Sky：无温度，无湿度，无风力的天气预报(2011-11-04 13:39)
· “摇一摇，味道更好”——雅虎发布“鸡尾酒”Web开发技术(2011-11-04 13:36)

编辑推荐：你正在成长为一名优秀的程序员吗？

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库

    做了几道zoj的题目,感到基础知识都忘得差不多了,很有必要重新学习,选了两本书,一本是大学时的课本《数据结构（C语言版）》,循序渐进,由浅入深,相信学过数据结构的都看过或者听说过这本书.还有一本是在网上找到的,书名是《数据结构和算法分析 C++描述》,这本书文字比较简练,但其中包含的信息量很大,读起来很有味道,也让人很有激情,很好.

    现在分析一下《数据结构和算法分析 C++描述》中图3-7,3-8的代码,看看能从这段代码中找到哪些需要注意的要点.

代码如下:

    1.第1行,template ['templit]关键字后接模板形参表,表明这里定义的Vector是一个类模板,而不是一个类,Vector<int>才是一个类.函数模板也是一样,它们都只是一个"公式".

    2.第5行,将构造函数声明为explicit [ik'splisit] ,是为了抑制由构造函数定义的隐式转换,如果这里没有explicit,那么下面的语句:

     Vector vec;

     ...

     vec=2;

将是合法的,"="右边的2将被这个不带explicit的构造函数隐式转换为一个Vector类型的临时变量,然后再通过operator=复制给vec.但这可能不是我们想要的结果,为了避免错误,在某些情况下,我们给单形参构造函数加上关键字explicit,这样的话上面的语句就不能编译通过了,vec=2要改为vec=vec(2).关于explicit的更多论述,可以参见《C++ Primer》第12.4.4小节.

    3.第6行,是构造函数的初始化列表.关于构造函数的初始化列表,有两个要点.第一,即使列表为空,没有初始化式,构造函数也会先初始化每个成员再进入函数体,这时初始化的规则与初始化变量相同,由此得知第二个要点:如果类的成员本身是一个没有默认构造函数的类类型,或者成员是const、引用类型,这样的成员必须在构造函数初始化列表中进行初始化.详见《C++ Primer》第12.4.1小节.

    4.第7行和第11行,第7行的new返回一个指向Object类型数组的指针,而通过new关键字分配的存储空间需要通过delete操作将其删除.反之,如果某个对象不是通过new操作动态创建获得的,那么它就不能由delete操作释放,事实上在这些对象的生命期结束之后,编译器会自动释放空间.这两行是一个特例,他们不是动态创建和释放单个对象,而是动态创建和释放数组,所以我们看到第11行使用了"delete []"操作符.

    5.第8行至第26行分别定义了Vector的复制构造函数,析构函数和重载赋值操作符.

    6.第52至55行,这里定义了重载下标操作符的两个版本,由于成员函数的定常性是(即函数名后是否有const关键字)是签名的一部分,因此我们可以使用访问函数的operator[]版本返回const引用,而修改函数版本返回一般引用.

作者: Barryhe 发表于 2011-10-31 14:45 原文链接

评论: 7　查看评论　发表评论

最新新闻：
· 调研称超1/3年轻人视网络如空气：离开无法生存(2011-11-04 14:09)
· 社交旅游网站Gogobot融资1500万美元，打造旅游爱好者的全能助手(2011-11-04 13:54)
· Digg创始人Kevin Rose新项目Oink上线，让你为周围的任何东西打分(2011-11-04 13:53)
· Dark Sky：无温度，无湿度，无风力的天气预报(2011-11-04 13:39)
· “摇一摇，味道更好”——雅虎发布“鸡尾酒”Web开发技术(2011-11-04 13:36)

编辑推荐：你正在成长为一名优秀的程序员吗？

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库

终于给力了一把,第一次submit就AC了.

恩,继续继续~~

作者: Barryhe 发表于 2011-10-25 17:15 原文链接

评论: 0　查看评论　发表评论

最新新闻：
· 调研称超1/3年轻人视网络如空气：离开无法生存(2011-11-04 14:09)
· 社交旅游网站Gogobot融资1500万美元，打造旅游爱好者的全能助手(2011-11-04 13:54)
· Digg创始人Kevin Rose新项目Oink上线，让你为周围的任何东西打分(2011-11-04 13:53)
· Dark Sky：无温度，无湿度，无风力的天气预报(2011-11-04 13:39)
· “摇一摇，味道更好”——雅虎发布“鸡尾酒”Web开发技术(2011-11-04 13:36)

编辑推荐：你正在成长为一名优秀的程序员吗？

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库

作者: Barryhe 发表于 2011-10-21 15:15 原文链接

评论: 0　查看评论　发表评论

最新新闻：
· 调研称超1/3年轻人视网络如空气：离开无法生存(2011-11-04 14:09)
· 社交旅游网站Gogobot融资1500万美元，打造旅游爱好者的全能助手(2011-11-04 13:54)
· Digg创始人Kevin Rose新项目Oink上线，让你为周围的任何东西打分(2011-11-04 13:53)
· Dark Sky：无温度，无湿度，无风力的天气预报(2011-11-04 13:39)
· “摇一摇，味道更好”——雅虎发布“鸡尾酒”Web开发技术(2011-11-04 13:36)

编辑推荐：你正在成长为一名优秀的程序员吗？

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库