平衡二叉树之AVL树（Adelson-Velsky and Landis Tree）简介及Java实现

[toc]

#### 一、AVL树简介
在前面的内容中，我们已经介绍了[平衡二叉树](https://www.datalearner.com/blog/1051540458496514)。其中提到了AVL树，这是一种非常著名的平衡二叉树。

在计算机科学中，AVL树（以发明者Adelson-Velsky和Landis命名）是一种自平衡二叉查找树。这是第一个发明类似自平衡机制的二叉树数据结构。在AVL树中，任何节点的两个子树的高度最多相差一个。如果在任何时候它们相差多于一个，则重新平衡以恢复此属性。查找，插入和删除在平均和最差情况下都需要$O(\log n)$时间，其中n是操作之前树中的节点数。插入和删除可能需要通过一个或多个树旋转来重新平衡树。

AVL树以其两位苏联发明家Georgy Adelson-Velsky和Evgenii Landis命名，他们在1962年的论文“An algorithm for the organization of information”中发表了这篇论文。

AVL树通常与红黑树进行比较，因为它们都支持相同的操作，并且对基本操作都是$O(\log n)$时间。对于查找密集型应用程序，AVL树比红黑树快，因为它们更严格地平衡。与红黑树相似，AVL树是高度平衡树。

#### 二、平衡因子（Balance Factor）
在二叉树中，平衡因子（Balance Factor）是一种高度之差，它等于左子树的高度减去右子树的高度：
```math
\text{BF(T)} = H_L - H_R
```

如果一个树是AVL树，那么它的平衡因子只能有三种取值，即0,1和-1。当平衡因子小于0，称为“left heavy”，大于0是“right-heavy”，等于0则是平衡的。

#### 三、自平衡适应
前面已经说过了，保证树的平衡会大大提高搜索的效率。那么如何保证平衡就是不同自平衡树之间的差异了。AVL树保持自平衡的方式是通过旋转的方式。上述定义的平衡因子就是帮助我们判断是否需要进行平衡操作的信息，而AVL树的平衡操作主要包括单旋转和双旋转两种，前者分为左单旋和右单旋，而后者则分成左右旋转和右左旋转。

旋转操作发生在插入和删除操作中，因为插入和删除可能会破坏树的平衡状态。以插入为例，所有新加的元素都是叶子节点，叶子节点的左右子树高度都是0，因此平衡因子也是0，不存在平衡的需要。因此，需要平衡的节点是其父节点。平衡的操作取决于新加的元素是左叶子节点还是右叶子节点。如果是右叶子节点，那么父节点的平衡因子就要减1，否则加1。这个操作也会传导到爷爷节点一直到根节点。因此，这里也引申出了自平衡操作的两个基础：
- 这种递归操作会传导到树的根节点
- 父节点的平衡因子已经是0了，因此一旦子树的平衡因子也是0的时候，那么父辈节点的平衡就不会改变。

下面我们看一个简单的例子：

<center>![](http://www.datalearner.com/resources/blog_images/959d9041-0f00-4ea3-a419-ca0c0ed339f1.png)

</center>

如上图所示，左图是一个不平衡的树，其中A节点的平衡因子是-2，B是-1，C是0。其中B的平衡因子超出了范围，需要调整，在这里，A的平衡因子过小，因此把A降下来，B提上去就能得到右图。这是一个左旋转的过程，因为A向左边下降了。具体来说，左旋转的过程如下：

1. 如果某个节点的平衡因子是-2，那么需要左旋转。
2. 找出平衡因子被破坏的节点（如上图的A）
3. 将该节点的右子节点变成根节点（如上图的B）
4. 把原来不平衡的节点（A）变成新的根节点（B）的左子节点
5. 如果新的根节点（B）本来就有了左子节点，那么把这个左子节点变成新的左子节点（A）的右子节点。注意，由于新的根节点是原来根节点（A）的右子节点。因此，把B的原来左子节点变成A的右子节点依然能保证平衡。不需要考虑更多。

在上图的例子中，B的左子节点是空，所以没有这一步。尽管这个原理很简单，但是在写代码的时候也有点技巧，因为我们需要移动节点，且要保证二叉搜索树的形状，还需要考虑更新所有父节点的指针。

我们来看一个更复杂的左旋转的例子，如下图所示：

<center>![](http://www.datalearner.com/resources/blog_images/7c09d38c-4d78-438c-9bda-19d2ab284221.png)
</center>

左树是一个平衡二叉树，假设我们要插入一个新节点F，变成了右图，新节点是E节点的左子节点。这样所有的节点的平衡因子就重新更新了，我们发现A节点的平衡因子是-2，那么根据上述步骤，我们需要把C节点变成根节点，A及其左子节点变成C的左子节点。但是我们发现C已经有了左子节点D，那么我们把D变成了A的右子节点。注意，C>A且D>A，所以D放在A的右子节点依然不会改变其二叉查找树的结构。我们得到一个新的子树：

<center>![](http://www.datalearner.com/resources/blog_images/018ec0f2-ef35-4087-aa46-67e3195be32f.png)

</center>

再把上述子树放到C的左边即可得到新的平衡二叉树。

<center>![](http://www.datalearner.com/resources/blog_images/65640f5c-fbe8-44eb-bbc4-91093dfa23cc.png)</center>

大家可以去https://www.cs.usfca.edu/~galles/visualization/AVLtree.html 这里看AVL树自平衡的可视化，自己试试。

#### 四、AVL树的Java实现
我们说一下AVL树的实现，最核心的部分肯定是旋转的操作。以上图的左旋转为例，其主要步骤分成如下：

把当前节点的右节点当做新的根节点
把新的根节点的左节点减下来
将减下来的节点拼接掉原来根节点的右节点上
把原来的根节点拼接到新的根节点左子节点上
其主要步骤如下：
```java
// 左旋转
  private AVLNode leftRotate(AVLNode rootNode){

AVLNode newRootNode = rootNode.rightNode;     // 新的根节点是原来根节点的右节点

// 将新的根节点的左节点拿出来，然后拼到原来的根节点上
    AVLNode pruningNode = newRootNode.leftNode;
    rootNode.rightNode = pruningNode;

// 再把拼接后的节点放到新根节点的左边
    newRootNode.leftNode = rootNode;

// 更新节点高度
    updateNodeHeight(rootNode);
    updateNodeHeight(newRootNode);

return newRootNode;   // 返回新的根节点

}

```

完整的AVL树Java代码如下：

```java
package com.huawei.machinelearning.data.structure;

/**
 * AVL Tree implementation
 * Created by d00454735 on 2018/10/26.
 */
public class AVLTree {

AVLNode root;     // 根节点

// 右旋转
  private AVLNode rightRotate(AVLNode rootNode){

AVLNode newRootNode = rootNode.leftNode;     // 新的根节点是原来根节点的左节点

// 将新的根节点的右节点拿出来，然后拼到原来的根节点上
    AVLNode pruningNode = newRootNode.rightNode;

// 再把拼接后的节点放到新根节点的左边
    newRootNode.rightNode = rootNode;
    rootNode.leftNode = pruningNode;

// 更新节点高度
    updateNodeHeight(rootNode);
    updateNodeHeight(newRootNode);

return newRootNode;   // 返回新的根节点

}

// 左旋转
  private AVLNode leftRotate(AVLNode rootNode){

AVLNode newRootNode = rootNode.rightNode;     // 新的根节点是原来根节点的右节点

// 将新的根节点的左节点拿出来，然后拼到原来的根节点上
    AVLNode pruningNode = newRootNode.leftNode;

// 再把拼接后的节点放到新根节点的左边
    newRootNode.leftNode = rootNode;
    rootNode.rightNode = pruningNode;

// 更新节点高度
    updateNodeHeight(rootNode);
    updateNodeHeight(newRootNode);

return newRootNode;   // 返回新的根节点

}

// 插入一个新节点
  AVLNode insert(AVLNode avlNode, int key) {

// 如果节点为空，当前插入的是根节点
    if (avlNode == null) {
      return new AVLNode((key));
    }

// 插入操作
    if (key < avlNode.key) {    // 如果插入的节点key小于根节点的key，则左边
      avlNode.leftNode = insert(avlNode.leftNode, key);
    } else if (key > avlNode.key) {
      avlNode.rightNode = insert(avlNode.rightNode, key);
    } else {    // 如果key已存在，则无法插入
      return avlNode;
    }

// 更新节点的高度
    updateNodeHeight(avlNode);

// 获取父节点的平衡因子
    int balance = getBalance(avlNode);

// 判断是否需要旋转操作，四种情况
    // 右旋转
    if( balance > 1 && key < avlNode.leftNode.key ){
      return rightRotate(avlNode);
    }

// 左旋转
    if( balance < -1 && key > avlNode.rightNode.key ){
      return leftRotate(avlNode);
    }

// 左右旋转
    if( balance > 1 && key > avlNode.leftNode.key){
      avlNode.leftNode = leftRotate(avlNode.leftNode);
      return rightRotate(avlNode);
    }

// 右左旋转
    if( balance < -1 && key < avlNode.rightNode.key){
      avlNode.rightNode = rightRotate(avlNode.rightNode);
      return leftRotate(avlNode);
    }

return avlNode;

}

// 获取当前节点的平衡因子
  private int getBalance(AVLNode avlNode){
    if( avlNode == null ){
      return 0;
    }

return height(avlNode.leftNode) - height(avlNode.rightNode);
  }

// 更新节点高度
  private void updateNodeHeight(AVLNode avlNode){
    avlNode.height = max(height(avlNode.leftNode), height(avlNode.rightNode))+1;
  }

// 返回较大的值
  private int max(int h1, int h2) {
    return h1 > h2 ? h1 : h2;
  }

// 取出节点的高度
  private int height( AVLNode avlNode ){
    if( avlNode == null ){
      return 0;
    }

return avlNode.height;
  }

// A utility function to print preorder traversal
  // of the tree.
  // The function also prints height of every node
  void preOrder(AVLNode node) {
    if (node != null) {
      System.out.print(node.key + " ");
      preOrder(node.leftNode);
      preOrder(node.rightNode);
    }
  }

public static void main(String[] args) {
    AVLTree tree = new AVLTree();

/* Constructing tree given in the above figure */
    tree.root = tree.insert(tree.root, 10);
    tree.root = tree.insert(tree.root, 20);
    tree.root = tree.insert(tree.root, 30);
    tree.root = tree.insert(tree.root, 40);
    tree.root = tree.insert(tree.root, 50);
    tree.root = tree.insert(tree.root, 25);

/* The constructed AVL Tree would be
             30
            /  \
          20   40
         /  \     \
        10  25    50
        */
    System.out.println("Preorder traversal" +
            " of constructed tree is : ");
    tree.preOrder(tree.root);
  }

}

// 定义AVL树的节点，这个和其他的一样
class AVLNode {

int key;      // 节点的key
  int height;   // 节点的高度
  AVLNode leftNode, rightNode;   // 左右子节点

AVLNode(int d) {
    key = d;
    height = 1;
  }

}

```

平衡二叉树之AVL树（Adelson-Velsky and Landis Tree）简介及Java实现

相关博客

最热博客