AVL树

平衡二叉查找树的效率是 O(log__n__)，但是添加或删除节点可能让树变得不平衡。因此，要维持二叉查找树的效率，需要某种机制，在树失衡时重新排列树的节点，让它重新平衡。在 1962 年有两位数学家 G. M. Adelson-Velsky 和 Evgenii Landis 便提出了重新排列节点让树重归平衡。AVL树(Adelson-Velsky and Landis Tree)便是以它们名字首字母命名的平衡二叉树，也是最早的平衡二叉树。

AVL树是一种平衡二叉查找树，在添加或删除节点时，如果子树的高度差大于1，便重新排列节点，让树重新平衡。

AVL树通过旋转来纠正失衡的树，当插入和删除节点时，只影响树的一部分，树的重新平衡可以只在局部执行。

单旋转

所谓旋转，是以某个节点作为支点进行向左(逆时针)旋转或向右(顺时针)旋转。

左旋转

看下图的具体示例，在添加节点前，最高子树与最低子树高度差是1，满足AVL树规则。而添加8的节点后，最高子树与最低子树高度差变成了2，为了满足AVL树的规则，需要通过旋转使其重归平衡。(b)以7所在的节点为支点，向左旋转。

旋转提升了7所在的节点和它的子树高度，同时降低了另一侧子树的高度，现在这棵树的高度差是0。支点的左子节点需要另找一个节点作为归宿。旋转之后，被下降高度的节点的右子节点位置就空出来了，正好作为6的归宿。

下图中，灰色三角形 _T_₁、_T_₂ 和 _T_₃ 分别表示一棵子树。(a)中，在添加节点前，子树的高度差是1。(b)中，添加节点后，子树高度差变成了2。此时需要执行左旋转保持树平衡。(c)中，以 B 为支点左旋转恢复了平衡。旋转过程提升支点及其子树的高度，同时降低父节点及另一侧子树的高度。旋转后，支点与父节点“调换了位置”。如果支点存在子树，将子树断开，再将子树重新接驳到原来的父节点。

右选择

右旋转与左旋转对称，如下图。

双旋转

并不是所有不平衡的情形都能通过一个旋转就能恢复的，除了单旋转，还有双旋转。顾名思义，双旋转就是两个单旋转分别组合的旋转。

左-右选择

如下图，(a)中添加了4的节点，若只旋转一次，不论如何旋转也不可能恢复平衡。(b)中先对新节点的父节点6左旋转，而后再像(c)中对刚刚的支点6执行右旋转。这时候树恢复了平衡。

我们可以将以上的例子抽象为下图。

向 T₂ 子树添加节点后，原本的高度差为1的树变成了2，图中的(b)。首先左旋 B 到 C 处(c)，接着右旋 B 到 A 处。通过组合两次单旋转完成了一个双旋转。

右-左旋转

右-左旋转是左-右旋转的对称情形，如下图。

旋转总结

在添加节点前，树是平衡的，添加节点后，可能会出现暂时的不平衡，通过一个单旋转或一个双旋转就能恢复平衡。如果添加节点导致树失衡，那么添加节点前的高度，和旋转恢复平衡后的高度是相同的。也就是说，这种情形下，添加节点前和旋转后的高度不变。换言之，会增加树高度的，都不会导致树失衡(不旋转。并不是所有添加都会增加树的高度)。

要确定如何旋转，需要先根据以下两点判定失衡的情形：

1. 不平衡的节点它自身是左子节点还是右子节点
2. 不平衡的节点的子节点是左子节点还是右子节点

第一点容易理解。如果不平衡节点同时有左子节点和右子节点，这时第二点就不好分辨了。我们通过两个例子解释第二点。

上图中，红色节点处失衡，我们只需要对其右旋转一次就能恢复平衡。而下图的情形需要右-左旋转才能恢复平衡。

从上图中不难看出，第二点的：“不平衡节点的子节点”，指的是它的最高子树所在的那一侧。如果两侧子树高度相等，可选取任一侧。

不平衡情形总结如下：

• 右-右——左旋
  不平衡节点和其子节点位于右子树
• 左-左——右旋
  不平衡节点和其子节点位于左子树
