Lecture: 8
Date: Jan 24, 2008

Recall BST.

Q: What does the class diagram look like?

   +---------------------+
   +-----------------+   |
   v                 |   |
A BST is one of      |   |
- a (make-leaf)      |   |
- a (make-node name BST BST)

(define-struct node (value left right))

Draw class diagram, draw example BST with 5 nodes.
Make this example.

Q: Does it makes sense to have new Leaf() everywhere?

We could do IBST leaf = new Leaf(); and use leaf everywhere.

Q: What's missing in this definition?
A: A comment on the fundamental invariant of BST.  A comment on
   whether repetitions are OK.

Develop the method insert: inserts a new node into BST.

Q: Header and purpose?

??? insert(???)

// Represent a binary search tree.
interface IBST {
  // insert given value into this tree.
  IBST insert(int value);
}

Make an example of how to use this.

First, a really simple one:

leaf.insert(5) --> new Node(5, leaf, leaf);

In Leaf:

// insert given value into this leaf.
IBST insert(int value) {
  /* Template: value int */
  return new Node(value, this, this);
}

Note: we could have said new Leaf instead of this, but we have a leaf
in our hands, ie. this!

Now let's make another example.

leaf.insert(5).insert(3) --> new Node(5,new Node(3, leaf, leaf), leaf);

In Node:

// insert given value into this node.
IBST insert(int value) {
  /* Template
  ... this.value ... int
  ... this.left ... IBST
  ... this.right ... IBST

  Q: Is this all?  What else do we know about left, right?
  They are IBST's and therefore implement insert!

  ... this.left.insert(int)  ... IBST
  ... this.right.insert(int) ... IBST
  */
  ...
}

Q: How can we re-interpret the purpose statement for these recursive calls?

A: Substitute "this" with "this left subtree", "this right subtree".

this.left.insert(int)  === "insert given node into this left subtree".

Q: In English, how do we insert a value into a node?
A: If the given value is less than the value at this node, insert into
   the left subtree, otherwise insert into the right.

Q: Is that all?  Where does this go wrong?
A: We need to make a new node with the same value as this node, and
   with the new subtrees.

Code it.

if (value >= this.value)
  return new Node(this.value, this.left, this.right.insert(value));
else
  return new Node(this.value, this.left.insert(value), this.right);


We want to be able to draw BSTs.  What might we need to do this?

- compute the height of a tree
- compute the width of a tree

// Represent a binary search tree.
interface IBST {
  // insert given value into this tree.
  IBST insert(int value);

  // compute the height of a tree.
  int height();

  // compute the width of a tree
  int width();
}

Examples:

leaf.height() --> 0  This gives us the code for our bas case (Leaf).
tree.height() --> 3

In Node:

// compute the height of this tree.
in height() {
  /* Template
  ... this.value ...
  ... this.left ...
  ... this.right ...

  AND
  "Compute the height of this left subtree."
  ... this.left.height() ... int
  "Compute the height of this right subtree."
  ... this.right.height() ... int
  */

  return 1+max(this.left.height(), this.right.height());
}


We wish listed an operation max.  Since it is a helper to our class
Node, we put it in Node (even though it doesn't really depend on
Node-- we don't see "this" in it's definition).

// return the maximum of two given numbers.
int max(int x, int y) {
  if x>y return x; else return y;
}

Q: How can we test this max method?

IBST n = new Node(5, leaf, leaf);
n.max(10,15);

This won't work.  Why?