知识卡片
AVL树限制左右子树高度差
AVL 树也是二叉搜索树,但要求每个节点的左右子树高度差至多 1,并在节点维护高度。
与红黑树按颜色和黑高约束不同;本章只在问题中给出定义,对数高度及插入过程留作证明与设计。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
An AVL tree is a binary search tree that is height balanced: for each node x, the heights of the left and right subtrees of x differ by at most 1.
参考来源
- 位置:《算法导论(第4版)》第 13 章问题 13-3(`OEBPS/chapter013.xhtml`,文本字符 [50000, 55000))。
- 结论依据:问题 13-3 定义每节点左右子树高度差至多 1,并要求维护节点高度 h;题目 (a)(b) 分别要求证明 O(log n) 高度和设计插入修复。
- 原始内容:An AVL tree is a binary search tree that is height balanced : for each node x , the heights of the left and right subtrees of x differ by at most 1.