知识卡片

普通读书笔记卡 · 1292.f.1.a.7

AVL树限制左右子树高度差

理解等级:初级

AVL 树也是二叉搜索树,但要求每个节点的左右子树高度差至多 1,并在节点维护高度。

与红黑树按颜色和黑高约束不同;本章只在问题中给出定义,对数高度及插入过程留作证明与设计。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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.