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.
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.
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.
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.
// 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();
};
.
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?
// 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++;
}
// 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; }
.
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?
