17.4.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)

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

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

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

17.4.1.5. Dictionary¶

• Java
• Java (Generic)

/** 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();
}

/** The Dictionary abstract class. */
public interface Dictionary<K, E> {

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

  /** Insert a record
      @param k The key for the record being inserted.
      @param e The record being inserted. */
  public void insert(K key, E elem);

  /** Remove and return a record.
      @param 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. */
  public E remove(K key);

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

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

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

17.4.1.6. .¶

.

17.4.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?

17.4.1.8. Binary Search Trees¶

A

B

A

B

(a)

(b)

A

B

EMPTY

A

EMPTY

B

(c)

(d)

17.4.1.9. BST as a Dictionary (1)¶

17.4.1.10. BST as a Dictionary (2)¶

17.4.1.11. BST findhelp¶

1 / 17 Settings

<<<>>>

Consider searching for the record with key value 32 in this tree. We call the findhelp method with a pointer to the BST root (the node with key value 37).

37

24

42

7

32

2

42

120

40

rt

Saving...
Server Error
Resubmit

17.4.1.12. BST inserthelp¶

1 / 22 Settings

<<<>>>

Consider inserting a record with key value 30 in this tree. We call the inserthelp method with a pointer to the BST root (the node with value 37).

37

24

42

7

32

2

42

120

40

30

rt

root

Saving...
Server Error
Resubmit

17.4.1.13. BST deletemax¶

1 / 6 Settings

<<<>>>

To remove the node with the maximum key value from a subtree, first find that node by starting at the subtree root and continuously move down the right link until there is no further right link to follow.

10

5

20

12

15

rt

Saving...
Server Error
Resubmit

17.4.1.14. BST removehelp¶

1 / 46 Settings

<<<>>>

Let's look a few examples for removehelp. We will start with an easy case. Let's see what happens when we delete 30 from this tree.

37

24

42

7

32

2

30

42

120

40

30

30

rt

temp

Saving...
Server Error
Resubmit

17.4.1.15. .¶

.

17.4.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?