15 | AVL树：如何让二叉排序树永远保持最优？
胡光
在极端情况下，利用二叉排序树解决第 k 大问题时，尽管它有最优的求解算法，代价依旧不低。这时，我们可以使用 AVL 树来解决。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
该试读文章来自《常用算法 25 讲》，如需阅读全部文章，
请先通过赠一得一解锁课程
请先通过赠一得一解锁课程
赠一得一
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(11)
- 最新
- 精选
思成请问老师，调整平衡的时候，需要对每课子树都判断平衡因子并调整平衡吗？文中的示例代码能做到这点吗，我理解示例代码是不是只多做了下一级子树的平衡判断？编辑回复: 因为AVL树的调整是自底而上逐层调整的，所以每次只需要向下判断一级
3
惜昔老师说的要经过两次旋转才能平衡的看的不明白编辑回复: 这位同学你好，我举个例子，如果需要用左旋的话，原右子树的左子树会直接继承到新的左子树，那如果不平衡是由这个子树导致的，则左旋没有办法将不平衡的树高差消掉，所以要先把右子树的左子树的树高先给抹掉，所以要旋转两次，具体可以多看几次双旋的case
21
norton/Dark这么复杂的算法竟然看明白了，作者功底扎实，建议多出个算法实战专栏4
刘旺旺感觉越来越难了，慢慢啃，加油2
宋不肥之前一直觉得avl太高大上，没想到avl的代码这么简单，仔细一想逻辑确实是这样，也是因为老师讲得好嗷，但感觉左右旋转的图的中间部分那个画的有问题，不应该有三个分支，实际上已经变成两个数了，利用tmp存了字树的指针，又合并在一起的，希望能改进一下1
Mona432太棒了！期待作者更多的优秀专栏1- 陈阳图2和图3中的 ‘2 号节点的任意一个孩子都可以放到 4 号节点的左孩子位置。’这端描述有问题， 应该是2号节点的右子树的任意一个孩子都可以放到4号节点的左孩子位置
- Geek_de2717老师课后练习的答案是不是文稿里已经给了？就是这段代码中的 if (H(L(root)) > H(R(root))) { 部分 //AVL树调整平衡 Node *maintain(Node *root) { if (abs(H(L(root)) - H(R(root))) <= 1) return root; if (H(L(root)) > H(R(root))) { if (H(R(L(root))) > H(L(L(root)))) { root->lchild = left_rotate(root->lchild); } root = right_rotate(root); } else { if (H(L(R(root))) > H(R(R(root)))) { root->rchild = right_rotate(root->rchild); } root = left_rotate(root); } return root; }
Liao Pei把 P 当作 J 的左子树，T2 剩余的节点当作 J 的右子树，再把 P 的父亲当作 J 的父亲 既然P是J的左子树，为什么又能共享一个父亲呢- 微风漂过update_height()函数是如何实现的？1
收起评论