In the last lecture we introduced binary trees, plus various tree-related terms such as the depth of a tree node, the height of a tree, and so on.
We can represent a binary tree in Python using an object for each node, similarly to how we represent linked lists. Here is a Node class we can use for binary trees:
class Node:
def __init__(self, val, left, right):
self.val = val
self.left = left # left child, or None if absent
self.right = right # right child, or None if absent
We will generally refer to a tree
using a pointer
to its root node. We
will use None
to represent the empty tree, just
as we used None
for the empty linked list. In all
leaf nodes, left
and right
will be None.
Here is a small binary tree with just 3 nodes:
We can build this tree in Python as follows:
l = Node(7, None, None) r = Node(5, None, None) root = Node(4, l, r)
Here's a recursive function that counts the number of nodes in a binary tree:
def size(n):
if n == None: # empty tree
return 0
return 1 + size(n.left) + size(n.right)Let's try it on the tree we just built:
>>> size(root) 3
Recursion is a natural fit for trees, since the pattern of recursive calls in a function like this one can mirror the tree structure.
Here's a recursive function that computes the height of a binary tree:
def height(node):
if node == None:
return -1
return max(height(node.left), height(node.right)) + 1Let's try it:
>>> height(root) 1
The constant -1 in this function may seem surprising. Recall that the height of a binary tree is defined as the greatest depth of any node. If a binary tree has only a single node, then the depth of that node is 0, so the tree's height is 0. And so if a tree is empty, meaning that it has no nodes at all, then for consistency it must have a height of one less than that, or -1.
As another example, let's write a function that generates a complete binary tree of a given height h. Each node of the tree will contain a random value from 0 .. 99. Once more we will use recursion:
def complete(h):
if h == -1:
return None
left = complete(h - 1) # generate left subtree
right = complete(h - 1) # generate right subtree
return Node(randrange(100), left, right)Now we can easily generate a large tree:
>>> t = complete(10) >>> size(t) 2047 >>> height(t) 10
A binary search tree is a binary tree in which the values are ordered in a particular way that makes searching easy: for any node N with value v,
all values in N's left subtree are less than v
all values in N's right subtree are greater than v
For example, here is a binary search tree of integers:
In the last lecture, we saw an abstract data type called a set, supporting the following operations:
We can use a binary search tree to store a set. To do this, we'll write a TreeSet class that holds the current root of a binary tree:
class TreeSet:
def __init__(self):
self.root = NoneIt is not difficult to find whether a binary tree
contains a given value x. We
begin at the root. If the root's value is x, then we are done.
Otherwise, we compare x
to
the root's value v. If x
<
v, we move to the left child; if x
>
v, we move to the right child. We proceed in this way until we have
found x or
until we hit None,
in which case x is
not in the tree.
Here's
how we can implement this in the TreeSet
class:
def contains(self, x):
n = self.root
while n != None:
if x == n.val:
return True
if x < n.val:
n = n.left
else:
n = n.right
return FalseInserting a value into a binary search tree is
also pretty straightforward. Beginning at the root, we look for an
insertion position, proceeding down the tree just as in the above
algorithm for contains. When we reach an empty left or
right child, we place the new node there. In the TreeSet
class:
# add a value, or do nothing if already present
def add(self, x):
n = Node(x, None, None) # new node to add
p = self.root
if p == None:
self.root = n
return
while True:
if x == p.val:
return # already present
elif x < p.val:
if p.left == None:
p.left = n
return
else:
p = p.left
else: # x > p.val
if p.right == None:
p.right = n
return
else:
p = p.rightDeleting a value from a binary search tree is a bit trickier. It's not hard to find the node to delete: we just walk down the tree, just like when searching or inserting. Once we've found the node N we want to delete, there are several cases.
If N is a leaf (it has no children), we can just remove it from the tree.
If N has only a single child, we replace N with its child. For example, we can delete node 15 in the binary tree above by replacing it with 18.
If N has two children, then we will replace
its value by the next highest value in the tree. To do this, we
start at N's right child and follow left child pointers for as long
as we can. This wil take us to the smallest node in N's right
subtree, which must be the next highest node in the tree after N.
Call this node M. We can easily remove M from the right subtree: M
has no left child, so we can remove it following either case (a) or
(b) above. Now we set N's value to the value that M had.
As
a concrete example, suppose that we want to delete the root node
(with value 10) in the tree above. This node has two children. We
start at its right child (20) and follow its left child pointer to
15. That’s as far as we can go in following left child pointers,
since 15 has no left child. So now we remove 15 (following case b
above), and then replace 10 with 15 at the root.
We won't give an implementation of this operation here, but writing this yourself is an excellent (and somewhat challenging) exercise.
It is not difficult to see that the add,
remove and contains operations described
above will all run in time O(h), where h is the height of a binary
search tree. What is their running time as a function of N, the
number of nodes in the tree?
First consider a complete binary search tree. As
we saw in the last lecture, if the tree has N nodes then its height
is h = log2(N + 1) – 1 ≈ log2(N)
– 1 = O(log N). So add, remove, and
contains will all run in time O(log N).
Even if a tree is not complete, these operations will run in O(log N) time if the tree is not too tall given its number of nodes N, specfically if its height is O(log N). We call such a tree balanced.
Unfortunately not all binary trees are balanced. Suppose that we insert values into a binary search tree in ascending order:
t = TreeSet()
for i in range(1, 1000):
t.add(i)The tree will look like this:
This tree is completely unbalanced. It basically
looks like a linked list with an extra None
pointer at every node. add, remove and
contains will all run in O(N) on this tree.
How can we avoid an unbalanced tree such as this one? There are two possible ways. First, if we insert values into a binary search tree in a random order then that the tree will almost certainly be balanced. We will not prove this fact here (you might see a proof in the Algorithms and Data Structures class next semester).
Unfortunately it is not always practical to insert in a random order – for example, we may be reading a stream of values from a network and may need to insert each value as we receive it. So alternatively we can use a more advanced data structure known as a self-balancing binary tree, which automatically balances itself as values are inserted. Two examples of such structures are red‑black trees and AVL trees. We will not study these in this course, but you will see them in Algorithms and Data Structures next semester. For now, you should just be aware that they exist. In a self-balancing tree, the add(), remove() and contains() methods are all guaranteed to run in O(log N) time, for any possible sequence of tree operations.
Let's write a function that will print all values in a binary search tree in increasing order. It is easy using recursion:
def print_tree(n):
if n == None: # empty
return
print_tree(n.left)
print(n.val)
print_tree(n.right)We have already seen several abstract data types: stacks, queues, and sets. Another abstract data type is a map (or dictionary), which maps keys to values. It provides these operations:
A map cannot contain the same key twice. In other words, a map associates a key with exactly one value.
This type should be familiar, since we have used Python's dictionaries, which are an implementation of this abstract type.
We can use a binary search tree to implement a map. To do so, we only need to make a small change to the binary search tree code we saw above: now each node will store a key-value pair. The lookup() operation is similar to the set operation contains(): it will search the tree for a node with the given key; if found, it will return the corresponding value. The map operations set() and remove_key() will also be similar to the set operations add() and remove().
As an experiment, let's create a binary search tree containing a set of words, then draw the tree using Python's turtle graphics module.
We will read the words from the text of a famous poem by John Keats. Here is a file with the text. We'll consider a word to be any contiguous sequence of letters. To extract the words, we'll convert every character that is not a letter into a space, and then we'll call split(). Here is code to read the file and build the tree:
tree = TreeSet()
f = open('poem')
for line in f:
s = ''
for c in line:
s += c if c.isalpha() else ' '
for word in s.split():
tree.insert(word.lower())Let's examine the tree that we have built:
>>> size(tree.root) 231 >>> height(tree.root) 14 >>> print_tree(tree.root) a about above adieu age ah all altar … winning with woe ye yet young your youth
We saw in the previous lecture that a complete tree with height h contains 2h + 1 – 1 nodes. That means that the minimal possible height for a tree with 231 nodes is log2 256 – 1 = 7. So this tree's height (14) is about twice the minimum that would be possible.
Let's draw a picture of this tree using Python's turtle graphics. We would like to choose an (x, y) position for each node so that the line segments in the tree do not cross. For any node, the y position can be its depth; that way, all nodes at the same tree level will be displayed in a single horizontal row. We will set each node's x-position to be its value's index in the sorted sequence of values in the tree. For example, the smallest value in the tree will have x-position 0, the next-smallest value will have x-position 1 and so on.
We will choose a coordinate system such that the upper-left corner of the window is (0, 0), with x increasing to the right and y increasing downward. The lower-right corner of the window will be (x1, y1), where x1 is the total number of nodes in the tree and y1 is twice the tree height. That means that the tree will occupy the upper half of the window. (Notice that in this coordinate system, an x-unit and a y-unit do not represent the same physical distance.)
Here is code to draw the tree:
def line(x1, y1, x2, y2):
penup()
goto(x1, y1)
pendown()
width(2)
goto(x2, y2)
next_x = 0
# Given a pointer to a Node n, draw n and its children (recursively), and
# return an integer representing the x-index of n.
def draw(n, depth):
global next_x
if n.left != None:
left_x = draw(n.left, depth + 1)
my_x = next_x
next_x += 1
if n.right != None:
right_x = draw(n.right, depth + 1)
if n.left != None:
line(my_x, depth, left_x, depth + 1) # draw line to left child
if n.right != None:
line(my_x, depth, right_x, depth + 1) # draw line to right child
return my_x
delay(0)
setworldcoordinates(0, 2 * height(tree.root), size(tree.root), 0)
draw(tree.root, 0)
done()Here is the resulting image of the tree with the words from the Keats poem:
The tree certainly does not have a symmetrical shape. Nevertheless it is reasonably balanced: as we saw above, its height is only about twice the minimum possible.