轉(zhuǎn)載自徹底搞懂AVL樹

什么是AVL樹

AVL樹赛惩，是一種平衡(balanced)的二叉搜索樹(binary search tree, 簡稱為BST)。由兩位科學(xué)家在1962年發(fā)表的論文《An algorithm for the organization of information》當(dāng)中提出焦除，作者是發(fā)明者G.M. Adelson-Velsky和E.M. Landis（鏈接由維基百科提供）尽楔。它具有以下兩個(gè)性質(zhì)：

• 任意一個(gè)結(jié)點(diǎn)的key繁涂，比它的左孩子key大盹靴，比它的右孩子key忻赀搿；
• 任意結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間高度差距最大為1鹉究；

所以，在代碼當(dāng)中踪宠，AVL樹的結(jié)構(gòu)應(yīng)該是這個(gè)樣子的(本文的具體代碼采用Java語法)：

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

基本操作(API)

對(duì)于一棵AVL樹來說自赔，它的應(yīng)該對(duì)外部提供的接口(Application Interface, 簡稱API)有：

• 往樹中插入(insert)一個(gè)結(jié)點(diǎn)；
• 刪除(delete)樹中已經(jīng)存在的某個(gè)結(jié)點(diǎn)柳琢；
• 搜索(search)樹中某個(gè)結(jié)點(diǎn)绍妨；
• 返回當(dāng)前結(jié)點(diǎn)在中序遍歷當(dāng)中的后一個(gè)結(jié)點(diǎn)(successor)；
• 返回當(dāng)前結(jié)點(diǎn)在中序遍歷當(dāng)中的前一個(gè)結(jié)點(diǎn)(predecessor)柬脸；
• 返回一個(gè)包含該AVL樹當(dāng)中的所有結(jié)點(diǎn)的有序集合(按照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);
}

輔助操作

為了實(shí)現(xiàn)上述的基本操作，我們會(huì)需要一些輔助的操作倒堕。因?yàn)锳VL樹是一種平衡樹灾测，所以每次增加或者減少樹中的元素都有可能使這棵樹由平衡變得不平衡，所以我們需要一種機(jī)制來檢測這棵樹是否平衡垦巴，以及當(dāng)它不平衡的時(shí)候媳搪，我們應(yīng)該通過某些操作使它重新平衡(rebalanced)。

平衡性檢測

對(duì)于一棵樹來說骤宣，它的高度(height)定義如下：

從根節(jié)點(diǎn)(root)開始到某一個(gè)葉子節(jié)點(diǎn)(leaf)的最長路徑(path)上結(jié)點(diǎn)的個(gè)數(shù)

根據(jù)AVL樹的定義秦爆，我們可以為所有的結(jié)點(diǎn)定義一個(gè)平衡因子(balanced factor)：

某個(gè)結(jié)點(diǎn)的平衡因子等于該節(jié)點(diǎn)的左孩子的高度減去右孩子的高度

根據(jù)平衡樹的定義，計(jì)算得到的平衡因?yàn)闀?huì)出現(xiàn)兩種情況：

• 如果平衡因子是0, 1, -1 這三個(gè)數(shù)的話憔披，可以認(rèn)定該節(jié)點(diǎn)是符合平衡樹的定義的等限；
• 否則，該結(jié)點(diǎn)不平衡芬膝，需要重新平衡望门；

對(duì)于一個(gè)BST來說，每次插入的元素只可能放在葉子結(jié)點(diǎn)上锰霜。所以只能影響某個(gè)子樹是否平衡怒允，對(duì)其他子樹不會(huì)有任何的影響。在這種情況下锈遥，我們只需要根據(jù)搜索的路徑纫事，從孩子往祖先找勘畔，如果有不平衡的結(jié)點(diǎn)就可以被找到。如果一直到根結(jié)點(diǎn)都沒有發(fā)現(xiàn)不平衡結(jié)點(diǎn)丽惶，則可以認(rèn)為這次的插入操作沒有造成樹的不平衡炫七。

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

再次平衡

如果發(fā)現(xiàn)了某個(gè)不平衡的結(jié)點(diǎn)，那么就需要對(duì)該結(jié)點(diǎn)進(jìn)行重平衡钾唬。實(shí)現(xiàn)重平衡的方法万哪，是對(duì)該節(jié)點(diǎn)的子樹進(jìn)行旋轉(zhuǎn)(rotation)。

旋轉(zhuǎn)有兩種情況抡秆，如下圖所示：

• 一種稱為左旋轉(zhuǎn)(關(guān)于X結(jié)點(diǎn)的左旋轉(zhuǎn));
• 一種稱為右旋轉(zhuǎn)(關(guān)于Y結(jié)點(diǎn)的右旋轉(zhuǎn));

