# 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)}$.

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 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 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 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.

Left Rotation

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

Right Rotation

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

Inserting in lr Left Rotation Right Rotation

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

Inserting in rl Right Rotation Left Rotation

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

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

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

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

## Example 1 - Rotate Left ¶

• $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

## Example 2 - Rotate Right ¶

• $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

## Example 3 - Rotate Left Right ¶

• $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

Left Rotation Right Rotation

## Example 4 - Rotate Right Left ¶

• $bf(tree) = depth(left) - depth(right) = 0 - 2 = -2$
• $bf(right) = depth(r\_left) - depth(r\_right) = 1 - 0 = 1$