Chapter 14 Binary Trees
153
Representing hierarchal data isn’t the only reason computer scientists use trees. As you already
know, you can search a sorted binary tree in logarithmic time. While a logarithmic search isn’t as fast
as a constant
time lookup in a hash table, binary search trees offer a few advantages over hash tables.
The first advantage is memory use. Because of collisions, hash tables can be 10 or more times larger
than the amount of data you store in them.
Binary search trees, on the other hand, do not consume
any additional memory. Also, a binary search tree allows you to quickly
traverse your data in both
sorted and reverse sorted order, whereas you cannot traverse a hash table in sorted or reverse sorted
order because hash tables don’t store data in order.
Creating
a Binary Tree
Here is how to create a binary tree in Python:
class BinaryTree:
def __init__(self, value):
self.key = value
self.left_child = None
self.right_child = None
def insert_left(self, value):
if self.left_child == None:
self.left_child = BinaryTree(value)
else:
bin_tree = BinaryTree(value)
bin_tree.left_child = self.left_child
self.left_child = bin_tree
def insert_right(self, value):
if self.right_child == None:
self.right_child = BinaryTree(value)
else:
bin_tree = BinaryTree(value)
bin_tree.right_child = self.right_child
self.right_child = bin_tree
First, you define a class called
BinaryTree
to represent your tree.
BinaryTree
has three instance
variables:
key
,
left_child
, and
right_child
.
The variable
key
holds the node’s data (for instance, an
integer),
left_child
keeps track of the node’s left child, and
right_child
keeps
track of its right
child. When you create a child node for your tree, you create a new instance of your
BinaryTree
class,
which also
has a key, a left child, and a right child. Every child node is a subtree. A
subtree is a node
in a tree,
other than the root node, and its descendants. A subtree can have subtrees.
Next, you define a method called
insert_left
to create a child node and insert it into the left side
of your tree.