旋轉(zhuǎn)示意圖

在上圖的基礎(chǔ)上奕巍，用代碼實(shí)現(xiàn)這個(gè)旋轉(zhuǎn)很簡單，代碼如下：

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
}

上述儒士，是原理性的操作的止。在真實(shí)的情況下，我們會(huì)遇到四種可能出現(xiàn)的情況 (注意下圖當(dāng)中的x,y, 不可以直接和上圖的對(duì)應(yīng)) :

四種可能情況意圖

圖中的x, y, z 所代表的含義如下：

• z着撩， 代表從插入元素的位置開始诅福，逆插入元素時(shí)的訪問結(jié)點(diǎn)的順序，從孩子向祖先方向開始檢測平衡因子時(shí)發(fā)現(xiàn)的第一個(gè)不平衡結(jié)點(diǎn)拖叙；
• y氓润，代表插入元素時(shí)的訪問結(jié)點(diǎn)路徑上，訪問z結(jié)點(diǎn)之后訪問的結(jié)點(diǎn)
• x薯鳍，代表插入元素時(shí)的訪問結(jié)點(diǎn)路徑上咖气，訪問y結(jié)點(diǎn)之后訪問的結(jié)點(diǎn)

這四種情況，都可以通過一次或者兩次的旋轉(zhuǎn)挖滤，來使得不平衡的結(jié)點(diǎn)變平衡采章。其中，case1, case4可以通過一次旋轉(zhuǎn)(singly rotation)重新平衡壶辜，case2, case3可以通過兩次旋轉(zhuǎn)(doubly rotation)重新平衡悯舟。

單次旋轉(zhuǎn)(singly rotatioin)

單次旋轉(zhuǎn)得到重新平衡的子樹的示意圖如下所示，需要注意的是分清對(duì)應(yīng)的結(jié)點(diǎn)砸民。

單次旋轉(zhuǎn)示意圖

在有了前面的輔助方法的情況下抵怎，我們可以寫如下的針對(duì)case1和case4的旋轉(zhuǎn)代碼：

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;
}

兩次旋轉(zhuǎn)(doubly rotatioin)

兩次旋轉(zhuǎn)就是要進(jìn)行兩次旋轉(zhuǎn)來使子樹重新平衡，流程如下圖示：

• case2情況下岭参，需要先對(duì)y結(jié)點(diǎn)進(jìn)行一次左旋轉(zhuǎn)反惕，然后再對(duì)z結(jié)點(diǎn)進(jìn)行一次右旋轉(zhuǎn)；
• case3情況下演侯，需要先對(duì)y結(jié)點(diǎn)進(jìn)行一次右旋轉(zhuǎn)姿染，然后再對(duì)z結(jié)點(diǎn)進(jìn)行一次左旋轉(zhuǎn)；

雙次旋轉(zhuǎn)示意圖

接著上面的代碼來寫：

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;
}

搜索子樹中的特殊元素

根據(jù)BST樹的性質(zhì)，我們可以在不搜索整棵樹的前提下悬赏，查找某些特殊的元素狡汉，比如最小key的元素以及最大key的元素。這兩個(gè)操作闽颇，可以O(shè)(logn)的時(shí)間內(nèi)完成盾戴。

搜索子樹中最大元素

在一棵子樹當(dāng)中，因?yàn)橛液⒆拥膋ey始終大于當(dāng)前結(jié)點(diǎn)key兵多，所以擁有最大key的元素必定位于其最深層的右孩子結(jié)點(diǎn)處尖啡。

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

搜索子樹中最小元素

在一棵子樹當(dāng)中，因?yàn)樽蠛⒆拥膋ey始終小于當(dāng)前結(jié)點(diǎn)key剩膘，所以擁有最小key的元素必定位于其最深層的左孩子結(jié)點(diǎn)處衅斩。

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

基本操作的具體實(shí)現(xiàn)

有了上面的輔助操作，我們可以考慮如何具體的實(shí)現(xiàn)前面提到的幾種基本操作了怠褐。對(duì)于一棵樹的操作畏梆，遍歷它的結(jié)點(diǎn)可以采用遞推或者遞歸的方法來進(jìn)行，本文盡量采用遞歸的方法使代碼看起來更加的優(yōu)雅惫搏。

插入元素(Insert)

在一棵AVL樹中插入一個(gè)元素的邏輯應(yīng)該是這樣子的：

1. 標(biāo)準(zhǔn)的BST插入元素操作，找到該元素應(yīng)該被放置的葉子結(jié)點(diǎn)蚕涤，將該元素連接上去筐赔；
2. 檢查這次操作是否破壞了樹的平衡，若是揖铜，通過旋轉(zhuǎn)維護(hù)平衡特性茴丰；

