Register

# 17.4. Binary Trees Part 2¶

## 17.4.1. Binary Trees Part 2¶

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

### 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¶

/** 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.7. Dictionary (2)¶

• How can we implement a dictionary?

• They might be sorted or unsorted.

• What are the pros and cons?

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

.

### 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?