数据结构 - AVL树

平衡因子（Balance Factor）：某节点的左右子树的高度差

AVL树的特点：

每个节点的平衡因子只可能是1、0、-1（绝对值<=1，否则失衡）

每个节点的左右子树高度差不超过1

搜索、添加、删除的时间复杂度是 $O(log{n})$

平衡

失衡

示例：往下面这棵子树添加 13

最坏情况：可能会导致所有祖先节点都失衡

父节点、非祖先节点，都不可能失衡

添加导致的失衡

示例：删除子树中的 16

可能会导致父节点或祖先节点失衡

只有一个节点会失衡，其他节点都不可能失衡

删除导致的失衡

添加

可能会导致所有祖先节点都失衡

只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡【仅需 $O(1)$ 次调整】

删除

可能会导致父节点或祖先节点失衡（只有1个节点会失衡）

恢复平衡后，可能会导致更高层的祖父节点失衡【最多需要 $O(log{n})$ 次调整】

平均时间复杂度

搜索： $O(log{n})$

添加： $O(log{n})$ ，仅需 $O(1)$ 次的旋转操作

删除： $O(log{n})$ ，最多需要 $O(log{n})$ 次的旋转操作

最后编辑于：2021.06.28 16:10:38

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。