G5BADS: Lecture 13
16 November 2000
Natasha Alechina

Problems with Binary Search Trees

What happens if we construct a binary search tree where new items are added in order (e.g. 1, 2, 3, 4, 5).

Balance in Binary Search Trees

If new items to be inserted arrive in random order, search tree remains reasonably balanced.

But if they arrive in non-random order, tree is likely to become unbalanced:

Hence deep and inefficient to search.

Need to revise tree insertion mechanism to preserve reasonable balance. (Perfect balance is very expensive to maintain and actually impossible for the even number of nodes).

Height Balance

A binary tree is height balanced if

the difference in height between the left and right subtrees is no greater than 1, and
the left and right subtrees are also height balanced

Height balanced tree:

Top Down and Bottom Up Insertion

Top down insertion algorithms make changes to the tree (necessary to keep the tree balanced) as they search for the place to insert the item. They make one pass through the tree.

Bottom up insertion algorithms first insert the item, and then work back through the tree making changes which are necessary to keep the tree balanced. They are less efficient because they make two passes through the tree.

Red-Black Trees

Red-black trees are binary search trees which come with additional information about the nodes: the nodes are coloured red or black. This is just for bookkeeping during insertion. The following rules should always be satisfied:

The root is always black;
A red node cannot have red children;
Every path from the root to a leaf or to a node with only one child should have the same number of black nodes.

