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)
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.
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.
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.
Dictionary
/** The Dictionary abstract class. */publicinterfaceDictionary{/** Reinitialize dictionary */publicvoidclear();/** Insert a record @param key The key for the record being inserted. @param elem The record being inserted. */publicvoidinsert(Comparablekey,Objectelem);/** 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. */publicObjectremove(Comparablekey);/** Remove and return an arbitrary record from dictionary. @return the record removed, or null if none exists. */publicObjectremoveAny();/** @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 */publicObjectfind(Comparablekey);/** @return The number of records in the dictionary. */publicintsize();}
.
.
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?
Binary Search Trees
A
B
A
B
BST as a Dictionary (1)
// Binary Search Tree implementationclassBST{privateBSTNoderoot;// Root of the BSTprivateintnodecount;// Number of nodes in the BST// constructorBST(){root=null;nodecount=0;}// Reinitialize treepublicvoidclear(){root=null;nodecount=0;}// Insert a record into the tree.// Records can be anything, but they must be Comparable// e: The record to insert.publicvoidinsert(Comparablee){root=inserthelp(root,e);nodecount++;}
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.publicComparableremove(Comparablekey){Comparabletemp=findhelp(root,key);// First find itif(temp!=null){root=removehelp(root,key);// Now remove itnodecount--;}returntemp;}// Return the record with key value k, null if none exists// key: The key value to findpublicComparablefind(Comparablekey){returnfindhelp(root,key);}// Return the number of records in the dictionarypublicintsize(){returnnodecount;}