not address data structures of radically different form—like those of the next two
sections.
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, and hence fast lookup and search in a
wide variety of applications—at least ideally, every time you follow a link to a subtree,
you divide the search space in half.
Built-in Options
Here too, Python supports search operations with built-in tools. Dictionaries, for ex-
ample, already provide a highly optimized, C-coded search table tool. In fact, indexing
a dictionary by key directly is likely to be faster than searching a Python-coded
equivalent:
>>> x = {} # empty dict
>>> for i in [3, 1, 9, 2, 7]: x[i] = None # insert
...
>>> x
{7: None, 1: None, 2: None, 3: None, 9: None}
>>>
>>> for i in range(8): print((i, i in x), end=' ') # lookup
...
(0, False) (1, True) (2, True) (3, True) (4, False) (5, False) (6, False) (7, True)Because dictionaries are built into the language, they are always available and will usu-
ally be faster than Python-based data structure implementations. Built-in sets can often
offer similar functionality—in fact, it’s not too much of an abstraction to think of sets
as valueless dictionaries:
>>> x = set() # empty set
>>> for i in [3, 1, 9, 2, 7]: x.add(i) # insert
...
>>> x
{7, 1, 2, 3, 9}
>>> for i in range(8): print((i, i in x), end=' ') # lookup
...
(0, False) (1, True) (2, True) (3, True) (4, False) (5, False) (6, False) (7, True)In fact, there are a variety of ways to insert items into both sets and dictionaries; both
are useful for checking if a key is stored, but dictionaries further allow search keys to
have associated values:
>>> v = [3, 1, 9]>>> {k for k in v} # set comprehensionBinary Search Trees | 1385