Binary Search Trees

Data Structures and Algorithms

Andrei Bulatov
 Algorithms – Binary Search Trees 12-2

Priority Queues and Search Trees

A priority queue is a data structure that allows to store a set of entries,
each with a key, and to perform operations such as Insert, Delete,
Extract Maximum, Increase Key (for max-priority queues)
Heaps is an example of an implementation of a priority queue.

Sometimes we need more. A search tree is data structure that allows

for Search, Insert, Delete, Minimum, Maximum, Predecessor,
Successor operations.
 Algorithms – Binary Search Trees 12-3

Binary Search Tree

A binary search tree is a binary rooted tree, in which keys satisfy the
Binary Search Tree property:
Let be a node in a binary search tree. If y is a node in the left
subtree of , then [ ] [ ].
If is a node in the right subtree of , then [ ] [ ]

5 5

3 7 7

2 5 8 6 8

5
 Algorithms – Binary Search Trees 12-4

Inorder Tree Walk

Having a binary search tree one can print its content in sorted order

Inorder-Tree-Walk( )
if ≠ Nil then do
Inorder-Tree-Walk(left[ ])
print key[ ]
Inorder-Tree-Walk(right[ ])

To print the entire tree just call Inorder-Tree-Walk(root[ ])

It is called inorder because the root is printed between the subtrees

A tree walk can also be preorder and postorder
 Algorithms – Binary Search Trees 12-5

Inorder Tree Walk (cntd)

Lemma
If is the root of an -node subtree, then the call
Inorder-Tree-Walk( ) takes Θ( ) time

Proof
Let ( ) denote the running time
If = Nil then (0) = , a constant
If > 0 then ( ) = ( ) + ( – – 1) + where is the
number of nodes in the left subtree
We prove that ( ) = ( + ) +
For = 0 we have ( + ) 0 + = = (0)
 Algorithms – Binary Search Trees 12-6

Inorder Tree Walk (cntd)

Proof
For > 0 we have
( )= ( )+ ( – – 1) +
= (( + ) + ) + (( + )( – – 1) + ) +
=( + ) + –( + ) + +
=( + ) +
QED
 Algorithms – Binary Search Trees 12-7

Searching
Elements of a binary search tree can be found efficiently

Tree-Search( , )
if = Nil or = [ ] then
return
if < [ ] then
return Tree-Search(left[ ], )
else
return Tree-Search(right[ ], )
 Algorithms – Binary Search Trees 12-8

Minimum and Maximum

We can find minimum and maximum keys in the tree

Tree-Minimum( )
while left ≠ Nil do
set : =left[ ]
endwhile
return

Tree-Maximum( )
while right ≠ Nil do
set : =right[ ]
endwhile
return
 Algorithms – Binary Search Trees 12-9

Successor
We can find the successor of a key in the tree

Tree-Successor( )
if right ≠ Nil then
return Tree-Minimum(right[ ])
endif
set ≔parent[ ]
while ≠ Nil and =right[ ] do
set : =
set : =parent[ ]
endwhile
return
 Algorithms – Binary Search Trees 12-10

Running Time

Theorem
The operations Search, Minimum, Maximum, Successor, and
Predecessor can be made to run in (ℎ) time on a binary search
tree of height ℎ.
 Algorithms – Binary Search Trees 12-11

Insertion
We insert a new value into a binary search tree .
The procedure is passed a node for which [ ]= ,
left[ ] = Nil, and right[ ] = Nil.
Tree-Insert( , )
set : =Nil, : =root[ ]
while ≠ Nil do
set : =
if [ ]< [ ] then set : =left[ ]
else set : =right[ ]
endwhile
set parent[ ]: =
if = Nil then set root[ ]: =
else if [ ]< [ ] then set left[ ]: =
else set right[ ]: =
 Algorithms – Binary Search Trees 12-12

Deletion
We delete a given node
Consider 3 cases:
(i) has no children

(ii) has one child

(iii) has 2 children

 Algorithms – Binary Search Trees 12-13

Deletion (cntd)
(i) has no children
6 6

1 7 1 7

0 4 9 0 4 9

2 5 8 10
2 8 10

3 3
 Algorithms – Binary Search Trees 12-14

Deletion (cntd)
(ii) has one child
6 6

1 7 1
9
0 4 9 0 4 8 10
2 5 8 10
2 5

3 3
 Algorithms – Binary Search Trees 12-15

Deletion (cntd)
(iii) has two children
6 2 6

1 7 1
9
0 4 9 0 4 8 10
2 5 8 10 3 5

3
6

2
9
0 4 8 10

3 5
 Algorithms – Binary Search Trees 12-16

Deletion
Tree-Delete( , )
if left[ ] =Nil or right[ ] =Nil then set : =
else set : =Tree-Successor( )
if left ≠ Nil then set : =left[ ]
else set : =right[ ]
if ≠ Nil then set parent[ ]: =parent[ ]
else set : =right[ ]
if parent = Nil then set root[ ]: =
else if =left[parent[ ]]: = then left[parent[ ]: =
else right[parent[ ]]: =
if ≠ then do
set key[ ]: =key[ ]
copy ’s data into
return
 Algorithms – Binary Search Trees 12-17

Binary Rooted Trees

If we need to run heap sort on a sequence of numbers of unpredictable
length, we cannot organize heap in an array
A binary tree is used
parent
root
NIL left right

parent parent

left right left right

parent parent parent NIL

left right left right left right
 Algorithms – Binary Search Trees 12-18

Arbitrary Rooted Trees

Sometimes a non-binary tree is needed

parent
root
NIL chil sibl

NIL

parent parent parent

chil sibl chil sibl chil sibl

parent parent parent

chil sibl chil sibl chil sibl
NIL

NIL NIL NIL