CS2040s: Lecture 8 - Balanced Binary Search Tree (AVL)

Balanced Binary Search Tree (AVL)

AVL TREES

Perfectly Balance, as all things should be.

Previously, when look at normal BST, if it is imbalance, its o(n). But if it is balance,

ie. h= logn always => O(logn)

1. Keep a height variable at each node

o.height = max(o.left.height, o.right.height) + 1 

2.Maintain the variant: All nodes in BST must be height balanced 

Both sides must be height balanced.

|o.left.height() – o.right.height()| ≤ 1

3. Rebalance via rotations

Balance Factor:

  Define b(o) = o.left.height() – o.right.height()
  b(o) of an empty tree (null) is -1 //its oni one side
  if b(o) > 1 or b(o) < -1 for any o, the tree is no longer height balanced.  

Ensure that both left and right side of the node has at most a difference of 1

Balancing O(n) time because we need to go through every element to count.

Claim:

A height balance tree with n nodes has at most height h< 2logn so

Time to do any operation on the tree -> h= O(logn)

Rotations

4 types:
 Left rotation

Applies: Y is X 's right child
Objective: Want y to be X's parents but need to preserve BST properties

We want to shift Y up one level and X down one level

What is the worst case time complexity of left rotation
O(1)
->We are just moving references around

function rotateLeft(x)
   y = x.right // reassign parent
   y.parent = x.parent // make y into x’s parent
   x.parent = y // move B  x.right = y.left
  if (x.right is not null)
      x.right.parent = x // make x into y’s child
  y.left = x // update heights and parent referencereturn y 

//We need to write for both sides x and y

Is the BST property preserved for the parent?
Yes 

 Right rotation

Objective: Want y to be x’s parent
But must preserve BST properties.Applies: y is x’s left child.
function rotateRight(x)
  y = x.left // reassign parent
  y.parent = x.parent// make y into x’s parent
  x.parent = y // move B
  x.left = y.right
  if (x.left is not null)
     x.left.parent = x // make x into y’s child
y.right = x // update heights and parent reference
return y  

We turn Right when node is imbalance on the left (Left side is longer)
Turn left if node is imbalance on the right

 Left-Right rotation

AKA Double right
left rotate my left child first before right rotate myself
If the unbalance side follow this order: node , left, right



 Right-Left rotation

AKA double left
right rotate my right child first before left rotate myself
If the unbalance side follow this order: node , right , left

Inbalance can be caused by insertion and deletion

if tree is right heavy
   if tree’s right subtree is left heavy
            right rotate, left rotate
    else
            left rotate
else if tree is left heavy
         if tree’s left subtree is right heavy
                    left rotate, right rotate
         else
                    right rotate

We need to check
1. Parent is balance
2. If parent is not balance, check the child on the side which is imbalance
    if the child has balance factor 's sign is opposite of the parents, its a double rotate
    else its just a single rotate

When to balance?
Can rotation increase height of tree? No, it either decrease by one or leave it the same
Rotation required after insert: 1, Just swap the imbalance side of the tree, up to the root
Rotation maybe required after deletion: O(logN) We need to go all the way up to the root