The difficult part is how to keep the rules satisfied while inserting a new node. This is done top down, changing colours and moving (`rotating') subtrees while searching for a place to insert the node.

The insertion algorithm for red-black trees is very complicated. Instead we will study in detail the algorithm for AVL trees (which is bottom up).

AVL Trees

AVL (Adelson-Velskii & Landis) trees are binary search trees where nodes also have additional information: the difference in depth between their left and right subtrees.

The difference is represented as a number equal to the depth of the right subtree minus the depth of the left subtree.

In an AVL tree, only the following values are allowed:

0: left \& right subtrees of same depth
1: right subtree one deeper than left
-1: left subtree one deeper than right

If after insertion the number becomes larger than 1 or less than -1 the tree is restructured.

Insertion into AVL Tree

Insert new leaf node, as for ordinary binary search tree.
Then work back up from new leaf to root, checking if any height imbalance has been introduced (computing new balance factors).
Perform rotation to correct height imbalance. (which rotation depends on the balance factor).
At most one (single or double) rotation will be needed to restore balance.

Rotations

The restructuring is done by performing a rotation.

A rotation is performed around some node X.

It can be

single right rotation,
single left rotation or
a double rotation.

Right Rotation

           X               A
          /               / \ 
         /               /   \
        A       ==>     B     X
       / \                   /
      /   \                 /
     B     C               C

Right rotation around X:

X moves down and to the right, into the position of its right child;
X's right subtree is unchanged.
X's left child A moves up to take X's place. X is now A's new right child.
This leaves the old right child of A unaccounted for. Since it comes from the left of X, it is less than X. So it becomes X's new left child.

Left Rotation

The tree is unbalanced on the right.

Left rotation around X gives:

              B
             / \
            /   \
           X     D
          / \     \
         /   \     \
        A     C     E

Double Rotations

Two single rotations in opposite directions (around two different nodes).

For example:

The tree with 30 as the top is unbalanced (balance factor -2) but rotating it to the right gives another unbalanced tree:

Double Rotation (II)

Make single left rotation around node 25:

             20                    20
            /  \                  /  \
           /    \                /    \
          10    30              10    30
               /                      /
              /           ==>        /
             25                     27
              \                    /
               \                  /
                27               25

Then make right rotation around node 30:

             20                    20
            /  \                  /  \
           /    \                /    \
          10    30              10    27
               /                      / \
              /           ==>        /   \
             27                     25   30
            /  
           /    
          25

Which Rotation?

Balance factor -2 (left subtree longer), balance factor of the left daughter -1 or 0: single right rotation

          -2        -2
         /          /
        /          /
      -1          0
      /          / \
     /          /   \

Balance factor 2 (right subtree longer), balance factor of the right daughter 1 or 0: single left rotation

           2         2
            \         \
             \         \         
              1         0
               \       / \
                \     /   \

Balance factor -2, balance factor of the left daughter 1: double rotation, around the daughter to the left, around the root to the right.
Balance factor 2, balance factor of the right daughter -1: double rotation, around the daughter to the right, around the root to the left.

Searching AVL Trees

Same algorithm as for search on ordered binary tree:

Compare node value with target
If identical, stop
Else descend down either left or right branch depending on comparison
and repeat
Continue either until target found
or until you can descend no further

Deleting from AVL Tree

Delete node essentially as for ordinary binary search tree.

Find leftmost node/subtree of deleted node's right subtree.
Delete leftmost subtree (keep a copy).
Work back up to deleted node, restoring any imbalances
Replace deleted node by leftmost subtree.
Work back up to root, restoring any imbalances.

Note: May require multiple rotations.

Sketch of implementation

AVL trees can be implemented as binary trees with an additional field balanceFactor.

Only give one of the cases (left or right), the other is symmetrical and replaced by ...

AVLTree avlInsert(ItemType item)
----------------------------
if(item <= value)  // Insert into left subtree
    if(left == null)
        // No left daughter: add new subtree with balanceFactor = 0
      left = InitializeAVL(item,0)
      balanceFactor-- // Mark extra depth on left
    else
      oldbf = left.balanceFactor
      left = left.avlInsert(item)
      if ((left.balanceFactor != oldbf) and (left.balanceFactor != 0))
      // Insertion changes balanceFactor on the left,
      // and left is not perfectly balanced
         balanceFactor--
else  // Insert into right subtree
      ...


if ((balanceFactor < -1) or (balanceFactor > 1))
    return this.rebalance()
else return this

AVLTree rebalance()
----------------

if (balanceFactor < -1)
 // Left side heavy: rotate right
  if(left.balanceFactor <= 0)
    // Single rotation
       return this.rotateRight()
  else  // Double rotation
       left = left.rotateLeft()
       return this.rotateRight()

if (balanceFactor >  1)
 // Right side heavy: rotate left
  ...

AVLTree rotateLeft()
-----------------

oldTop = this
newTop = oldTop.right
// Make rotation:
oldTop.right = newTop.left
newTop.left = oldTop
// Update balance factors:
otBF = oldTop.balanceFactor
ntBF = newTop.balanceFactor
newTop.balanceFactor = (ntBF - 1) - max(0, ntBF+1-otBF)
oldTop.balanceFactor = (otBF - 1) - max(0, ntBF)
return newTop

How balance factors are calculated

Consider left rotation. Let

d1 be the depth of the left subtree of oldTop,
d2 the depth of the left subtree of newTop,
d3 the depth of the right subtree of newTop:


         oldTop                         newTop
        /|      \ 1                   1 /    |\
       / |       \ newTop       oldTop /     | \
      /  |      /|\                   /|\    |  \
     /   |     /|| \                 / | \   |   \
    /    |    / ||  \               /  | |\  | d3 \
   /  d1 |   /  || d3\             /   | | \ |_____\
  /______|  / d2||____\           / d1 | |d2\
           /____|                /_____| |___\

The depth of the right subtree of oldTop is max(d2,d3) + 1.
otBF = max(d2, d3) + 1 - d1,
ntBF = d3 - d2, so
d3 = d2 + ntBF and
d1 = max(d2, d3) + 1 - otBF.
new otBF= d2 - d1
new ntBF = d3 - (1 + max(d1,d2))
After substitutions get
new otBF = (otBF - 1) - max(0, ntBF)
new ntBF = (ntBF - 1) - max(0, ntBF+1-otBF).

Summary

Binary search trees can become imbalanced, leading to inefficient search

AVL trees: height balanced binary search trees.

Leads to reasonable search complexity: O(log₂N).

Efficient (but complicated) algorithms for maintaing height balance under insertion and deletion.

Requires rotations to restore balance.