平衡二叉树

平衡二叉树(AVL树)

为什么叫 AVL 树，因为他的发明者是 G.M.Adelson-Velsky & Evgenii Landis，根据科学家的英文名也称为AVL树。在1962年发表的论文 《An algorithm for the organization of information》 中公开了这一数据结构。

为什么要有平衡二叉树

二叉查找树在一定程度上可以提高搜索效率。但是，当原序列为有序时。构造的就是一颗倾斜二叉查找树。这时，二叉树退化成单链表，搜索效率降低为 $O(n)$

二叉查找树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查询效率。

左右子树的高度相差不超过1的树为平衡二叉树

平衡二叉树

平衡二叉查找树:简称平衡二叉树

1. 可以是空树。
2. 如果不是空树，任何一个节点的左子树与右子树都是平衡二叉树，并且高度之差绝对值不超过1。

平衡因子

平衡因子:某节点的左子树和右子树的高度（深度）差即为该节点的平衡因子（BF,Balance Factor）。在一颗平衡二叉树中，节点的平衡因子只能是 0、1、-1。

失衡与调整

最小失衡树：在新插入的节点向上查找，一第一个平衡因子的绝对值超过1的节点为根的子树称为最小不平衡子树。也就是说，一颗失衡的树，是有可能有多颗子树同时失衡的。而这个时候，我们只需要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

旋转的目的是减少高度，通过降低整棵树的高度来平衡。

删除元素 & 添加元素都有可能造成树的失衡，需要进行调整

左旋

右子树高度高于左子树。

节点的右孩子替代此节点位置

右孩子的左子树变为该节点的右子树

节点本身变成右孩子的左子树

右旋

左子树高度高于右子树

节点的左孩子替代节点位置

节点的右子树变为该节点的左子树

节点本身变成左孩子的右子树

参考

1. 什么是平衡二叉树 ↩