{1, 3, 9}
>>> set(v) # set constructor
{1, 3, 9}>>> {k: k+100 for k in v} # dict comprehension
{1: 101, 3: 103, 9: 109}
>>> dict(zip(v, [99] * len(v))) # dict constructor
{1: 99, 3: 99, 9: 99}
>>> dict.fromkeys(v, 99) # dict method
{1: 99, 3: 99, 9: 99}So why bother with a custom search data structure implementation here, given such
flexible built-ins? In some applications, you might not, but here especially, a custom
implementation often makes sense to allow for customized tree algorithms. For in-
stance, custom tree balancing can help speed lookups in pathological cases, and might
outperform the generalized hashing algorithms used in dictionaries and sets. Moreover,
the same motivations we gave for custom stacks and sets apply here as well—by en-
capsulating tree access in class-based interfaces, we support future extension and
change in more manageable ways.
Implementing Binary Trees
Binary trees are named for the implied branch-like structure of their subtree links.
Typically, their nodes are implemented as a triple of values: (LeftSubtree, NodeValue,
RightSubtree). Beyond that, there is fairly wide latitude in the tree implementation.
Here we’ll use a class-based approach:
- BinaryTree is a header object, which initializes and manages the actual tree.
- EmptyNode is the empty object, shared at all empty subtrees (at the bottom).
- BinaryNode objects are nonempty tree nodes with a value and two subtrees.
Instead of coding distinct search functions, binary trees are constructed with “smart”
objects—class instances that know how to handle insert/lookup and printing requests
and pass them to subtree objects. In fact, this is another example of the object-oriented
programming (OOP) composition relationship in action: tree nodes embed other tree
nodes and pass search requests off to the embedded subtrees. A single empty class
instance is shared by all empty subtrees in a binary tree, and inserts replace an Empty
Node with a BinaryNode at the bottom. Example 18-14 shows what this means in code.
Example 18-14. PP4E\Dstruct\Classics\btree.py
"a valueless binary search tree"
class BinaryTree:
def init(self): self.tree = EmptyNode()
def repr(self): return repr(self.tree)
def lookup(self, value): return self.tree.lookup(value)
def insert(self, value): self.tree = self.tree.insert(value)
1386 | Chapter 18: Data Structures