Skip to Main Content
Programming Python, 3rd Edition
book

Programming Python, 3rd Edition

by Mark Lutz
August 2006
Intermediate to advanced content levelIntermediate to advanced
1600 pages
51h 46m
English
O'Reilly Media, Inc.
Content preview from Programming Python, 3rd 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 the 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.[*]

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 EmptyNode with a BinaryNode at the bottom ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Learning Python, 3rd Edition

Learning Python, 3rd Edition

Mark Lutz

Publisher Resources

ISBN: 0596009259Supplemental ContentErrata Page