3.2. Binary Trees Part 3¶
3.2.1. Binary Trees Part 3¶
3.2.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?
3.2.1.2. Comparison (2)¶
- Fundamental issue: Defining the key is a property of the context, NOT a property of the record.
3.2.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; } }
3.2.1.4. .¶
.
3.2.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() { return theKey.toString() + ", " + theVal.toString(); } }
3.2.1.6. .¶
.
3.2.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(A, j, j-1); }What is being compared?
What if we want to find the record that has a given key?
3.2.1.8. Binary Tree Implementation (1)¶
"Simple" node model.
3.2.1.9. Binary Tree Implementation (2)¶
Internal nodes can be different from leaf nodes.
3.2.1.10. Inheritance (1)¶
// Base class for expression tree nodes interface VarBinNode { boolean isLeaf(); // All subclasses must implement } /** Leaf node */ class VarLeafNode implements VarBinNode { private String operand; // Operand value VarLeafNode(String val) { operand = val; } boolean isLeaf() { return true; } String value() { return operand; } }
3.2.1.11. Inheritance (2)¶
/** Internal node */ 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; } boolean isLeaf() { return false; } VarBinNode leftchild() { return left; } VarBinNode rightchild() { return right; } Character value() { return operator; } }
3.2.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
3.2.1.14. Composite (1)¶
/** Base class: Composite */ interface VarBinNode { boolean isLeaf(); void traverse(); } /** Leaf node: Composite */ class VarLeafNode implements VarBinNode { private String operand; // Operand value VarLeafNode(String val) { operand = val; } boolean isLeaf() { return true; } String value() { return operand; } void traverse() { Visit.VisitLeafNode(operand); } }
3.2.1.15. Composite (2)¶
/** Internal node: Composite */ 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; } boolean isLeaf() { return false; } VarBinNode leftchild() { return left; } VarBinNode rightchild() { return right; } Character value() { return operator; } void traverse() { Visit.VisitInternalNode(operator); if (left != null) left.traverse(); if (right != null) right.traverse(); } }
3.2.1.16. Composite (3)¶
/** Preorder traversal */ static void traverse(VarBinNode rt) { if (rt != null) rt.traverse(); }
3.2.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.
3.2.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.
