[Data Structure] AVL Tree - 3: AVL Insertions & Removals

AVL Insertions

Inserting an item into an AVL tree may cause the tree to become temporarily unbalanced. A rotation can rebalance the tree.

If you have read the pseudocode of rotation carefully, you would've noticed that there is a case labeled as Double Rotation case, where we need to apply two rotations for rebalancing. 

In the following case, we apply double right rotation at C to rebalance the AVL Tree. 

 

4 AVL Imabalance Cases

 

AVL Imbalance Cases and Corresponding Rotations

 

AVLTreeInsert(tree, node) {
   if (tree⇢root == null) {
      tree⇢root = node
      node⇢parent = null
      return
   }

   cur = tree⇢root
   while (cur != null) {
      if (node⇢key < cur⇢key) {
         if (cur⇢left == null) {
            cur⇢left = node
            node⇢parent = cur
            cur = null
         }
         else {
            cur = cur⇢left
         }
      }
      else {
         if (cur⇢right == null) {
            cur⇢right = node
            node⇢parent = cur
            cur = null
         }
         else
            cur = cur⇢right
      }
   }

   node = node⇢parent
   while (node != null) {
      AVLTreeRebalance(tree, node)
      node = node⇢parent
   }
}

 

---

AVL Removals

Giving a key, an AVL tree remove operation removes the first-found matching node, restructuring the tree to preserve all AVL tree requirements. 

Removal begins by removing the node using the standard BST removal algorithm. 

After removing a node, all ancestors of the removed node, from the nodes' parent up to the root, are rebalanced. 

A node is rebalanced by first computing the node's balance factor, then performing rotations if the balance factor is 2 or -2. 

 

단순하게 BST removal algorithm 시행 이후 insertion에서와 마찬가지로 제거한 node의 부모 node부터 root node까지 모든 조상 node들의 balancing factor를 업데이트 해주고, 만약 2 또는 -2라면 적절하게 left/right rotation을 시행합니다. 

또한 rebalancing은 반복적으로 dynamically 적용되기 때문에, 최초 메소드 시행 시 root node였던 node가 balancing 되어 다른 노드가 root node가 된 이후에도 새롭게 root node가 된 node에게 반복적으로 balancing을 적용합니다. 

반복적 rebalancing은 root node가 balanced 상태라면 멈춥니다. (balancing factor = 1, 0, -1)

 

AVLTreeRebalance(tree, node) {
    AVLTreeUpdateHeight(node)
    if (AVLTreeGetBalance(Node) == -2) {
        if (AVLTreeGetBalance(node→right) == 1) {
            # right-left case
            AVLTreeRotateRight(tree, node→right)
        }
        return AVLTreeRotateLeft(tree, node)
    }
    else if (AVLTreeGetBalance(node) == 2) {
        if (AVLTreeGetBalance(node→left) == -1) {
            # left-right case
            AVLTreeRotateLeft(tree, node→left)
        }
        return AVLTreeRotateRight(tree, node)
    }
    return node
}


AVLTreeRemoveKey(tree, key) {
    node = BSTSearch(tree, key)
    return AVLTreeRemoveNode(tree, node)
}


AVLTreeRemoveNode(tree, node) {
    if (node == null) {
        return false
    }
    
    # Parent needed for rebalancing
    parent = node→parent
    
    # Case 1: Internal node with 2 children
    if (node→left != null && node→right != null) {
         # Find successor
         successor = node→right
         while (successor→left != null) {
             successor = successor→left
         }
         
         # Copy the key from the successor node
         node→key = sucecssor→key
         
         # Recursively remove successor
         AVLTreeRemoveNode(tree, successor)
         
         # Nothing left to do since the recursive call will have rebalanced
         return true
     }
     
     # Case 2: Root node (with 1 or 0 children)
     else if (node == tree→root) {
         if (node→left != null) {
             tree→root = node→left
         } else if (node→right != null) {
             tree→root = node→right
         } if (tree→root != null) {
             tree→root→parent = null
         }
         return true
     }
     
     # Case 3: Internal with left child only
     else if (node→left != null) {
         AVLTreeReplaceChild(parent, node, node→left)
     }
     
     # Case 4: Internal with right child only OR left
     else {
        AVLTreeReplaceChild(parent, node, node→right)
    }
    
    # Node is gone. Anything that was below node that has persisted is already correctly balanced
    # But ancestors of node may need rebalancing. 
    node = parent
    while (node != null) {
        AVLTreeRebalance(tree, node)
        node = node→parent
    }
    return true
}