Class Notes (1,100,000)
CA (620,000)
Queen's (10,000)
CISC (500)
Lecture 9

CISC 235 Lecture Notes - Lecture 9: Binary Search Tree, Search Algorithm, Binary Tree


Department
Computing
Course Code
CISC 235
Professor
Robin W Dawes
Lecture
9

Page:
of 8
CISC 235 Lecture 9
Binary Search Trees aka Lexically Ordered Binary Trees
When we store information in a binary tree there is no rule that
says the information must be stored according to a specific pattern
or rule. However, the most popular use of binary trees involves
enforcing a simple rule for the placement of the values in the tree:
small values go to the left and large values go to the right. We can
formalize this as follows:
Binary Search Tree: a binary search tree is a binary tree in which
each vertex contains an element of the data set. The vertices are
arranged to satisfy the following additional property: at each
vertex, the value stored is >= all values stored in the vertex's left
subtree, and < all values stored in the vertex's right subtree. Note
that we use ">=" for the left subtree to accommodate the
possibility of having duplicate values in the tree.
Binary Search Trees are wildly popular as data structures - we will
spend the next couple of weeks looking at their properties in some
detail.
Suppose we are creating an application that requires 3 operations
on the data set:
- search for a value
- insert a value
- delete a value
We already have data structures that support these operations: one-
dimensional arrays and lists. In order to make a case for using a
BST, we need to determine the complexity of algorithms for the
operations, and then argue that they are superior to the algorithms
for the same operations on an array or list.
BST_Search
Because of the ordering of the values in the vertices, searching a
BST works just like binary search on a sorted array. We start at
the root - if it contains the value we want, we are done. If not, we
go to the left or right child, as appropriate.
Our intended set-up of this (and all subsequent) data structures is
that the user - in this case, the program which is calling the search
function - should not need to know any details about the
implementation of the structure. For example, the user should not
need to know that the root of the tree is identified by an attribute
called "root". For this reason, the function header is just
BST_Search(T,x) where T is the tree to be searched and x is the
search value. Of course, if this function has been implemented as a
method belonging to the tree, the function call would probably
look like T.BST_search(x).
We need to decide which flavour of search we are going to
implement ("if x is there, return True?" versus "if x is there, return
its location") We will opt for the former, since it is neither easier
nor more difficult. If x is in T, we return True. If x is not in T, we
return False.
BST_Search(T,x):
current = T.root # in class I
used "v" instead of "current". "current" is probably
a better choice since it is a more informative name
while current != nil:
if current.value == x:
return True
elif current.value < x:
current = current.right_child
else:
current = current.left_child
return False # if we have reached this point, x
is not in the tree
We can also implement the search algorithm recursively. We use a
"wrapper" function so that the interface does not change:
BST_Search(T,x):
return rec_BST_Search(T.root,x)
rec_BST_Search(current,x):
if current == nil:
return False
elif current.value == x:
return True
elif current.value > x:
return rec_BST_Search(current.left_child,x)
else:
return rec_BST_Search(current.right_child,x)
You should convince yourself that these algorithms do indeed
achieve the same result. It is easy to see that they have the same
complexity since they visit exactly the same sequence of tree
vertices.
Which of the two is better? The recursive version is marginally
more elegant, but the iterative version is probably a bit more
efficient - this is because a function call, in real life, takes longer to
execute than an iteration of a loop. This means that even though
the two algorithms have the same complexity, the constant
multiplier for the iterative version may be smaller than the constant
multiplier for the recursive version.
At least, this is the conventional wisdom. As I discovered with my
recursive versus iterative implementations of quicksort, it seems
that (in Python at least) recursive implementations of some
algorithms may be faster than iterative implementations of the
same algorithm. I encourage you to conduct some further
experiments to explore this question for yourself.
Regardless of the difference in speed, I prefer the recursive