题目内容
（请给出正确答案）
[主观题]
试证明：a)按照二叉搜索树的基本算法在AVL树中引入一个节点后，失衡的节点可能多达Ω（logn)个;b)按照二叉搜索树的基本算法从AVL树中摘除一个节点后，失衡的节点至多1个。
提问人：网友yanjingjing2019
发布时间：2022-06-11
如搜索结果不匹配，请 
题目内容
（请给出正确答案）
您可能会需要：
安装简答题APP，拍照搜题省时又省心！
更多“试证明：a)按照二叉搜索树的基本算法在AVL树中引入一个节点…”相关的问题
第5题
关于α-β剪枝的陈述哪些是正确的？
A.α-β剪枝旨在增加其搜索树中由minimax算法评价的节点数量。
B.α-β剪枝旨在增加其搜索树中由minimax算法评价的节点数量。
C.α-β剪枝旨在消除其搜索树中由minimax算法评价的大部分。
D.α-β剪枝旨在减少其搜索树中由minimax算法评价的节点数量。
第6题
二叉搜索树可用来对n个元素进行排序。试编写一个排序算法，首先将n个元素a[1..n]插人到一个空的
二叉搜索树中，然后对树进行中序遍历，并将元素按序放人数组a中，为简单起见，假设a中的数据互不相同。试编写一个函数，从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h)，其中h是二叉搜索树的高度。
第10题
试证明，采用BST::insert（)算法（教材188页代码7.5)，在二叉搜索树中插入节点v之后。a)除v的历代祖先以外，其余节点的高度无需更新;b)祖先高度不会降低，但至多加一;c)一旦某个祖先高度不变，更高的祖先也必然高度不变。
第11题
对于二叉搜索树（Binary Search Tree），以下说法正确的是：
A、二叉搜索树的查找时间效率是
B、二叉搜索树的前序遍历序列，是从小到大排列的
C、二叉搜索树的查找算法与二分法查找是等价的
D、同样一组数据，如果按照不同顺序插入到一棵初始状态为空的二叉搜索树当中，则产生的二叉搜索树形态有可能不同。