// 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)

在一棵樹中，刪除某個(gè)元素天吓，邏輯應(yīng)該是這樣子的：

1. 搜索給定的key贿肩，確定其是否在樹中；
2. 如果不在樹中龄寞，返回null汰规；如果在樹中，執(zhí)行標(biāo)準(zhǔn)的BST刪除操作物邑，并返回該刪除的結(jié)點(diǎn)溜哮；
3. 檢查被刪除結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)是否平衡，如果不平衡色解，則執(zhí)行重平衡操作茂嗓；

標(biāo)準(zhǔn)的BST刪除操作，必須維持BST的性質(zhì)科阎，應(yīng)該是這樣子的：

1. 找到要?jiǎng)h除的結(jié)點(diǎn)述吸；
2. 找到中序遍歷下，該節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)锣笨，把這個(gè)結(jié)點(diǎn)移到要?jiǎng)h除的結(jié)點(diǎn)的位置蝌矛；
3. 返回被刪除的結(jié)點(diǎn)道批；

尋找中序遍歷下，某個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)又會(huì)出現(xiàn)以下幾種情況：

• 該結(jié)點(diǎn)沒有或只有一個(gè)孩子：
  • 若沒有孩子朴读，直接移除這個(gè)結(jié)點(diǎn)屹徘；
  • 若有且僅有一個(gè)孩子，用該孩子頂替將要被刪除結(jié)點(diǎn)的位置衅金；
• 該結(jié)點(diǎn)有兩個(gè)孩子：
  • 尋找該節(jié)點(diǎn)的右子樹的最小元素 (即該結(jié)點(diǎn)右子樹最深層的左孩子)噪伊；

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中的搜索是完全一樣的，根據(jù)左孩子key小于根結(jié)點(diǎn)key氮唯，右結(jié)點(diǎn)key大于根結(jié)點(diǎn)key的性質(zhì)：

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;
}

當(dāng)前節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)

前一個(gè)元素(successor)

這里所說的前一個(gè)元素，以及下文所說的后一個(gè)元素是指AVL樹在中序遍歷的情況下的前一個(gè)元素和后一個(gè)元素瞒渠。因?yàn)樵贐ST當(dāng)中良蒸，中序遍歷可以將所有的元素按照key升序 (如果不允許重復(fù)的元素出現(xiàn))排列。

首先伍玖，需要知道什么是中序遍歷：

先訪問結(jié)點(diǎn)的左孩子顿肺，然后訪問該結(jié)點(diǎn)猜欺，最后訪問該結(jié)點(diǎn)的右孩子拾弃。

中序遍歷哩照，可以用如下的偽碼 (遞歸的方式)表示：

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

在AVL樹中，尋找符合上述要求的前一個(gè)結(jié)點(diǎn)椰棘，可能會(huì)遇到以下兩種情況：

• 當(dāng)前結(jié)點(diǎn)有左子樹纺棺，查找左子樹的最大元素 (即當(dāng)前結(jié)點(diǎn)的左子樹的最深層右孩子)
• 當(dāng)前結(jié)點(diǎn)沒有左子樹：向上查找祖先結(jié)點(diǎn)，直到找到第一個(gè)比當(dāng)前結(jié)點(diǎn)的key小的結(jié)點(diǎn)邪狞，返回之祷蝌；若查到root都沒有，則證明當(dāng)前結(jié)點(diǎn)沒有前一個(gè)元素帆卓，返回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;
}

后一個(gè)元素(predecessor)

同上理，在AVL樹中鳞疲，尋找符合上述要求的后一個(gè)結(jié)點(diǎn)罪郊，可能會(huì)遇到以下兩種情況：

• 當(dāng)前結(jié)點(diǎn)有右子樹，查找右子樹的最小元素 (即當(dāng)前結(jié)點(diǎn)的右子樹的最深層左孩子)
• 當(dāng)前結(jié)點(diǎn)沒有右子樹：向上查找祖先結(jié)點(diǎn)尚洽，直到找到第一個(gè)比當(dāng)前結(jié)點(diǎn)的key大的結(jié)點(diǎn)悔橄，返回之；若查到root都沒有，則證明當(dāng)前結(jié)點(diǎn)沒有后一個(gè)元素癣疟，返回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;
}

獲取樹中所有結(jié)點(diǎn)的有序集合

因?yàn)橐蠓祷匕揂VL樹當(dāng)中的所有結(jié)點(diǎn)按照key的升序排列的有序集合，很顯然可以通過中序遍歷整棵樹得到睛挚，上文已經(jīng)給出了中序遍歷的偽碼邪蛔，只需要實(shí)現(xiàn)它即可：

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);
}