Class Notes (1,100,000)

CA (620,000)

Queen's (10,000)

CISC (500)

CISC 235 (20)

Robin W Dawes (20)

Lecture 9

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

**Unlock Document**

###### Document Summary

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. 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

## More from OC330671

###### CISC 235 Lecture Notes - Lecture 1: Autocomplete

Lecture Note

###### CISC 235 Lecture Notes - Lecture 12: Self-Balancing Binary Search Tree, Binary Tree, Null Pointer

Lecture Note

###### CISC 235 Lecture Notes - Lecture 4: Reverse Polish Notation, Infix Notation, Operand

Lecture Note

## Classmates also unlocked

###### CISC 235 Lecture Notes - Lecture 1: Autocomplete

Lecture Note

###### CISC 235 Lecture Notes - Lecture 12: Self-Balancing Binary Search Tree, Binary Tree, Null Pointer

Lecture Note

###### CISC 235 Lecture Notes - Lecture 4: Reverse Polish Notation, Infix Notation, Operand

Lecture Note

###### CISC 235 Lecture Notes - Lecture 13: Quadratic Probing, Linear Probing, Hash Table

Lecture Note

###### CISC 235 Lecture Notes - Lecture 14: Donald Knuth, American Broadcasting Company

Lecture Note

###### CISC 235 Lecture Notes - Lecture 20: Minimum Spanning Tree, Binary Heap, Prims

Lecture Note

###### CISC 235 Lecture Notes - Lecture 2: Random-Access Machine, Complex Instruction Set Computing, Time Complexity

Lecture Note

###### CISC 235 Lecture Notes - Lecture 19: Directed Acyclic Graph, Topological Sorting, Critical Path Method

Lecture Note

###### CISC 235 Lecture Notes - Lecture 2: Random-Access Machine, Virtual Memory, Memory Address

Lecture Note

###### CISC 235 Lecture Notes - Lecture 8: Reverse Polish Notation, Polish Notation, Binary Tree

Lecture Note

###### CISC 235 Lecture Notes - Lecture 21: Bit Array, The Algorithm, Bloom Filter

Lecture Note

###### CISC 235 Lecture Notes - Lecture 3: Sorting Algorithm, Merge Sort, Bubble Sort

Lecture Note

###### CISC 235 Lecture 12: CISC_235_29-March-2016

Lecture Note

###### CISC235 Lecture 1: Week 1

Lecture Note

###### CISC 235 Lecture Notes - Lecture 11: Binary Search Tree, Longest Path Problem, Complex Instruction Set Computing

Lecture Note