Topics

Binary Tree Traversals

Running time of operations on Trees

How to ensure O(lg N) running time

AVL Trees

Heaps (the tree kind)

Binary Tree Traversals

Here is (another) class to represent a binary tree. It will be used to illustrate binary tree traversals. (link to the source code)

#ifndef BINTREENODE_H
#define BINTREENODE_H

template 
class binTreeNode;

#include "btnodevisitor.h"

template <class T>
class binTreeNode
{
public:
  T data;
  binTreeNode *left;
  binTreeNode *right;
  binTreeNode(const T& d) : data(d), left(0), right(0) {}
  binTreeNode(const T& d, binTreeNode *lf, binTreeNode *rt) :
    data(d), left(lf), right(rt) {}
  template <class S, class R>
  R accept(btNodeVisitor<T,S,R>& v, const S& x)
  {
    return v.visit(this, x);
  }
};
#endif

Exercises:

1. Create a binary tree.

2. The tree is not a "linear" structure. It's hard to know what order
data was inserted after the tree has been built.
What is a  "reasonable" order (or orders)?

3. Print all the data in the tree in a "reasonable" order.

4. A binary search tree has the properties
   a. The data in the tree has a natural ordering (e.g. intgers,
      strings, etc. have natural orderings. A type representing an
      Shape might not have a natural ordering.
   b. For every node in a binary search tree, the data is >= the
      data in its left child (if present) and < the data in its right
      child (if present). 

   What tree results from inserting the values 
	
  	          10, 1, 20, 15, 30, 3,4, 2

   into an initially empty binary search tree?

5. What is the height of the tree in 4?

6. How many comparisons does it take to find out that 17 is not in the
   tree? 

7. If the same data were inserted in order into a list, how
   many comparisions would be needed to find out that 17 is not in the
   list? 

8. Why is the height of a binary search tree important for
   insertion and find operations?

9. A balanced binary tree would have smaller height. What would be a
   definition of "balanced" that we could use in writing a balanced
   binary search tree class. That is, we would want to be able to test
   this condition in the insert method, so it needs to be fairly
   precise. 

10. Preorder traversal of a binary tree with root p:

	a. Visit the p (e.g. print the data in the node)
        b. Visit the tree rooted at p->left in preorder.
        c. Visit the tree rooted at p->right in preorder.

    What is the preorder traversal of the tree in 4?

11. What is the definition of postorder traversal? of inorder
traversal?

Traversals Example

(Link to source code and header file. )

...
typedef binTreeNode treenode;

void preorderPrint(treenode *p)
{
  if ( p == 0 ) return;
  cout << p->data << " ";
  preorderPrint(p->left);
  preorderPrint(p->right);
}

void inorderPrint(treenode *p)
{
  if ( p == 0 ) return;
  inorderPrint(p->left);
  cout << p->data << " ";
  inorderPrint(p->right);
}

void postorderPrint(treenode *p)
{
  if ( p == 0 ) return;
  postorderPrint(p->left);
  postorderPrint(p->right);
  cout << p->data << " ";
}

void doDrawTree(treenode *p, string lpad, string rpad)
{
  string pad = lpad.substr(0, lpad.size() - 1);
  if (p == 0) return;
  doDrawTree(p->right, rpad + "    |", rpad + "     ");
  cout << pad << "+--" << setw(3) << p->data << endl;
  doDrawTree(p->left,  lpad + "     ", lpad + "    |");
}
void drawTree(treenode *p)
{
  doDrawTree(p, " ", " ");
}

int main()
{

  treenode *root;
  root = new treenode(5);
  root->left = new treenode(3);
  root->right = new treenode(10);
  treenode *p = root->right;
  p->left = new treenode(8);
  p->right = new treenode(15);
  p->left->left = new treenode(7);
  p->left->right = new treenode(9);
  root->left->right = new treenode(4);
  root->left->left = new treenode(1);

  drawTree(root);
  cout << endl;

  cout << "Preorder Traversal:" << endl;
  preorderPrint(root);

  cout << "\nInorder Traversal:" << endl;
  inorderPrint(root);

  cout << "\nPostorder Traversal:" << endl;
  postorderPrint(root);

  return 0;
}

Examle Output


          +-- 15
     +-- 10
     |    |    +--  9
     |    +--  8
     |         +--  7
+--  5
     |    +--  4
     +--  3
          +--  1

Preorder Traversal:
5 3 1 4 10 8 7 9 15 
Inorder Traversal:
1 3 4 5 7 8 9 10 15 
Postorder Traversal:
1 4 3 7 9 8 15 10 5

More Examples

           A
         /   \
        B     C
       / \   / 
      D   E F

Preorder:   A B D E C F
Inorder:    D B E A F C
Postorder:  D E B F C A

Exercise 1.

1. The preorder traversal of a binary tree is

	X Y A B C D

2. The inorder traversal of the same tree is

	Y A X C B D

3. What is the postorder traversal?

Separating Visitors from Binary Trees

The idea: 
(a) Binary Tree represents structural arrangement of data.

(b) Allow flexibility in order of visiting and processing data
elements in a Binary Tree.

The binTreeNode Class (again)

#ifndef BINTREENODE_H
#define BINTREENODE_H

template 
class binTreeNode;

#include "btnodevisitor.h"

template 
class binTreeNode
{
public:
  T data;
  binTreeNode *left;
  binTreeNode *right;
  binTreeNode(const T& d) : data(d), left(0), right(0) {}
  binTreeNode(const T& d, binTreeNode *lf, binTreeNode *rt) :
    data(d), left(lf), right(rt) {}
  template 
  R accept(btNodeVisitor& v, const S& x)
  {
    return v.visit(this, x);
  }
};
#endif

BinaryTreeNodeVisitor Abstract Class

(Link to source code)


template 
class btNodeVisitor;

#include "binTreeNode.h"

template 
class btNodeVisitor
{
public:
  virtual R visit(binTreeNode *p, const S& x) = 0;
};

A Postfix Visitor

(Link to source code)


#include "btnodevisitor.h"

class postfix: public btNodeVisitor
{
public:

  int visit(binTreeNode *p, const int& x)
  {
    if (p == 0) {
      return 0;
    }
    p->left->accept(*this, 0);
    p->right->accept(*this, 0);
    cout << p->data << " ";
    return 0;
  }
};

A SumVisitor

(Link to source code)


#include "btnodevisitor.h"

class sumvisitor: public btNodeVisitor
{
public:

  int visit(binTreeNode *p, const int& x)
  {
    int y = x;
    if (p == 0) {
      return y;
    }
    y += p->left->accept(*this, 0);
    y += p->data;
    y += p->right->accept(*this, 0);
    return y;
  }
};

Drawing the Binary Search Tree

1. What order were the nodes visited to produce this drawing?

          +-- 15
     +-- 10
     |    |    +--  9
     |    +--  8
     |         +--  7
+--  5
     |    +--  4
     +--  3
          +--  1

Preorder Traversal:
5 3 1 4 10 8 7 9 15 
Inorder Traversal:
1 3 4 5 7 8 9 10 15 
Postorder Traversal:
1 4 3 7 9 8 15 10 5

A Draw visitor

(Link to source code)

Running Times and Algorithms

Let f(N) = number of microseconds to solve a problem of size N for an
algorithm. The what is the biggest size problem that can be solved in
1 minute. 

     f(N)        Largest N solvable in 1 minute
     log₂(N)        10^18000000
     N              60000000
     Nlog₂(N)        2811900
     N²                 7746
     N³                  391
     2^N                   25

Running time of operations on binary search trees - Worst Case

Insertion/find/deletion:

 Worst case: Tree is just a list; e.g., every node has a null left
             link.

 Worst case running time: O(n) where n is the number of nodes.

Running times for find

Let d be the depth of the node to 'find'.

The running time for the operation on such a node is O(d).

So in general,

   Worst case is O(h) where h is the height of the tree.

"Average" Height of a Binary Search Tree

What do we mean by the "average" height of binary search trees with n nodes?

One possibility is to compute the heights of the binary search trees resulting from inserting each permutation of 1,2,...,n into an initially empty tree. Then compute the average of these n! heights.

It turns out that this average is O(lg n).

This is somewhat hard to prove. However, some intuition can be gained by considering the following:

For n = 4, of the 24 permutations of 1-4 for insertion, the resulting
tree heights and their frequencies are:

	height  frequency
          3        8
          2       16

So the average height is 2.333...

log(n+1) = log(5) = 2.3219...

One could also write a program to determine the heights and their frequencies for all permutations of n for other values of n.

The average height could then be computed as the average height of the n! trees generated for each permutaion of the values 1,2,...,n.

How do we guarantee a height of O(log n)?

We could try to ensure that the heights of both subtrees of the root have equal height or if that is not possible, guarantee that the heights differ by at most 1.

That is not quite enough. For example, the tree we get from inserting the following would have that property, but the height would be approximately n/2 = O(n), not O(log n):

  Insert the values 0,1,2,...,100   (n=101) in the order

  50, 49,48,47,46, ...,2,1,0,51,52,53,54,55,56,...,100

Both right and left subtrees would have height 49.

We have to ensure that each subtree is also balanced.

So one property would be that at every node in the tree:

The difference between the heights of the left and right subtrees
should be at most 1.

To handle cases like 

               5
              /
             4

where the height of the left subtree of 5 is 0, 

the height of an empty subtree is defined to be -1.

AVL Trees

AVL trees are Binary Search Trees with the additional property that the methods maintain a "balanced" property:

For every node in an AVL tree, the heights of its children differ by
at most 1.

For the purpose of this definition (and also the implementation), an empty child will be considered to be at height -1.

The AVL tree below shows the height of each node.

The children of 600 have heights 

	 0 (left child 550) and
	-1 (right child empty).

and these differ by only 1.

Insertion into an AVL Tree

Maintaining the AVL Tree property, requires that the insert includes some code to rebalance portions of the tree if the property would otherwise be violated.

For example if we try to insert the value 525 into this tree in the usual way as a child of 550, the height of 550 would become 1, while the right child (empty) is still at height -1, a difference of 2.

The Rotate Methods

This problem is solved by:

1. First insert in the usual way for a binary search tree either in
the left subtree or right subtree. (Duplicates are not allowed in
this version.)
2. Check if the heights of the two children subtrees differs by 2.
   If so, then rotate nodes to restore the AVL properties.

There are two kinds of rotations: single or double.

The double rotation can be implemented by calling 2 single rotation methods.

There are also two directions to rotate: with the left child or the right child.

The 4 Rotate Methods

The 4 methods are:


1. private static Node rotateWithLeftChild( Node k2 )

2. private static Node doubleWithLeftChild( Node k3 )

3. private static Node rotateWithRightChild( Node k2 )

4. private static Node doubleWithRightChild( Node k3 )

Example

Fix Unbalanced Node with rotateWithRightChild

Returning to the example AVL tree, we try to insert 525:

The rotateWithLeftChild method below is called to rotate the left child, 550 to become the parent of 525 and 600:

Example Requiring a Double Rotation

If we try to insert 425 into this tree, node 500 would then violate the AVL condition. However, we can't use the rotateWithLeftChild method:

A "double" rotation will first rotate 400 with its new right child (450), and then rotate 500 with its new left child (450 again in a new position) to get:

Same Double Rotation, Bigger Tree

A slightly more typical example of a double rotation is shown below. The value 450 is being inserted:

The same 2 single rotations as before will make 425 the new root with left child 400 and right child 500.

What happens to 425's previous left and right children?

The rotateWithLeftChild Method

Here is the implementation for this method:

  private static Node rotateWithLeftChild( Node k2 )
  {
    // Rotate with k2's left child
    Node k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;

    // Adjust the heights since the nodes have been rotated.
    k2.height = Math.max( height(k2.left), height(k2.right) ) + 1;
    k1.height = Math.max( height(k1.left), k2.height ) + 1;

    return k1;
  }

The height method is a static method just returns the height of the node passed to it, but also handles the case if null is passed. In the later case, height returns -1.

The doubleWithLeftChild Method

Here is Weiss's implementation of this method:

  private static Node doubleWithLeftChild( Node k3 )
  {
    k3.left = rotateWithRightChild( k3.left );
    return rotateWithLeftChild( k3 );
  }

As promised, it is implemented by performing 2 single rotations.

The VisAvlTree Class

This is a java program that has an AvlTree member and which displays the data from this AVL tree as it allows the user to interactively insert data (no deletions, although it wouldn't be hard to add those too).

Priority Queues and Trees

We previously mentioned minPriority queues and maxPriority queues. A minPriority queue would have the following methods as an abstract data type:

template <class T>
PriorityQueue
{
public:
  T deleteMin();
  public void insert(const T& x);
  public boolean empty();
}

A class could implement this interface through composition using any of the various container classes such as C++'s vector or list, or deque, as I asked you to do.

The suggested implementations are not be especially efficient, however. We can do better. In fact we can achieve this efficiency:

                            Running Time
      operation             Proportional To:              Big-Oh Notation
      deleteMin()           log(N)                          O(log(N))
      insert                log(N)                          O(log(N))

Recall for a list implementation, the best we can do is: 

      deleteMin             constant                        O(1)
      insert                N                               O(N)

or the otherway around

      deleteMin             N                               O(N) 
      insert                1                               O(1)


Which is better?

Replacing the list

The problem with using the list (or vector or deque) to implement the PriorityQueue is that we want both operations, insert and deleteMin to be efficient.

A balanced binary search tree would be one possibility. E.g., an AVL tree. What would the running times be for the two operations?

Another balanced tree which does not require the AVL type rotations, is the MinHeap. (There is also a MaxHeap).

MinHeap

A MinHeap is a binary tree with the following properties:

  1. All leaf nodes are at depth d or d-1 for some d.
  2. All nodes at depth < d - 1 have two children.
  3. All nodes at depth d are as far to the left as possible.
  4. The value at each node must be <= the values of its
     children.

Examples

Exampes:

   This is a MinHeap:        This is not a MinHeap
           1                          1                 
       +---|---+                  +---|---+             
       |       |    	          |       |             
       8       3    	          8       3             
     +-|-+   +-|-+  	        +-|-+   +-|-+           
     |   |   |   |  	        |   |   |   |           
     9  10  12   4  	        9  10  12   2    
   +-|              	      +-|                       
   |                	      |                         
   11               	      11

Heap Insertion


Insertion works by 

 1. Add the new item as a leaf in the next available position.
    (This may destroy the heap condition!)

 2. "Bubble" the new item up until the heap condition is satisfied.
    Swap the item with its parent if it is smaller than the parent.

Example

Example of insertion:

Insert 1 into the heap

            2                           2                   
        +---|---+                   +---|---+               
        |       |                   |       |               
        8       3     =>            8       3                     
      +-|-+   +-|-+               +-|-+   +-|-+             
      |   |   |                   |   |   |   |           
      9  10  12                   9  10  12   1    




                    2                            1                      
                +---|---+                    +---|---+              
                |       |                    |       |              
 =>             8       1     =>             8       2             
              +-|-+   +-|-+                +-|-+   +-|-+            
              |   |   |   |                |   |   |   |            
              9  10  12   3                9  10  12   3

Heap Deletion

Deletion from a heap is only slightly more complicated.

Heap Deletion:

Deletion works by 

 1. Remove the last item in the heap and use it to replace the item to
    be deleted. 
    (This may destroy the heap condition!)

 2. "Bubble" the new item down until the heap condition is satisfied.
    Swap the item with its smaller of its children if either
    child is smaller than the item.