彻底搞懂AVL树

本文是作者原创文章，欢迎转载，请注明出处 from:@Eric_Lai

做一次标题党，平常很少用这个“彻底搞懂”这几个字，最近在学AVL树，用这几个字希望自己是真的懂了。同时也希望本文可以帮助大家理解AVL树，以及它的一些基本操作。

什么是AVL树

AVL树，是一种平衡(balanced)的二叉搜索树(binary search tree, 简称为BST)。由两位科学家在1962年发表的论文《An algorithm for the organization of information》当中提出，作者是发明者G.M. Adelson-Velsky和E.M. Landis（链接由维基百科提供）。它具有以下两个性质：

任意一个结点的key，比它的左孩子key大，比它的右孩子key小；
任意结点的孩子结点之间高度差距最大为1；

所以，在代码当中，AVL树的结构应该是这个样子的(本文的具体代码采用Java语法)：

class AVLNode {
  AVLNode left;
  AVLNode right;
  int height;
  int key;
  ArrayList<Object> values;
}

基本操作(API)

对于一棵AVL树来说，它的应该对外部提供的接口(Application Interface, 简称API)有：

往树中插入(insert)一个结点；
删除(delete)树中已经存在的某个结点；
搜索(search)树中某个结点；
返回当前结点在中序遍历当中的后一个结点(successor)；
返回当前结点在中序遍历当中的前一个结点(predecessor)；
返回一个包含该AVL树当中的所有结点的有序集合(按照key的升序排列)；

具体的接口文件如下所示：

// Assume the node of AVL tree is represented by AVLNode
interface AVLTree {
  /* return the inserted node */
  AVLNode insert(int key, Object value);
  /* return the deleted node, if no that node with the given key, return null */
  AVLNode delete(int key);
  /* return the node with the given key, if no that node that key, return null */
  AVLNode search(int key);
  /* return a list with all nodes in that tree in their key's increasing order */
  ArrayList<AVLNode> allNodes();
  /* return the next node of the given node when preforming inorder traversal */
  AVLNode next(AVLNode node);
  /* return the previous node of the given node when preforming inorder traversal */
  AVLNode prev(AVLNode node);
}

辅助操作

为了实现上述的基本操作，我们会需要一些辅助的操作。因为AVL树是一种平衡树，所以每次增加或者减少树中的元素都有可能使这棵树由平衡变得不平衡，所以我们需要一种机制来检测这棵树是否平衡，以及当它不平衡的时候，我们应该通过某些操作使它重新平衡(rebalanced)。

平衡检测

对于一棵树来说，它的高度(height)定义如下：

从根节点(root)开始到某一个叶子节点(leaf)的最长路径(path)上结点的个数

根据AVL树的定义，我们可以为所有的结点定义一个平衡因子(balanced factor)：

某个结点的平衡因子等于该节点的左孩子的高度减去右孩子的高度

根据平衡树的定义，计算得到的平衡因为会出现两种情况：

如果平衡因子是0, 1, -1 这三个数的话，可以认定该节点是符合平衡树的定义的；
否则，该结点不平衡，需要重新平衡；

对于一个BST来说，每次插入的元素只可能放在叶子结点上。所以只能影响某个子树是否平衡，对其他子树不会有任何的影响。在这种情况下，我们只需要根据搜索的路径，从孩子往祖先找，如果有不平衡的结点就可以被找到。如果一直到根结点都没有发现不平衡结点，则可以认为这次的插入操作没有造成树的不平衡。

int getBalancedFactor(AVLNode node) {
  if (node != null) 
    return node.left.height - node.right.heigh;
  return -1;
}

重平衡

如果发现了某个不平衡的结点，那么就需要对该结点进行重平衡。实现重平衡的方法，是对该节点的子树进行旋转(rotation)。

旋转有两种情况，如下图所示：

一种称为左旋转(关于X结点的左旋转);
一种称为右旋转(关于Y结点的右旋转);

旋转示意图

在上图的基础上，用代码实现这个旋转很简单，代码如下：

AVLNode rightRotation(AVLNode y) {
  AVLNode x = y.left;
  AVLNode T2 = x.right;
  x.right = y;
  y.left = T2;
  y.height = Math.max(y.left.height, y.right.height);
  x.height = Math.max(x.left.height, x.right.height);
  return x;
}

AVLNode leftRotation(AVLNode x) {
  AVLNode y = x.rigth;
  AVLNode T2 = y.left;
  x.right = T2;
  y.left = x;
  x.height = Math.max(x.left.height, x.right.height);
  y.height = Math.max(y.left.height, y.right.height);
  return y
}

上述，是原理性的操作。在真实的情况下，我们会遇到四种可能出现的情况 (注意下图当中的x,y, 不可以直接和上图的对应) :

四种可能情况示意图

图中的x, y, z 所代表的含义如下：

z，代表从插入元素的位置开始，逆插入元素时的访问结点的顺序，从孩子向祖先方向开始检测平衡因子时发现的第一个不平衡结点；
y，代表插入元素时的访问结点路径上，访问z结点之后访问的结点
x，代表插入元素时的访问结点路径上，访问y结点之后访问的结点

