[数据结构]检索二叉排序树的结点删除习题平衡二叉树AVL树因为插入新结点而导致失去平衡的调整方法习题习题

• 二分检索算法的时间复杂度为：O(log2(n+1))
• 若以二分检索来确定块，则分块检索查找成功时的平均查找长度为

log2(n/s+1)+s/2

• 删除操作的平均时间亦为O(log2n)

二叉排序树的结点删除

用其中序前驱代替该结点

用其中序前驱代替该结点

将其左子树收为该结点中序后继的左孩子

将其左子树收为该结点中序后继的左孩子

习题

• 适用于折半查找表的存储方式及元素排列要求为顺序方式存储，元素有序



0-6
4-6
• 注意：中间3是不算入比较的
  
  第一层比一次，第二层比两次，第三层从上到下要比三次…那么第五层有15个，第六层有2个未找到
  
  因为题目是找不存在的元素，所以第五层的15个只比较到了第四层，第6层的两个只比较到第五层
  (15*4+2*5)/17
比较最多的次数是5

(1*1+2*2+4*3+5*4)/12

7<log2^100<8
  书本231 9.4 9.7

平衡二叉树

又称AVL树

• 性质:
  1左子树和右子树都是平衡二叉树
  2左子树和右子树高度之差的绝对值不超过1
• 平衡因子：左子树和右子树高度之差
• 丰满树一定是平衡树，但平衡树不一定是丰满树
  

AVL树因为插入新结点而导致失去平衡的调整方法

LL型平衡旋转

即跟结点左边的结点的左边节点

RR型平衡旋转

LR型平衡旋转

RL型平衡旋转

习题

这张图记死！！！！

习题

答案D

• A :最多五层，A排除
• B，C：第五层都没有，更错了
  
  答案C
• 画出图后最多6层，在图中我们看到丰满树是到了第二层，根据平衡二叉树的定义只有倒数第一层和倒数第二层可以不满，所以关键字应该在第三层到第五层。
• 再看B，28应该在第一个数和第二个数之间，排除

最后

以上就是灵巧心锁为你收集整理的[数据结构]检索二叉排序树的结点删除习题平衡二叉树AVL树因为插入新结点而导致失去平衡的调整方法习题习题的全部内容，希望文章能够帮你解决[数据结构]检索二叉排序树的结点删除习题平衡二叉树AVL树因为插入新结点而导致失去平衡的调整方法习题习题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。