OCAML Course

AVL trees

Go back

An AVL (Adelson-Velsky and Landis) is a balanced Binary Search Trees. We are making sure that the depth is $\pm 1$, instead of having something like the tree below with your usual Binary Search Trees. The complexity is now $\log{(n)}$.

ABR bad - complexity O(n)

Everything is the same as for a Binary Search Trees, but we will balance our tree in add and remove.


  • ✅: faster than an ordered list for add, remove
  • ✅: better than an unbalanced BST
  • ✅: aside from add and remove, same implementation as a BST
  • ❌: add and remove are difficult to understand/implement
  • ❌: sightly slower than an ordered list for mem, get_min
  • ❌: Unless storing the cardinal, calculating it takes too much time

The time was tested with a sample of around 500 000 randomly generated values in [0;10000].

>>>>>>>>>> TIME FOR LISTS <<<<<<<<<<
Average time of add:                     0.000046
Average time of remove:                  0.000047
Average time for mem:                    0.002340
Average time for get_min:                0.001870
Average time for cardinal:               0.353290 (long)
>>>>>>>>>> TIME FOR BST <<<<<<<<<<
Average time of add:                     0.000002
Average time of remove:                  0.000002
Average time for mem:                    0.006270
Average time for get_min:                0.003290
Average time for cardinal:               inf (too long)
>>>>>>>>>> TIME FOR AVL <<<<<<<<<<
Average time of add:                     0.000010
Average time of remove:                  0.000005
Average time for mem:                    0.003430
Average time for get_min:                0.002800
Average time for cardinal:               inf (too long)

Depth

You will have to check whether your tree is balanced. The depth is the height of your tree. The depth of the root is the maximum between the depth of its children.

In OCaml, it's strongly advised to store the depth of the tree. I'm starting from 0, you may start from 1 (replace d+1 with d, and add 1 to max ...).

(* elt is the type of one element *)
type avl = Empty | Node of set * elt * int * set
let get_depth s = match s with | Empty -> 0 | Node(_,_,d,_) -> d + 1
(* create a node *)
let node l h r = Node(l, h, max (get_depth l) (get_depth r), r)

My note 🙄: the depth is usually called the height of the tree, but it was disturbing me because we were also calling "h" the head of the tree, now with the depth I'm fine 😬🙄.


Rotations

We got four rotations, that we will use to balance our tree.

AVL Rotate Left - Begin Left Rotation AVL Rotate Left - End

(1/4) Left Rotation: If we are adding a child in rr.

AVL Rotate Right - Begin Right Rotation AVL Rotate Right - End

(2/4) Right Rotation: If we are adding a child in ll.

AVL Rotate Left-Right - Begin Inserting in lr AVL Rotate Left-Right - Balance Left Rotation AVL Rotate Left-Right - Half done Right Rotation AVL Rotate Left-Right - End

(3/4) Left-Right Rotation: If we are adding a child in lr (=lrh if lr is empty, otherwise either lrl or lrr).

AVL Rotate Right-Left - Begin Inserting in rl AVL Rotate Right-Left - Balance Right Rotation AVL Rotate Right-Left - Half done Left Rotation AVL Rotate Right-Left - End

(4/4) Right-Left Rotation: If we are adding a child in rl (=rlh if lr is empty, otherwise either rll or rlr).


Balance your tree

You know about the depth/height. Each node got this information.

Depth AVL The tree was almost balanced, but not anymore after adding 4 Depth AVL

Notes

  • We are allowing a difference of depth of $\pm 1$
  • The difference is now 2

We can see it in our code by checking what we call the Balance factor (bf). This is the difference of depth between two branches (left minus right).

  • check in which side the tree in unbalanced
    • bf(tree) = 2: then left balanced
    • bf(tree) = -2: then right balanced
    • else (if 0, 1, or -1): then almost balanced or balanced (do nothing)
  • if right balanced, check the balance factor of the right
    • bf(right) = 1: Rotate Right Left
    • bf(right) = 0: ❌ (not possible)
    • bf(right) = -1: Rotate Left
  • if left balanced, check the balance factor of the left
    • bf(left) = 1: Rotate Right
    • bf(left) = 0: ❌ (not possible)
    • bf(left) = -1: Rotate Left Right

Examples

Example 1 - Rotate Left

AVL example 1 - Rotate left

  • Adding 5
  • $bf(tree) = depth(left) - depth(right) = 0 - 2 = -2$
  • The tree is Right balanced
  • $bf(right) = depth(r\_left) - depth(r\_right) = 0 - 1 = -1$
  • Rotate Left

AVL example 1 - Rotate left - init AVL example 1 - Rotate left - do AVL example 1 - Rotate left - clean

Example 2 - Rotate Right

AVL example 2 - Rotate right

  • Adding 0
  • $bf(tree) = depth(left) - depth(right) = 2 - 0 = 2$
  • The tree is Left balanced
  • $bf(left) = depth(l\_left) - depth(l\_right) = 1 - 0 = 1$
  • Rotate Right

AVL example 2 - Rotate right - init AVL example 2 - Rotate right - do AVL example 2 - Rotate right - clean

Example 3 - Rotate Left Right

AVL example 3 - Rotate Left Right

  • Adding 2
  • $bf(tree) = depth(left) - depth(right) = 2 - 0 = 2$
  • The tree is Left balanced
  • $bf(left) = depth(l\_left) - depth(l\_right) = 0 - 1 = -1$
  • Rotate Left Right
    • We will Rotate Left the left
    • We will Rotate Right the tree

AVL example 3 - Rotate Left Right - Begin Left Rotation AVL example 3 - Rotate Left Right - Left Rotation Right Rotation AVL example 3 - Rotate Left Right - Right Rotation AVL example 3 - Rotate Left Right - Done

Example 4 - Rotate Right Left

AVL example 4 - Rotate Right Left

  • Adding 2
  • $bf(tree) = depth(left) - depth(right) = 0 - 2 = -2$
  • The tree is Right balanced
  • $bf(right) = depth(r\_left) - depth(r\_right) = 1 - 0 = 1$
  • Rotate Right Left
    • We will Rotate Right the right
    • We will Rotate Left the tree

AVL example 4 - Rotate Right Left - Begin Right Rotation AVL example 4 - Rotate Right Left - Right Rotation Left Rotation AVL example 4 - Rotate Right Left - Left Rotation AVL example 4 - Rotate Right Left - Done