INN701 Lecture 3
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 5 – Binary tree, binary search tree
and algorithms
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R 2
Aims of this lecture
• This lecture introduces tree data structures and algorithms
– Binary tree and algorithms
– Binary search tree and algorithms
CRICOS No. 00213J
a university for the worldreal R
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Addison-Wesley, third edition, 2012. Sections 1.4, 5.3
• Thomas H. Cormen etc. Introduction to Algorithms. MIT Press,
Third Edition, 2009. Chapter 12.
3
CRICOS No. 00213J
a university for the worldreal R
Binary tree
A binary tree is a non-linear data structure in which each node
has at most two children.
4
CRICOS No. 00213J
a university for the worldreal R
Binary tree
A binary tree is a set T of nodes
such that either
– T is empty, or
– T is partitioned into three
disjoint subsets:
• A single node root, the root
• Two possibly empty sets
that are binary trees, called
left and right subtrees of
root.
5
CRICOS No. 00213J
a university for the worldreal R
item lchild rchild
Binary tree implementation
lchild: left child pointer
rchild: right child pointer
The structure of a binary tree node (BTNode):
6
CRICOS No. 00213J
a university for the worldreal R
Binary tree implementation
^ null
A
D ^ ^
C ^
G ^
B
E ^ ^
H ^ ^
F ^
root
7
CRICOS No. 00213J
a university for the worldreal R
Traversal of a binary tree
• Often one wishes to visit each of the nodes in a binary tree and
examine the value there.
• There are three common orders in which the nodes can be
visited, and each has useful properties that are exploited in
algorithms based on binary trees.
– Pre-order
– In-order
– Post-order
8
CRICOS No. 00213J
a university for the worldreal R
Pre-order traversal
• Pre-order traversal is recursively
defined as follows:
– visit the root first, then
– traverse the left subtree in
pre-order, and then
– traverse the right subtree in
pre-order.
A B D E C F G H
9
CRICOS No. 00213J
a university for the worldreal R
Pre-order traversal algorithm
ALGORITHM Pre-order (root)
if root ≠ null
visit root.item
Pre-order(root.lchild)
Pre-order(root.rchild)
10
CRICOS No. 00213J
a university for the worldreal R
In-order traversal
• In-order traversal is recursively
defined as follows:
– traverse the left subtree in in-
order, then
– visit the root, and then
– traverse the right subtree in
in-order.
D B E A C G H F
11
CRICOS No. 00213J
a university for the worldreal R
In-order traversal algorithm
ALGORITHM In-order (root)
if root ≠ null
In-order(root.lchild)
visit root.item
In-order(root.rchild)
12
CRICOS No. 00213J
a university for the worldreal R
Post-order traversal
• Post-order traversal is
recursively defined as follows:
– traverse the left subtree
in post-order, and then
– traverse the right subtree
in post-order, and then
– visit the root.
D E B H G F C A
13
CRICOS No. 00213J
a university for the worldreal R
Post-order traversal algorithm
ALGORITHM Post-order (root)
if root ≠ null
Post-order(root.lchild)
Post-order(root.rchild)
visit root.item
14
CRICOS No. 00213J
a university for the worldreal R
Efficiency of the binary tree traversal
algorithms
• Pre-order: O(n), where n is the number of nodes in the binary tree
• In-order: O(n), where n is the number of nodes in the binary tree
• Post-order: O(n), where n is the number of nodes in the binary tree
15
CRICOS No. 00213J
a university for the worldreal R
Binary search tree
A binary search tree is a binary tree, where every node’s left subtree
contains values that are less than or equal to the node’s value,
every node’s right subtree contains values that are greater than or
equal to the node’s value, and both left and right binary trees and
binary search trees.
binary search tree
60
50 70
30 65
80
75
55
60
50 70
30 65
75
80
55
not a binary search tree
16
CRICOS No. 00213J
a university for the worldreal R
Search
Searching a binary search tree for a specific item is a recursive
process due to the property of binary search trees.
We begin by examining the root.
– If the given item equals to the item at the root, return true;
– If it is less than the item at the root, we recursively search
the left subtree in the same manner.
– Similarly, if it is greater than the item at the root, we
recursively search the right subtree in the same manner.
17
CRICOS No. 00213J
a university for the worldreal R
Search
60
50 70
30 65
80
75
55
Search for 80
18
CRICOS No. 00213J
a university for the worldreal R
Search
60
50 70
30 65
80
75
55
Search for 79
19
CRICOS No. 00213J
a university for the worldreal R
Search algorithm
ALGORITHM Search (K, root)
if root ≠ null
if root.item = K
return true
else
if root.item < K
return Search(K, root.rchild)
else
return Search(K, root.lchild)
else
return false
20
CRICOS No. 00213J
a university for the worldreal R
Insert
60
50 70
30 65
80
75
55
Insert 45
45
21
CRICOS No. 00213J
a university for the worldreal R
Insert algorithm
ALGORITHM Insert (K, root)
if root = null
ptr ← new BTNode; ptr.item ← K; root ← ptr
else
if root.item > K
if root.lchild = null
ptr ← new BTNode; ptr.item ← K; root.lchild ← ptr
else Insert(K, root.lchild)
else
if root.rchild = null
ptr ← new BTNode; ptr.item ← K; root.rchild ← ptr
else Insert(K, root.rchild)
22
CRICOS No. 00213J
a university for the worldreal R
Delete
There are three cases that need to be considered:
– the node to be deleted is a leaf
– the node to be deleted has only one child
– the node to be deleted has two children
23
CRICOS No. 00213J
a university for the worldreal R
Delete
parent
ptr
parent
Case 1: the node to be deleted is a leaf
24
parent
ptr
parent
CRICOS No. 00213J
a university for the worldreal R
Delete
Case 2: the node to be deleted has only one child
25
parent
ptr
parent
c
c
CRICOS No. 00213J
a university for the worldreal R
Delete
ptr
The right-most
node in the left
subtree of ptr
Case 3: the node to be deleted has two children
Transform it into the problem of deleting a
node that has only one child or deleting a leaf:
1. find the right-most node in the left subtree of ptr;
2. copy the item of the right-most node to ptr
3. delete the right-most node
26
CRICOS No. 00213J
a university for the worldreal R
Delete algorithm
ALGORITHM Delete(K, root)
// delete a node whose key is K from a binary search tree
// root is the pointer of the binary search tree
// search for node where K is stored and its parent
ptr ← root
parent ← null // parent of ptr
while ptr ≠ null and ptr.item ≠ K do
parent ← ptr
if ptr.item > K // move to the left subtree of ptr
ptr ← ptr.lchild
else //move to the right subtree of ptr
ptr ← ptr.rchild
27
CRICOS No. 00213J
a university for the worldreal R
if ptr ≠ null // if the search was successful
if ptr.lchild ≠ null and ptr.rchild ≠ null //ptr has two children
// find the right-most node in left subtree of ptr
if ptr.lchild.rchild = null // a special case: the right subtree
// of ptr.lchild is empty
ptr.item ← ptr.lchild.item
ptr.lchild ← ptr.lchild.lchild
else
p ← ptr.lchild
pp ← ptr //parent of p
while p.rchild ≠ null do
pp ← p; p ← p.rchild
ptr.item ← p.item // copy the item at p to ptr
pp.rchild ← p.lchild
28
CRICOS No. 00213J
a university for the worldreal R
else // cases 1 & 2: item has no or only one child
if ptr.lchild ≠ null
c ← ptr.lchild
else
c ← ptr.rchild
// remove node ptr
if ptr = root //need to change root
root ← c
else
if ptr = parent.lchild
parent.lchild ← c
else
parent.rchild ← c
29
CRICOS No. 00213J
a university for the worldreal R
Demo – a binary search tree ADT in C#
• There are three files used in this demo:
– IBSTree.cs – The interface of the binary search tree ADT
– BSTree.cs – The implementation of the binary search tree ADT
– TestBSTreeADT.cs – A program that tests the operations
defined and implemented in the binary search tree ADT. It can
be considered as an application of the binary search tree ADT.
30
CRICOS No. 00213J
a university for the worldreal R
Demo – a binary search tree ADT in C#
31
CAB301 Algorithms and Complexity��Lecture 5 – Binary tree, binary search tree and algorithms
Aims of this lecture
References
Binary tree
Binary tree
Binary tree implementation
Binary tree implementation
Traversal of a binary tree
Pre-order traversal
Pre-order traversal algorithm
In-order traversal
In-order traversal algorithm
Post-order traversal
Post-order traversal algorithm
Efficiency of the binary tree traversal algorithms
Binary search tree
Search
Search
Search
Search algorithm
Insert
Insert algorithm
Delete
Delete
Delete
Delete
Delete algorithm
Slide Number 28
Slide Number 29
Demo – a binary search tree ADT in C#
Demo – a binary search tree ADT in C#