# 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 treeTcontaining \(n-1\) internal nodes has \(n\) leaves.

### 17.4.1.3. Full Binary Tree Theorem (2)¶

Induction Step:Given treeTwith \(n\) internal nodes, pick internal node \(I\) with two leaf children. Remove \(I\)’s children, call resulting treeT’.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.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¶

### 17.4.1.9. BST as a Dictionary (1)¶

### 17.4.1.10. BST as a Dictionary (2)¶

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