• 左-右——左-右旋
  不平衡节点位于左子树，其子节点位于右子树
• 右-左——右-左选
  不平衡节点位于右子树，其子节点位于左子树

添加节点

接下来分析将数列 [4, 7, 8, 3, 2, 6] 添加到AVL树的过程。节点旁的数字表示节点的高度；为了辅助理解，None 节点用灰色表示，高度为 0。灰色节点并不是真实存在的节点。

上图中前面添加的两个节点并没有打破平衡，当添加8之后，其父节点6出现了不平衡。向左旋转后重新恢复了平衡。

继续添加节点，添加3的时候并没有打破平衡，只需要更新节点的高度即可。添加2之后，平衡被打破，根据上面的规则，向右旋转后恢复了平衡。如下图。

继续添加剩下的 6，树的平衡被破坏了。根据上面的规则，执行右-左旋转后恢复了平衡。如下图。

删除节点

下面演示从树中删除节点后树失去平衡，以及旋转恢复平衡的过程。前面文章“二叉查找树”已讨论过删除节点，AVL树也属于二叉查找树，在不考虑旋转时，删除的操作是一样的，此处不再赘述。

删除节点3之后，其左子节点2往上提，所在子树高度变小。右子树7处失衡，需要对其左子节点执行右-左旋转才能恢复平衡。

代码实现

在代码实现中需要一个 height 字段存储每个节点的高度，节点的高度差也称为平衡因子(balance factor)。在每一次添加新节点之后都需要实时更新子树路径中对应节点的高度，其中父节点的高度来自于左右子树最大节点高度 +1。通过查看比较左右子节点的平衡因子来决定是否旋转，每一次旋转后，替换和被替换的节点的高度都等于其左右子树最大节点高度+1。为了简单起见，插入和删除都使用递归执行，在弹栈时可以顺带执行更新节点高度和旋转。如果用迭代实现的话需要借助栈，且代码会更复杂些。

use std::cmp;
use std::cmp::Ordering;

struct Node<T> {
    v: T,
    height: usize,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn from(v: T) -> Self {
        Self {
            v,
            height: 1,
            left: None,
            right: None,
        }
    }
}

struct AVLTree<T> {
    root: Option<Box<Node<T>>>,
}

impl<T: Ord> AVLTree<T> {

    /// 添加节点
    fn insert(&mut self, v: T) {
        Self::insert_node(&mut self.root, Node::from(v).into());
    }

    /// 删除节点
    fn delete(&mut self, v: &T) {
        Self::delete_node(&mut self.root, v)
    }

    fn insert_node(current: &mut Option<Box<Node<T>>>, node: Box<Node<T>>) {
        match current {
            None => {
                // 在当前位置插入新节点
                current.replace(node);
                return;
            },
            Some(current) => match node.v.cmp(&current.v) {
                Ordering::Less => Self::insert_node(&mut current.left, node),
                Ordering::Greater => Self::insert_node(&mut current.right, node),
                Ordering::Equal => return,
            }
        };

        // 更新节点高度。递归出栈后执行，从添加路径的子树不断更新到根。
        // 即使后续不旋转，所在的不平衡子树的节点高度也是正确的。
        Self::update_height(current);

        // 旋转
        Self::rotate(current);
    }

    fn delete_node(current: &mut Option<Box<Node<T>>>, v: &T) {
        match current {
            None => return,
            Some(node) => match v.cmp(&node.v) {
                Ordering::Less => Self::delete_node(&mut node.left, v),
                Ordering::Greater => Self::delete_node(&mut node.right, v),
                Ordering::Equal => match (&node.left, &node.right) {
                    (None, None) => *current = None,
                    (Some(_), None) => *current = node.left.take(),
                    (None, Some(_)) => *current = node.right.take(),
                    (Some(_), Some(_)) =>
                        // Find max value on left to replace. Or use min value on right.
                        node.v = Self::find_min(&mut node.right).take().unwrap().v,
                }
            }
        }

        // 更新节点高度。递归出栈后执行，从添加路径的子树不断更新到根。
        // 即使后续不旋转，所在的不平衡子树的节点高度也是正确的。
        Self::update_height(current);

        // 旋转
        Self::rotate(current);
    }