这四种情况，都可以通过一次或者两次的旋转，来使得不平衡的结点变平衡。其中，case1, case4可以通过一次旋转(singly rotation)重新平衡，case2, case3可以通过两次旋转(doubly rotation)重新平衡。

单次旋转(singly rotatioin)

单次旋转得到重新平衡的子树的示意图如下所示，需要注意的是分清对应的结点。

单次旋转示意图

在有了前面的辅助方法的情况下，我们可以写如下的针对case1和case4的旋转代码：

AVLNode rebalanced(AVLNode node, int insertedKey) {
  balancedFactor = getBalancedFactor(node);
  if (balancedFactor > 1 && insertedKey < node.key)
    return rightRotation(node);		//case 1
  if (balancedFactor < -1 && insertedKey > node.key)
    return leftRotation(node);		//case 4
  
  // ......
  // miss other 2 possibilities
  
  // if do not need rebalanced (all conditions cannot satisfied)
  // then return the current node
  return node;
}

双次旋转(doubly rotatioin)

双次旋转顾名思义，就是要进行两次旋转来使子树重新平衡，流程如下图示：

case2情况下，需要先对y结点进行一次左旋转，然后再对z结点进行一次右旋转；
case3情况下，需要先对y结点进行一次右旋转，然后再对z结点进行一次左旋转；

双次旋转示意图

接着上面的代码来写：

AVLNode rebalanced(AVLNode node, int insertedKey) {
  balancedFactor = getBalancedFactor(node);
  if (balancedFactor > 1 && insertedKey < node.key)
    return rightRotation(node);		//case 1
  if (balancedFactor < -1 && insertedKey > node.key)
    return leftRotation(node);		//case 4
  if (balancedFactor > 1 && insertedKey > node.left.key) {
    // case 2
  	node.left = leftRotation(node.left);
    return rightRotation(node);
  }
  if (balancedFactor < -1 && insertedKey < node.left.key) {
    // case 3
  	node.right = rightRotation(node.right);
    return leftRotation(node);
  }
  // if do not need rebalanced (all conditions cannot satisfied)
  // then return the current node
  return node;
}

搜索子树中的特殊元素

根据BST树的性质，我们可以在不搜索整棵树的前提下，查找某些特殊的元素，比如最小key的元素以及最大key的元素。这两个操作，可以O(logn)的时间内完成。

搜索子树中最大元素

在一棵子树当中，因为右孩子的key始终大于当前结点key，所以拥有最大key的元素必定位于其最深层的右孩子结点处。

AVLNode maxOfSubtree(AVLNode node) {
  while (node.right != null) node = node.right;
  return node;
}

搜索子树中最小元素

在一棵子树当中，因为左孩子的key始终小于当前结点key，所以拥有最小key的元素必定位于其最深层的左孩子结点处。

AVLNode minOfSubtree(AVLNode node) {
  while (node.left != null) node = node.left;
  return node;
}

基本操作的具体实现

有了上面的辅助操作，我们可以考虑如何具体的实现前面提到的几种基本操作了。对于一棵树的操作，遍历它的结点可以采用递推或者递归的方法来进行，本文尽量采用递归的方法使代码看起来更加的优雅。

插入元素(Insert)

在一棵AVL树中插入一个元素的逻辑应该是这样子的：

标准的BST插入元素操作，找到该元素应该被放置的叶子结点，将该元素连接上去；
检查这次操作是否破坏了树的平衡，若是，通过旋转维护平衡特性；

// assume root point to the root of the tree
AVLNode insert(AVLNode node, int key, Object value) {
  // if the tree is empty
  if (node == null) {
    root = new AVLNode(key, value);
    return root;
  }
  if (key > node.key)
    return insert(node.right, key, value);
  else if (key < node.key)
    return insert(node.left, key, value);
  else {
    // if key is already in the tree, here I will update the value
	node.value = value;
    return node;
   }
  // update the height of the node in insertion path
  node.height = 1 + Math.max(node.left.height, node.right.height);
  return rebalanced(node, key);
}

删除元素(Delete)

在一棵树中，删除某个元素，逻辑应该是这样子的：

搜索给定的key，确定其是否在树中；
如果不在树中，返回null；如果在树中，执行标准的BST删除操作，并返回该删除的结点；
检查被删除结点的所有祖先结点是否平衡，如果不平衡，则执行重平衡操作；

标准的BST删除操作，必须维持BST的性质，应该是这样子的：

找到要删除的结点；
找到中序遍历下，该节点的下一个结点，把这个结点移到要删除的结点的位置；
返回被删除的结点；

寻找中序遍历下，某个结点的下一个结点又会出现以下几种情况：

该结点没有或只有一个孩子：
- 若没有孩子，直接移除这个结点；
- 若有且仅有一个孩子，用该孩子顶替将要被删除结点的位置；
该结点有两个孩子：
- 寻找该节点的右子树的最小元素 (即该结点右子树最深层的左孩子)；

