Michael's Wiki

Trace: › avl_trees

An [http://en.wikipedia.org/wiki/AVL_tree AVL tree] is a binary search tree which maintains balance by clever use of rotation after updates.

For each node x:

  • * Height(left subtree) and Height(right subtree) must differ by less than 1.
  • * If the difference is greater than 1, a rotation is done

Insertion

For an AVL tree, there are always at most 2 rotations after an insertion

  1. Insert the new value at a new leaf node
  2. Through a path from the new leaf back to the root:
    1. update heights
    2. if an imbalance has been created, perform a rotation
Deletion

The case analysis for this is very messy…

  1. Delete the target node, replacing it with one of its children
  2. Through a path from the child back to the root:
    1. update heights
    2. if an imbalance has been created, perform a rotation
Last modified: 2017/01/15 02:47
CC Attribution-Share Alike 4.0 International Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International