4.2. Binary Trees Part 3¶
4.2.1. Binary Trees Part 3¶
4.2.1.1. Binary Tree Implementation (1)¶
“Simple” node model.
4.2.1.2. Binary Tree Implementation (2)¶
Internal nodes can be different from leaf nodes.
4.2.1.3. 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; } }
4.2.1.4. 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; } }
4.2.1.6. Design Patterns¶
Design patterns capture reusable pieces of design wisdom.
- Goals:
Quickly communicate design wisdom to new designers
Give a shared vocabulary to designers
4.2.1.7. 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); } }
4.2.1.8. 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(); } } }
4.2.1.9. Composite (3)¶
/** Preorder traversal */ public static void traverse(VarBinNode rt) { if (rt != null) { rt.traverse(); } }
4.2.1.10. 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.
4.2.1.11. 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 (of a smaller amount!) overhead.
Note that some space is needed to distinguish leaves from internal nodes.
