10.18. Binary Trees Part 3¶
10.18.1. Binary Trees Part 3¶
10.18.1.1. Binary Tree Implementation (1)¶
“Simple” node model.
10.18.1.2. Binary Tree Implementation (2)¶
Internal nodes can be different from leaf nodes.
10.18.1.3. Inheritance (1)¶
10.18.1.4. Inheritance (2)¶
10.18.1.5. Inheritance (3)¶
10.18.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
10.18.1.7. Composite (1)¶
10.18.1.8. Composite (2)¶
10.18.1.9. Composite (3)¶
10.18.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.
10.18.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.
