《avl树例题1.ppt》由会员分享,可在线阅读,更多相关《avl树例题1.ppt(5页珍藏版)》请在文库网上搜索。
例8-2,给定一个关键字序列4,5,7,2 ,1,3,6,试生成一棵平衡二叉树。分析:平衡二叉树实际上也是一棵二叉排序树,故可以按建立二叉排序树的思想建立,在建立的过程中,若遇到不平衡,则进行相应平衡处理,最后就可以建成一棵平衡二叉树。具体生成过程见图8-14。平衡二叉树本身就是一棵二叉排序树,故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树,不像二叉排序树一样,会出现最坏的时间复杂度O(n),它的时间复杂度与二叉排序树的最好时间复杂相同,都为O(log2n)。 例8-3,对例8-2给定的关键字序列4,5,7,2,1,3,6,试用二叉排序树和平衡二叉树两种方法查找,给出查找6的次数及成功的平均查找长度。分析:由于关键字序列的顺序己经确定,故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图8-14,得到的二叉排序树见图8-15。 从图8-15的二叉排序树可知,查找6需4次,平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。从图8-14的平衡二叉树可知,查找6需2次,平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知,平衡二叉树的查找性能优于二叉排序树。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- avl 例题