    fn find_min(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> {
        let mut current = node;
        while let Some(node) = current {
            current = &mut current.as_mut().unwrap().left;
        }
        current
    }

    /// 更新节点高度。
    /// 是其最大子节点的高度+1。
    fn update_height(node: &mut Option<Box<Node<T>>>) {
        if let Some(node) = node {
            node.height = 1 + cmp::max(
                Self::height(&node.left),
                Self::height(&node.right)
            );
        }
    }

    /// 旋转
    /// 通过检测子节点的平衡因子来确定是否需要旋转
    fn rotate(current: &mut Option<Box<Node<T>>>) {
        let current_v = current.as_mut().unwrap();
        let balance_factor = Self::balance_factor(current_v);

        match balance_factor {
            // 不平衡的节点位于左子树
            bf if bf > 1 =>
                // 根据子节点的平衡因子来确定子节点在左子树还是右子树
                match Self::balance_factor(current_v.left.as_ref().unwrap()) {
                    // 子节点位于不平衡节点的左子树，执行右旋转
                    1 => Self::rotate_right(current),
                    // 子节点位于不平衡节点的右子树，执行左-右旋转
                    -1 => {
                        Self::rotate_left(&mut current_v.left);
                        Self::rotate_right(current);
                    }
                    _ => ()
                },

            // 不平衡的节点位于右子树
            bf if bf < -1 =>
            // 根据子节点的平衡因子来确定子节点在左子树还是右子树
                match Self::balance_factor(current_v.right.as_ref().unwrap()) {
                    // 子节点位于不平衡节点的右子树，执行左旋转
                    -1 => Self::rotate_left(current),
                    // 子节点位于不平衡节点的左子树，执行右-左旋转
                    1 => {
                        Self::rotate_right(&mut current_v.right);
                        Self::rotate_left(current);
                    }
                    _ => (),
                },
            _ => (),
        }
    }

    fn height(node: &Option<Box<Node<T>>>) -> usize {
        match node {
            None => 0,
            Some(n) => n.height,
        }
    }

    fn balance_factor(node: &Node<T>) -> i8 {
        let left = Self::height(&node.left);
        let right = Self::height(&node.right);
        match left < right {
            true => -((right - left) as i8),
            false => (left - right) as i8,
        }
    }

    /// 左旋转
    /// 旋转的是其右子节点。右子节点替换当前节点。
    fn rotate_left(node: &mut Option<Box<Node<T>>>) {
        if let Some(parent) = node {
            match parent.right.take() {
                Some(mut right) => {
                    // 交换中间节点
                    parent.right = right.left.take();
                    // 上下交换节点
                    node.as_mut().unwrap().left = node.replace(right.into()); // Box::from(*right);
                }
                None => unreachable!(),
            }
            Self::update_height(node);
            Self::update_height(&mut node.as_mut().unwrap().left);
        }

    }

    /// 右旋转
    /// 旋转的是其左子节点。左子节点替换当前节点。
    fn rotate_right(node: &mut Option<Box<Node<T>>>) {
        if let Some(parent) = node {
            match parent.left.take() {
                Some(mut left) => {
                    // 交换中间节点
                    parent.left = left.right.take();
                    // 上下交换节点
                    node.as_mut().unwrap().right = node.replace(left.into()); // Box::from(*left)
                }
                None => unreachable!(),
            }
            Self::update_height(node);
            Self::update_height(&mut node.as_mut().unwrap().right);
        }
    }
}

总结

由于AVL树是高度平衡的二叉查找树，因此它的查找效率可以达到 O(log__n__)，在添加和删除节点时，需要额外的操作保持平衡，这些操作也有一定的计算复杂度。在添加和删除操作较少时，通常不是什么问题，但是当添加和删除都比较频繁时，为了维持树的平衡，这些额外的操作对性能的影响可能会愈发明显。因此，对于查找远大于添加和删除的操作，AVL树是个不错的选择。除了查找之外，如果添加和删除的操作也很多，可能AVL树并不是最优解，下一篇讨论另一种树——红黑树，它不仅有近乎AVL树的查找效率，在添加和删除时，对性能的影响也不如AVL树那么大。