CS 240: Lecture 16 - Binary Tree

This name of this class includes the term Data Structures. We are looking at ways to structure data to speed up the computational tasks we are trying to perform. So far we've seen two ways to structure collections of data: in an array or in a linked list. Today we add a third: a tree.

Trees are often—but not always—implemented as a linked structure. Each node in the tree stores a value and links to its children. When nodes have no more than two children, we have a binary tree.

Terms

Linked lists had just a few anatomical terms: head, tail, next, and previous. Trees have many more terms. Let's run through a few of these as we examine some random binary trees.

• root: the topmost node in a tree
• parent: a node that has children
• child: a node that has a parent
• leaf: a node that has no children
• edge: the relationship between a parent and child
• depth: the number of edges from the root to a descendent node
• height: the depth of the bottommost node in a tree; confusingly, it's one less than the number of levels
• ancestor: a parent node that eventually begets some other node
• descendent: a node that is begotten by some other node
• sibling: a node that has the same parent as another

Properties

How many nodes can appear at each depth? Drawing pictures helps answer this question. We see the following:

Each new level holds twice as many nodes as the level above it. This table inspires a couple of related questions:

• What is the total number of nodes that appear in a perfect tree of height \(h\)?
• What is the least height that a tree can have if it has \(n\) nodes?

Binary Search Tree

Trees model branching data. You find branching data in a file system, in decision logic, and in recursive grammatical structures. They can also be used to accelerate search.

Last week we saw how hash tables achieve a search with constant time complexity. This is hard to beat. But sometimes you need more operations than a hash table can provide, like a total ordering of all the items. A binary search tree provides this, and it also provides a very fast search.

In a binary search tree, the key at the root is ideally in the middle of the data. All keys to the left are less than the root's key, and all keys to the right are greater than the root's key. To search for a key, we start at the root and recurse down exactly one of the children based on the relative ordering of the keys. Since we are throwing away “half” the remaining items on each step, we have a binary search.

You've already seen binary search with arrays, so why do we need a different data structure that lends itself to a binary search? Adding new items to an array is a linear time operation. But adding new items to a tree is \(O(\log_2 n)\) if the tree is balanced.

Together we'll construct some binary trees using magnetic letters.

Tree Map

Binary search trees can be used to implement the map interface that we introduced with hash tables. Together we'll write the TreeMap class below, which supports just the put and get operations. These operations are easier to write recursively than iteratively. We'll use some private helper methods to prime the recursive descent through the tree.

public class TreeMap<K extends Comparable<K>, V> {
  private Node root;

  public TreeMap() {
    root = null;
  }

  public void put(K key, V value) {
    root = put(key, value, root);
  }

  private Node put(K key, V value, Node node) {
    if (node == null) {
      return new Node(key, value);
    } else {
      int order = key.compareTo(node.key);
      if (order == 0) {
        node.value = value;
      } else if (order < 0) {
        node.left = put(key, value, node.left);
      } else {
        node.right = put(key, value, node.right);
      }
      return node;
    }
  }

  public V get(K key) {
    return get(key, root);
  }

  private V get(K key, Node node) {
    if (node == null) {
      return null;
    } else {
      int order = key.compareTo(node.key);
      if (order == 0) {
        return node.value;
      } else if (order < 0) {
        return get(key, node.left);
      } else {
        return get(key, node.right);
      }
    }
  }

  private class Node {
    K key;
    V value;
    Node left;
    Node right;

    Node(K key, V value) {
      this.key = key;
      this.value = value;
    }
  }
}

TODO

You've got a few things to do before we meet again:

See you next time!

P.S. It's time for a haiku: