Loading [MathJax]/jax/output/HTML-CSS/jax.js

3.Full and Complete Binary Trees§

Full binary tree: Each node is either a leaf or internal node with exactly two non-empty children.

Complete binary tree: If the height of the tree is d, then all leaves except possibly level d are completely full. The bottom level has all nodes to the left side.

Created with Raphaël 2.1.2
Created with Raphaël 2.1.2
(a)
(b)

Full Binary Tree Theorem (1)

Theorem: The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.

Proof (by Mathematical Induction):

Base case: A full binary tree with 1 internal node must have two leaf nodes.

Induction Hypothesis: Assume any full binary tree T containing n1 internal nodes has n leaves.

Full Binary Tree Theorem (2)

Induction Step: Given tree T with n internal nodes, pick internal node I with two leaf children. Remove I’s children, call resulting tree T’.

By induction hypothesis, T’ is a full binary tree with n leaves.

Restore I’s two children. The number of internal nodes has now gone up by 1 to reach n. The number of leaves has also gone up by 1.

Full Binary Tree Corollary

Theorem: The number of null pointers in a non-empty tree is one more than the number of nodes in the tree.

Proof: Replace all null pointers with a pointer to an empty leaf node. This is a full binary tree.

Dictionary

/** The Dictionary abstract class. */
public interface Dictionary {

  /** Reinitialize dictionary */
  public void clear();

  /** Insert a record
      @param key The key for the record being inserted.
      @param elem The record being inserted. */
  public void insert(Comparable key, Object elem);

  /** Remove and return a record.
      @param key The key of the record to be removed.
      @return A maching record. If multiple records match
      "k", remove an arbitrary one. Return null if no record
      with key "k" exists. */
  public Object remove(Comparable key);

  /** Remove and return an arbitrary record from dictionary.
      @return the record removed, or null if none exists. */
  public Object removeAny();

  /** @return A record matching "k" (null if none exists).
      If multiple records match, return an arbitrary one.
      @param key The key of the record to find */
  public Object find(Comparable key);

  /** @return The number of records in the dictionary. */
  public int size();
}

.

.

Dictionary (2)

Binary Search Trees

Created with Raphaël 2.1.2
A
B
Created with Raphaël 2.1.2
A
B

BST as a Dictionary (1)

// Binary Search Tree implementation
class BST {
  private BSTNode root; // Root of the BST
  private int nodecount; // Number of nodes in the BST

  // constructor
  BST() { root = null; nodecount = 0; }

  // Reinitialize tree
  public void clear() { root = null; nodecount = 0; }

  // Insert a record into the tree.
  // Records can be anything, but they must be Comparable
  // e: The record to insert.
  public void insert(Comparable e) {
    root = inserthelp(root, e);
    nodecount++;
  }

BST as a Dictionary (2)

  // Remove a record from the tree
  // key: The key value of record to remove
  // Returns the record removed, null if there is none.
  public Comparable remove(Comparable key) {
    Comparable temp = findhelp(root, key); // First find it
    if (temp != null) {
      root = removehelp(root, key); // Now remove it
      nodecount--;
    }
    return temp;
  }

  // Return the record with key value k, null if none exists
  // key: The key value to find
  public Comparable find(Comparable key) { return findhelp(root, key); }

  // Return the number of records in the dictionary
  public int size() { return nodecount; }

BST findhelp

0 / 0 Settings
<<<>>>

  • private Comparable findhelp(BSTNode rt, Comparable key) {
  • if (rt == null) return null;
  • if (rt.value().compareTo(key) > 0)
  • return findhelp(rt.left(), key);
  • else if (rt.value().compareTo(key) == 0)
  • return rt.value();
  • else return findhelp(rt.right(), key);
  • }
Created with Raphaël 2.1.2
37
24
42
7
32
2
42
120
40
Proficient Saving... Error Saving
Server Error
Resubmit

BST inserthelp

0 / 0 Settings
<<<>>>

  • private BSTNode inserthelp(BSTNode rt, Comparable e) {
  • if (rt == null) return new BSTNode(e);
  • if (rt.value().compareTo(e) >= 0)
  • rt.setLeft(inserthelp(rt.left(), e));
  • else
  • rt.setRight(inserthelp(rt.right(), e));
  • return rt;
  • }
Created with Raphaël 2.1.2
37
24
42
7
32
2
42
120
40
30
Proficient Saving... Error Saving
Server Error
Resubmit

BST deletemax

0 / 0 Settings
<<<>>>

  • // Delete the maximum valued element in a subtree
  • private BSTNode deletemax(BSTNode rt) {
  • if (rt.right() == null) return rt.left();
  • rt.setRight(deletemax(rt.right()));
  • return rt;
  • }
Created with Raphaël 2.1.2
10
5
20
12
15
Proficient Saving... Error Saving
Server Error
Resubmit

BST removehelp

0 / 0 Settings
<<<>>>

  • private BSTNode removehelp(BSTNode rt, Comparable key) {
  • if (rt == null) return null;
  • if (rt.value().compareTo(key) > 0)
  • rt.setLeft(removehelp(rt.left(), key));
  • else if (rt.value().compareTo(key) < 0)
  • rt.setRight(removehelp(rt.right(), key));
  • else { // Found it
  • if (rt.left() == null) return rt.right();
  • else if (rt.right() == null) return rt.left();
  • else { // Two children
  • BSTNode temp = getmax(rt.left());
  • rt.setValue(temp.value());
  • rt.setLeft(deletemax(rt.left()));
  • }
  • }
  • return rt;
  • }
Created with Raphaël 2.1.2
37
24
42
7
32
2
30
42
120
40
Proficient Saving... Error Saving
Server Error
Resubmit

.

.

BST Analysis

Find: O(d)

Insert: O(d)

Delete: O(d)

d= depth of the tree

d is O(logn) if the tree is balanced.

What is the worst case cost? When?