Programming Python, Second Edition

Binary Search Trees

Binary trees are a data structure that impose an order on inserted nodes: items less than a node are stored in its left subtree, and items greater than a node are inserted in the right. At the bottom, the subtrees are empty. Because of this structure, binary trees naturally support quick, recursive traversals -- at least ideally, every time you follow a link to a subtree, you divide the search space in half.^[137]

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.

Rather than 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 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 EmptyNode with a BinaryNode at the bottom (see Example ...