17.5. Binary Trees Part 3¶
17.5.1. Binary Trees Part 3¶
17.5.1.1. Comparison (1)¶
How do we generalize the concept of comparison?
“<” is not good enough. String < String won’t give you what you want.
Need a general way to get the key out of a record
- Define a method record.key()?
[Note for C++ users: Operator overloading is effectively the same thing.]
That is not good enough. What if we want to search on different key fields?
17.5.1.2. Comparison (2)¶
Fundamental issue: The key is a property of the context, NOT a property of the record.
17.5.1.3. KVpair¶
This is a truly general way to solve the problem.
// KVPair class definition public class KVPair implements Comparable { Comparable theKey; Object theVal; KVPair(Comparable k, Object v) { theKey = k; theVal = v; } public int compareTo(Object it) throws ClassCastException { if (it instanceof KVPair) // Compare two KVPair objects return theKey.compareTo(((KVPair)it).key()); else if (it instanceof Comparable) // Compare against a key value return theKey.compareTo(it); else throw new ClassCastException("Something comparable is expected."); } public Comparable key() { return theKey; } public Object value() { return theVal; } public String toString() { String s = "("; if (theKey != null) { s += theKey.toString(); } else { s += "null"; } s += ", "; if (theVal != null) { s += theVal.toString(); } else { s += "null"; } s += ")"; return s; } }// KVPair class definition public class KVPair<K extends Comparable<K>, E> implements Comparable<KVPair<K, E>> { K theKey; E theVal; KVPair(K k, E v) { theKey = k; theVal = v; } // Compare KVPairs public int compareTo(KVPair<K,E> it) { return theKey.compareTo(it.key()); } // Compare against a key public int compareTo(K it) { return theKey.compareTo(it); } public K key() { return theKey; } public E value() { return theVal; } public String toString() { String s = "("; if (theKey != null) { s += theKey.toString(); } else { s += "null"; } s += ", "; if (theVal != null) { s += theVal.toString(); } else { s += "null"; } s += ")"; return s; } }
17.5.1.4. .¶
.
17.5.1.5. KVpair: Generics¶
// KVPair class definition public class KVPair<K extends Comparable<K>, E> implements Comparable<KVPair<K, E>> { K theKey; E theVal; KVPair(K k, E v) { theKey = k; theVal = v; } // Compare KVPairs public int compareTo(KVPair<K,E> it) { return theKey.compareTo(it.key()); } // Compare against a key public int compareTo(K it) { return theKey.compareTo(it); } public K key() { return theKey; } public E value() { return theVal; } public String toString() { String s = "("; if (theKey != null) { s += theKey.toString(); } else { s += "null"; } s += ", "; if (theVal != null) { s += theVal.toString(); } else { s += "null"; } s += ")"; return s; } }
17.5.1.6. .¶
.
17.5.1.7. Using the KVpair (1)¶
static <T extends Comparable<T>> void inssort(T[] A) { for (int i=1; i<A.length; i++) // Insert i'th record for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--) Swap.swap(A, j, j-1); }static <T extends Comparable<T>> void inssort(T[] A) { for (int i=1; i<A.length; i++) { // Insert i'th record for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--) { swap(A, j, j-1); } } }def inssort(A): for i in range(len(A)): # Insert i'th record j = i; while (j != 0) and (A[j] < A[j-1]): swap(A, j, j - 1) j -= 1What is being compared?
What if we want to find the record that has a given key?
17.5.1.8. Binary Tree Implementation (1)¶
“Simple” node model.
17.5.1.9. Binary Tree Implementation (2)¶
Internal nodes can be different from leaf nodes.
17.5.1.10. Inheritance (1)¶
// Base class for expression tree nodes public interface VarBinNode { public boolean isLeaf(); // All subclasses must implement } /** Leaf node */ public class VarLeafNode implements VarBinNode { private String operand; // Operand value VarLeafNode(String val) { operand = val; } public boolean isLeaf() { return true; } public String value() { return operand; } }
17.5.1.11. Inheritance (2)¶
// Internal node public class VarIntlNode implements VarBinNode { private VarBinNode left; // Left child private VarBinNode right; // Right child private Character operator; // Operator value VarIntlNode(Character op, VarBinNode l, VarBinNode r) { operator = op; left = l; right = r; } public boolean isLeaf() { return false; } public VarBinNode leftchild() { return left; } public VarBinNode rightchild() { return right; } public Character value() { return operator; } }
17.5.1.13. Design Patterns¶
Design patterns capture reusable pieces of design wisdom.
- Goals:
Quickly communicate design wisdom to new designers
Give a shared vocabulary to designers
17.5.1.14. Composite (1)¶
/** Base class: Composite */ public interface VarBinNode { public boolean isLeaf(); public void traverse(); } /** Leaf node: Composite */ public class VarLeafNode implements VarBinNode { private String operand; // Operand value VarLeafNode(String val) { operand = val; } public boolean isLeaf() { return true; } public String value() { return operand; } public void traverse() { Visit.VisitLeafNode(operand); } }
17.5.1.15. Composite (2)¶
/** Internal node: Composite */ public class VarIntlNode implements VarBinNode { // Internal node private VarBinNode left; // Left child private VarBinNode right; // Right child private Character operator; // Operator value VarIntlNode(Character op, VarBinNode l, VarBinNode r) { operator = op; left = l; right = r; } public boolean isLeaf() { return false; } public VarBinNode leftchild() { return left; } public VarBinNode rightchild() { return right; } public Character value() { return operator; } public void traverse() { Visit.VisitInternalNode(operator); if (left != null) { left.traverse(); } if (right != null) { right.traverse(); } } }
17.5.1.16. Composite (3)¶
/** Preorder traversal */ public static void traverse(VarBinNode rt) { if (rt != null) { rt.traverse(); } }
17.5.1.17. Space Overhead (1)¶
- From the Full Binary Tree Theorem:
Half of the pointers are null.
If leaves store only data, then overhead depends on whether this is full tree.
Ex: Full tree, all nodes the same, with two pointers to children and one to element
Total space required is \((3p + d)n\)
Overhead: \(3pn\)
If \(p = d\), this means \(3p/(3p + d) = 3/4\) overhead.
17.5.1.18. Space Overhead (2)¶
Eliminate pointers from the leaf nodes
\[\frac{n/2(2p)}{n/2(2p) + dn} = \frac{p}{p + d}\]This is 1/2 if \(p = d\).
\((2p)/(2p + d)\) if data only at leaves \(\Rightarrow\) 2/3 overhead.
Note that some method is needed to distinguish leaves from internal nodes.
