AVL Tree Cheatsheet 平衡二叉树（速记版）

定义

平衡二叉树是一种自平衡的二叉搜索树，在满足二叉搜索树的同时自动保持树的相对平衡，使得最坏情况仍能保持$O(logn)$的复杂度，而不至于退化成链表。

实现要点

1. 节点包括数据，优先级和树高三个部分。优先级用于比较，树高用于平衡。
2. 插入和删除都会产生失衡。
3. 对更新节点判断失衡，并向其父节点传播。已平衡则中途结束。
4. 平衡化的规则：
   • 内旋取代父亲节点，外旋更换子代节点
   • 外侧失衡直接内旋
   • 内侧失衡先外旋，再内旋
5. 删除的顺序：
   • 无后代：直接删除，判断失衡
   • 单子代：子代代替，判断失衡
   • 双子代：向左寻找最大后代，或向右寻找最小后代代替当前节点，然后判断失衡

代码实现

    //TODO