平衡二叉树

AVL树可视化工具

AVL树可视化工具（旧金山大学 (usfca)|数据结构可视化工具）

一、平衡二叉树定义

平衡二叉树又称AVL树。它可以是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的高度之差(平衡因子)的绝对值不超过1且它的左子树和右子树都是一颗平衡二叉树。

从上面简单的定义我们可以得出几个重要的信息：

• 平衡二叉树又称AVL树
• 平衡二叉树必须是二叉排序树
• 每个节点的平衡因子=左子树和右子树的高度差至多为1。

 在插入操作中，只要将最小不平衡子树调整A平衡，则其他祖先结点都会恢复平衡
选择规则如下：

节点的平衡因子

最小的不平衡子树

当插入新节点导致不平衡时，就调整最小的不平衡子树

 调整规则：

 平衡二叉树的查找复杂度

证明如下：所有可以推出平衡二叉树的最大深度。