3.1.1.1. 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.

(a)

(b)

3.1.1.2. 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 $n-1$ internal nodes has $n$ leaves.

3.1.1.3. 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.

3.1.1.4. 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.

3.1.1.5. Dictionary¶

// The Dictionary abstract class.
interface Dictionary {

  // Reinitialize dictionary
  void clear();

  // Insert a record
  // k: the key for the record being inserted.
  // e: the record being inserted.
  void insert(Comparable k, Object e);

  // Remove and return a record.
  // k: 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.
  Object remove(Comparable k);

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

  // Return a record matching "k" (null if none exists).
  // If multiple records match, return an arbitrary one.
  // k: the key of the record to find
  Object find(Comparable k);

  // Return the number of records in the dictionary.
  int size();
};

3.1.1.6. .¶

.

3.1.1.7. Dictionary (2)¶

• How can we implement a dictionary?

  • We know about array-based lists and linked lists.
  • They might be sorted or unsorted.
  • What are the pros and cons?

3.1.1.8. Binary Search Trees¶

3.1.1.9. 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++;
  }

3.1.1.10. 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; }

3.1.1.11. BST findhelp¶

0 / 0 Settings

<<<>>>

37

24

42

7

32

2

42

120

40

Saving...
Server Error
Resubmit

3.1.1.12. BST inserthelp¶

Settings

Saving...
Server Error
Resubmit

3.1.1.13. BST deletemax¶

Settings

Saving...
Server Error
Resubmit

3.1.1.14. BST removehelp¶

Settings

Saving...
Server Error
Resubmit

3.1.1.15. .¶

.

3.1.1.16. BST Analysis¶

Find: $O(d)$

Insert: $O(d)$

Delete: $O(d)$

$d =$ depth of the tree

$d$ is $O(\log n)$ if the tree is balanced.

What is the worst case cost? When?