参照物 一文读懂 AVL 树

链接：https://www.61mon.com/index.php/archives/218/

背景

AVL 树是一棵平衡的二叉查找树，于 1962 年，G. M. Adelson-Velsky 和 E. M. Landis 在他们的论文《An algorithm for the organization of information》中发表。

所谓的平衡之意，就是树中任意一个结点下左右两个子树的高度差不超过 1。（本文对于树的高度约定为：空结点高度是 0，叶子结点高度是 1。）

那 AVL 树和普通的二叉查找树有何区别呢？如图，如果我们插入的是一组有序上升或下降的数据，则一棵普通的二叉查找树必然会退化成一个单链表，其查找效率就降为 O(n)。而 AVL 树因其平衡的限制，可以始终保持 O(logn) 的时间复杂度。

具体实现与代码分析

在我们进行完插入或删除操作后，很可能会导致某个结点失去平衡，那么我们就需要把失衡结点旋转一下，使其重新恢复平衡。

经过分析，不管是插入还是删除，它们都会有四种失衡的情况：左左失衡，右右失衡，左右失衡，右左失衡。因此每次遇到失衡时，我们只需判断一下是哪个失衡，再对其进行相对应的恢复平衡操作即可。

好，下面以插入操作为例，来看下这四种失衡的庐山真面目。（以下统一约定：红色结点为新插入结点，y 结点为失衡结点）

（1）左左失衡

所谓的左左，即 "失衡结点" 的左子树比右子树高 2，左孩子下的左子树比右子树高 1。

我们只需对 "以 y 为根的子树" 进行 "左左旋转 (ll_rotate)" 即可。一次旋转后，恢复平衡。

Node * AVL::ll_rotate(Node * y)

{

Node * x = y->left;

y->left = x->right;

x->right = y;

y->height = max(get_height(y->left), get_height(y->right)) + 1;

x->height = max(get_height(x->left), get_height(x->right)) + 1;

return x;

}

（2）右右失衡

所谓的右右，即 "失衡结点" 的右子树比左子树高 2，右孩子下的右子树比左子树高 1。

我们只需对 "以 y 为根的子树" 进行 "右右旋转 (rr_rotate)" 即可。一次旋转后，恢复平衡。

Node * AVL::rr_rotate(Node * y)

{

Node * x = y->right;

y->right = x->left;

x->left = y;

y->height = max(get_height(y->left), get_height(y->right)) + 1;

x->height = max(get_height(x->left), get_height(x->right)) + 1;

return x;

}

（3）左右失衡

所谓的左右，即 "失衡结点" 的左子树比右子树高 2，左孩子下的右子树比左子树高 1。

观察发现，若先对 "以 x 为根的子树" 进行 "右右旋转 (rr_rotate)"，此时 "以 y 为根的子树" 恰好符合 "左左失衡"，所以再进行一次 "左左旋转 (ll_rotate)"。两次旋转后，恢复平衡。

Node * AVL::lr_rotate(Node * y)