These lecture notes are based on chapter 9 in ``Data Structures, Algorithms, & Software Principles in C'' by Thomas Standish.

Overview

• previously - intro to trees
• heap
  • partial order on labels
  • priority queue
  • relatively good retrieval, insert performance
• binary search tree
  • total order on labels
  • relatively efficient retrieval
  • easy to insert, delete keys

Sequential Representation of a Tree

A complete binary tree is a tree that has all leaves on the same level or two adjacent levels, such that the leaves in the bottommost level are as far left as possible.

This is a complete binary tree.

     9
    / \
   5   8
  / \    
 3   4

This is not (leaves aren't to the left).

     9
    / \
   5   8
  / \   \
 3   4   7

This is not (leaves aren't on adjacent levels).

       9
      / \ 
     5   7
    / \      
   3   3     
  / \
 1   4

Why should you care? Because we can efficiently store a complete binary tree in an array as follows.

• label nodes in level order (see diagram)
• put node into proper array position
• space efficient representation
• for any node at array position A[n]
  • root is at A[1]
  • left child is at A[2*n
  • right child is at A[2*n + 1]
  • parent is at A[n/2]
  • A[i] is a leaf if 2*i is bigger than n

A level-order labeled tree, level-order means visit nodes across rather than down the tree first.

      a 1 
     / \
 2  b   c 3
   / \    
4 d   e 5

Sequential representation

    A[1] = a
    A[2] = b
    A[3] = c
    A[4] = d
    A[5] = e

Verify that the relationships listed above hold, i.e., parent of d at A[4] is A[4/2] = A[2] = b.

Heaps

A heap is a complete binary tree with values stored in its nodes such that no child has a value bigger than the value of the parent.

Below is a heap.

     9
    / \
   8   2
  / \    
 6   4

A heap provides a representation for a priority queue. Example: messages processed by priority at a server

• messages given priority weighting, higher numbers give better service
• highly dynamic, messages coming and going frequently
• need efficient insert new message and remove highest priority message

Removal causes heap to be reheapified. For example if we remove 9

     ?
    / \
   8   2
  / \    
 6   4

then we reheapify by copying rightmost leaf to root (4 becomes the root)

     4
    / \
   8   2
  /      
 6

and then we recursively reestablish the heap property as follows: if the parent is greater than a child, swap the parent with the highest priority child. Keep swapping until no more swaps are possible. So in the above tree, first we would swamp 4 with 8.

     8
    / \
   4   2
  /      
 6

Then we would swap 4 with 6.

     8
    / \
   6   2
  /      
 4

The final swap yields a heap!

The cost of removing an item (reheapifiying after removing the item) is O(log n). The algorithm just traverses one path in the tree, which is O(log n) in length. For each node on that path it performs at most two comparisons and one swap (3 operations -> constant time). So overall the algorithm has a worst case time complexity of O(log n).

Space complexity is O(n) since a sequential array representation can be used.

Analysis of a Heap

Consider three implementations of a priority queue

1. as an unordered array
   • create priority queue is O(1)
   • remove highest priority item is O(n) (search through array to find max)
   • insert a new item is O(1)
2. as an ordered list
   • create priority queue is O(n log n) (must sort by priority)
   • remove highest priority item is O(1)
   • insert a new item is O(n) (traverse list to find where in list it belongs)
3. as a heap
   • create priority queue is O(n) (we didn't study this)
   • remove highest priority item is O(log n)
   • insert a new item is O(log n)

Binary Search Trees

The primary characteristic of a binary search tree is that, for each node, keys in the left subtree are less than the key in the node which is in turn less than the keys in the right subtree. Below is an example of a binary search tree.

     8
    / \
   4   9
  / \    
 2   6

The tree shown below is not a binary search tree since 4 is to the right of 6.

     8
    / \
   6   9
  / \    
 2   4

Binary search trees support efficient retrieval of keys. How efficient?

• internal path length is sum distances to each node
• external path length is internal path length plus dead-ends
• when searching for a key, 2 comparisons are made at each node
• to sucessfully find key at level i costs 2*i + 1 comparisons
• if search for nodes is equally likely, and search is successful then average cost is (2*i + n)/n
• E = I + 2n.
• average unsuccessful search costs 2*E/(n+1)