CSC301 Apr29

slide version

single file version

Contents

  1. AVL Tree insertion demo (again)
  2. Adapting BST Tree Methods for an AVL Tree
  3. Insertion in a Binary Search Tree
  4. Insertion in an AVL Tree
  5. Which Rotations?
  6. Rotations in Pictures
  7. Order of growth of AVL Tree methods
  8. Level Order Traversal
  9. Practice Problem 1
  10. Practice Problem 2
  11. Practice Problem 3
  12. Practice Problem 4
  13. Practice Problem 5
  14. Practice Problem 6
  15. Appendix: Height of an AVL Tree
  16. Estimating f(h)

AVL Tree insertion demo (again)[1] [top]

Which rotations to use, when?

Adapting BST Tree Methods for an AVL Tree[2] [top]

Assume a private Node class is used for an AVL tree class:


public class AVL<Key extends Comparable<Key>, Value>
{
  // AVL members and methods
  ...

     // inner class
     private class Node 
     {
       private Key key;
       private Value val;
       private Node left;
       private Node right;
       private int height; // optional

       private  Node() {}
       private Node(Key k, Value v) {
	 key = k;
         val = v;
	 height = 0; // optional? Not really
	 left = right = null;
       }
     }
}

Insertion in a Binary Search Tree[3] [top]

Recall insertion (without rebalancing) into a Binary Search Tree. We assume the BST has a private member root whose value is null if the BST is empty:

      private Node root;
    
public void put(Key k, Value v)
{
   root = put(k, v, root);
}

private Node put(Key k, Value v, Node t)
{
  if ( t == null ) {
     t = new Node(k,v);
  } else if ( k.compareTo(t.key) < 0 ) {
     t.left = put(k, v, t.left);
  } else if ( k.compareTo(t.key) > 0 ) {
     t.right = put(k, v, t.right);
  }
  return t;
}

Insertion in an AVL Tree[4] [top]

An AVL tree is a binary search tree with a balance condtition

The insertion for an AVL tree uses the same code as for any biinary search tree (above), but must add code to keep the AVL tree balanced and to compute changes in heights of nodes:

public void put(Key k, Value v)
{
   root = put(k, v, root);
}

private Node put(Key k, Value v, Node t)
{
  if ( t == null ) {
     t = new Node(k, v);
  } else if ( k.compareTo(t.key) < 0 ) {
     t.left = put(k, v, t.left);
     // If t is unbalanced call rotate method(s) to restore the balance
  } else if ( k.compareTo(t.key) > 0 ) {
     t.right = put(k, v, t.right);
     // If t is unbalanced call rotate method(s) to restore the balance
  }
  // Recompute the height of t if height is member of Node
  return t;
}

Which Rotations?[5] [top]

Which rotation should be used when a node bcomes unbalanced depends on which child subtree (left or right) the offending value was inserted and which subtree (left or right) of that child.

Rotations in Pictures[6] [top]

Single rotation with P's right child R (change 2 links)

Double rotation with P's right child Q (change 4 links)

Order of growth of AVL Tree methods[7] [top]

For a binary search tree (which includes AVL trees), the order of growth of the put, get, delete, min, max, floor, ceiling, rank, and select methods all are determined by the height the tree.

Fact:

For an AVL tree, the height = O(log(N)), where N is the number of keys.

This follows from the fact that if an AVL tree has height h, the number of keys, N, can't be too small. More precisely,

      N >= 2h / 2

Solving for h, this means

      h / 2 <= log(N)

So

      h <= 2log(N)

(See the appendix below for the details.)

Level Order Traversal[8] [top]

The level number (or depth) of a node in a binary search tree is the distance from the root.

Level order means to list the keys in order by their level and for keys on the same level, list them from left to right (that is, in increasing order).

Listing ALL the keys in a binary search tree in their usual order doesn't give any information about the shape of the tree. Is it balanced, essentially a linked list, or what?

However, if the keys are listed in level order you can use this as the INPUT order to rebuild the original tree! So instead of drawing binary search trees they can be described by giving the level order list of keys.

Practice Problem 1[9] [top]

Level order of a binary search tree: 80 30 90 10 85 5 20 89 12.

What is the level order after inserting 70?

Practice Problem 2[10] [top]

Level order of a binary search tree: 80 30 90 10 85 5 20 89 12.

What is the level order after Hibbard deletion of 5, 10 and 80?

(Hibbard deletion of a Node with 2 children replaces that Node with its successor.

Practice Problem 3[11] [top]

Level order of a binary search tree: 80 30 90 10 85 5 20 89 12.

If we search for key 15, what keys in the tree are compared for this search miss?

What about a search for key 100?

Practice Problem 4[12] [top]

Level order of a binary search tree: 80 30 90 10 85 5 20 89 12.

What is the level of key 20?

What is the height of the subtree at 20?

Practice Problem 5[13] [top]

Level order of a binary search tree: 80 50 100 30 70 90 105 20 40 60 85 10

Is this an AVL tree?

Practice Problem 6[14] [top]

Level order of an AVL tree: 80 50 100 30 70 90 105 20 40 60 85 10

The key 65 is inserted into this tree. Is a rotation required?

Appendix: Height of an AVL Tree[15] [top]

Here is a sketch of the proof that an AVL tree with N keys has height h = O(log(N)).

Let f(h) be the minimum number of keys in an AVL tree of height h.

(For example, try to draw AVL trees of heights 1, 2, and 3 with the smallest number of keys.)

      f(-1) = 0
      f(0) = 1
      f(1) = 2

For h >= 1,

Estimating f(h)[16] [top]

      f(h) = 1 + f(h-1) + f(h-2)

Since f(h-1) >= f(h-2), we get

      f(h) > 2f(h-2)   (for all h >= 1)
f(7) > 2f(5) f(8) > 2f(6)
f(7) > 22f(3) f(8) > 22f(4)
f(7) > 23f(1) f(8) > 23f(2)
f(7) > 232 f(8) > 24f(0)
f(7) > 24 f(8) > 24

In general,

      f(h) > 2ceiling(h/2) > 2h/2

where ceiling(x) means the smallest integer that is >= x.