AVLNode delete(AVLNode node, int key) {
  if (root == null) return null;
  if (key > node.key)
    return delete(node.right, key);
  else if (key < node.key)
    return delete(node.left, key);
  
  // if the target key is found
  if ((node.left == null) || (node.right == null)) {
    // if there is only a child or no child
    if ((node.left == null) && (node.right == null)) {
      node = null;
    }else if ((node.left != null) && (node.right == null)) {
      node = node.left;
    }else if ((node.left == null) && (node.right != null)) {
      node = node.right;
    }
  } else {
    // if there is two child
    AVLNode temp = minOfSubTree(node.right);
    // copy the key and values to the current node
    node.key = temp.key;
    node.values = temp.values;
    node.right = delete(node.right, temp.key);
  }
  
  // if node has no child just remove itself
  if (node == null) return null;
  // otherwise, update the height after deletion because we just 
  // replace the target node with another node, so the height of 
  // the node's children will never change
  node.height = 1 + Math.max(node.left, node.right);
  // rebalanced
  return rebalanced(node, key);
}

搜索(search)

在AVL树中搜索和在BST中的搜索是完全一样的，根据左孩子key小于根结点key，右结点key大于根结点key的性质：

AVLNode search(AVLNode node, int key) {
  if (node != null) {
    if (key == node.key) return node;
    if (key > node.key) return search(node.right, key);
    if (key < node.key) return search(node.left, key);
  }
  return null;
}

前一个元素(successor)

这里所说的前一个元素，以及下文所说的后一个元素是指AVL树在中序遍历的情况下的前一个元素和后一个元素。因为在BST当中，中序遍历可以将所有的元素按照key升序 (如果不允许重复的元素出现)排列。

首先，需要知道什么是中序遍历：

先访问结点的左孩子，然后访问该结点，最后访问该结点的右孩子。

中序遍历，可以用如下的伪码 (递归的方式)表示：

inOrderTraversal(Node node)
  if (node.left != null) 
    inOrderTraversal(node.left)
      visit(node)
  if (node.right != null)
    inOrderTraversal(node.right)

在AVL树中，寻找符合上述要求的前一个结点，可能会遇到以下两种情况：

当前结点有左子树，查找左子树的最大元素 (即当前结点的左子树的最深层右孩子)
当前结点没有左子树：向上查找祖先结点，直到找到第一个比当前结点的key小的结点，返回之；若查到root都没有，则证明当前结点没有前一个元素，返回null；

AVLNode prev(AVLNode root, int key) {
  AVLNode curNode = root;
  if (curNode == null) return null;
  Stack<AVLNode> visited = new Stack<>();
  while (curNode != null) {
    visited.push(curNode);
    if (key > curNode.key) {
      curNode = curNode.right;
      continue;
    } else if (key < curNode.key) {
      curNode = curNode.left;
      continue;
    }
    // if the target key is found, check whether
    // it has left subtree or not
    if (curNode.left != null) 
      return maxOfSubtree(curNode.left);
    else {
      // pop out the current node itself
      visited.pop();
      while (visited.peek().key > key) {
        // if the top element's key is greater than
        // the given key, keep check its parent
        visited.pop();
        if (visited.isEmpty())
          // if reach to the root
          return null;
      }
      return visited.pop();
    }
  }
  // if reach here means the given key
  // do not exit in the tree
  return null;
}

后一个元素(predecessor)

同上理，在AVL树中，寻找符合上述要求的后一个结点，可能会遇到以下两种情况：

当前结点有右子树，查找右子树的最小元素 (即当前结点的右子树的最深层左孩子)
当前结点没有右子树：向上查找祖先结点，直到找到第一个比当前结点的key大的结点，返回之；若查到root都没有，则证明当前结点没有后一个元素，返回null；

AVLNode nextKey(AVLNode root, int key) {
  AVLNode curNode = root;
  Stack<MyAVLNode> visited = new Stack<>();
  while (curNode != null) {
    visited.push(curNode);
    if (key > curNode.key) {
      curNode = curNode.right;
      continue;
    }
    if (key < curNode.key) {
      curNode = curNode.left;
      continue;
    }
    if (curNode.right != null) {
      return minOfSubTree(curNode.right);
    } else {
      // if the node do not has right subtree
      visited.pop();
      while (visited.peek().key < key) {
        // if the top element is less than the given key
        // pop them out, search for the ancestor
        visited.pop();
        if (visited.isEmpty())
          // reach the root
          return null;
      }
      // find the first ancestor whose key is greater than the given key
      return visited.pop();
    }
  }
  return null;
}

获取树中所有结点的有序集合

因为要求返回包含该AVL树当中的所有结点按照key的升序排列的有序集合，很显然可以通过中序遍历整棵树得到，上文已经给出了中序遍历的伪码，只需要实现它即可：

ArrayList<AVLNode> allNodes() {
  ArrayList<AVLNode> list = new ArrayList<>();
  inOrderTraversal(this.root, list);
  return list;
}

void inOrderTraversal(Node node, ArrayList<AVLNode> list) {
  if (node.left != null) inOrderTraversal(node.left);
  list.add(node);
  if (node.right != null)inOrderTraversal(node.right);
}