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 ...
Get Programming Python, Second Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
