A short review: BFS, DFS, {Preorder, Inorder, Postorder} traversal
Using the same example in the lecture:
e4 v4 [BFS] Idea: Start with any vertex,
v0 mark it as visited. Visit all its
e0 e3 v3 neighbors, then for each visited
e5 e2 vertex, repeat the same procedure
v1 until all vertices are visited
e1 v2
Ex1. BFS (start with v1)
Ans: v1, v0, v2, v4, v3
Q: If there are
Q: Is this “v1, v2, v0, v3, v4” also correct?
more than one
Q: Is this “v1, v0, v2, v4, v3” also correct? possible sequences,
Q: Is this “v1, v2, v0, v4, v3” also correct? which sequences
Q: Is this “v1, v2, v3, v0, v4” also correct? will be output?
Ans: Depends on how you implement it (e.g. using queue, and how
you label the vertices to “visit” them in sequence)!
2
e4 v4 [DFS] Idea: Start with any vertex v,
v0 mark this node as visited, then for
e3 v3 each unvisited neighbor of v is
e0 searched in turn, using the same
e5 e2
v1 procedure recursively.
e1 v2
Recursive in nature
Ex2. DFS (start with v3)
Ans: v3, v0, v1, v2, v4
Q: If there are
Q: Is this “v3, v2, v1, v0, v4” also correct?
more than one
Q: Is this “v3, v0, v4, v1, v2” also correct? possible sequences,
Q: Is this “v3, v2, v1, v4, v0” also correct? which sequences
Q: Is this “v3, v0, v2, v1, v4” also correct? will be output?
You should know how to answer this question,
lecture gives you a hints on stack implementation,
right?
3
Using the same example in the lecture too:
Ex3. BFS starts with r
r Ans: r f a e g b d c
Is this “r e f a g b d c” correct too?
f e
a
g Ex4. DFS starts with r
b d
c Ans: r f g a b c d e
Is this “r e a d b c f g” correct too?
[Preorder traversal]: Staring from root, visit the node, then repeat
the same procedure in each of its subtrees one by one
following the order of the subtrees
Preorder: Ex5. Postorder traversal
rfgabcde Ans: g f c b d a e r
4
r Remark: for inorder traversal, original
definition only applies to binary tree
f e
g a Ex6. Inorder traversal
b d
c Ans: g f a r c b e d
Q: In lecture, we extend it to non-binary tree too, do you
remember?
r
Remark: Some extend the
Q: do you know the
inorder traversal for general
degree. f e inorder traversal
a
Inorder(T1); g for this tree using
visit(root(T)); b d the extended
for i = 2 to k do c definition?
Inorder(Ti);
5
We learned quite a lot in data structures already:
- Set, List, Stack, Queue, Graph, Tree, Hashing
These are more or less basic, now we
proceed to learn more advanced ones
6
Searching and Binary Search Tree (Outcome (2))
Review: let’s revisit the searching problem.
Problem: Given a set of n elements and an element x, return the
location of the element x or report that such an element does
not exist in the set.
Do you
Sequential (Linear) Search
remember/learn all
Binary Search
these
Hashing
Sequential (Linear) Search Successful or unsuccessful search
Unsorted/ sorted Worst case: O(n)
array implementation Average case: O(n)
for i = 0 to n-1 { //elements stored in array A[0..n-1]
if A[i] = x
return i;}
return -1; // -1: not found
How about linked-list?
7
Binary Search
Searching in a sorted array (return i if A[i]=x or –1 otherwise):
6 30 55 70 90 95 100 120 x = 100
Binary search:
Observation: if (A[i] > x), x ¹ A[j] with j>i
if (A[i] < x), x ¹ A[j] with j<i
So, check the “middle” element and eliminate
half of elements if x is not found yet
6 30 55 70 90 95 100 120
90 95 100 120
100 120
if x = 105 120
8
int Search(A, x) { // binary search, A[0..n-1]
int lo=0, hi=n-1, mid
while (lo £ hi) do
mid = ë(lo+hi)/2û
if (x < A[mid])
hi=mid-1
else if (x > A[mid])
lo=mid+1
else return mid
return –1
}
(1) What is the worst case time complexity?
(2) Can you rewrite it as a recursive algorithm?
(1) The while loop will be executed O(log n) times
[why?], so the time complexity of the algorithm is
O(log n).
9
For binary search
- assuming that the elements are sorted according to their keys
Successful or unsuccessful search
Worst case: O(log n)
Sorted array implementation
Average case: O(log n) [proof?]
Sorted linked-list implementation?
Cannot implement binary search
Hashing
For ave. case complexity Unsuccessful Successful
Chaining O(1+a) O(1+a)
Open Addressing O(1/(1-a))* O(1/ a ln (1/(1- a)))*
Worst case complexity: O(n) where n is the no. of keys in
dictionary
Summary: Best worst-case algorithm – binary search
But insertion/deletion takes O(n) time, can we do better?
* Analysis not required in the exam. 10
Binary Search Tree
Given a set of elements, a binary search tree can support the
following operations:
Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete
Binary search tree can be used as a dictionary!
What is a binary search tree?
A binary search tree is a binary tree with keys stored in the nodes
which satisfy the following property (binary-search-tree-property).
If y and z are nodes in left subtree and right subtree, respectively,
of node x, then key(x) > key(y) and key(x) < key(z)
We assume that
parent (p)
each node has 3
8
pointers and a key
key
stored in it.
5 60 And a pointer to the
root is given. left child right child
3
45 70 (left) (right)
4 If x denotes the pointer to the node,
x.p (parent), [Link] (left child), [Link] (right child)
11
From this example, can you guess which
8
node has the minimum key? Which one has
5 the maximum key?
60
Minimum: the leftmost node
3 Maximum: the rightmost node
45 70
4 Tree-Maximum(x) {
while ([Link] ¹ null)
Tree-Minimum(x) { x = [Link];
return x; 50
while ([Link] ¹ null)
x = [Link]; }
O(h)
return x; 40
} O(h) where h is the height of the tree
This can be O(n) where n is the number of nodes 30
A worst case example 20
for Tree-minimum(x)
.............. 10
12
On the other hand, if the tree is roughly a complete binary tree,
then h = O(log n)
You will see examples of such balanced search tree
Do you know how to perform search? 8 8 < 50
Given k = 50
5 60 60 > 50
Tree-Search(x, k) {
if (x = Null) or (k = key(x)) 3
45 70
return x
else 4
45 < 50
if (k < key(x))
Tree-Search([Link], k);
else
Tree-Search([Link], k);
} Do you know how to write
O(h) this without using
recursion?
14
How about Predecessor and Successor?
8
Successor(x): return the node whose key is
5 just larger than that of x or Null if key(x) is
60 the largest key
3 Predecessor(x): return the node whose key is
45 70 just smaller than that of x or Null if key(x) is
4 the smallest key
Successor
Where are the nodes whose
key is larger than yours? If right
e.g. The node with key = 8 subtree
The node with key = 5 does not
The node with key = 4 exist
Among these nodes, which smallest
one is the smallest? in this
subtree
15
Tree-Successor(x) {
if ([Link] ¹ null)
return Tree-Minimum([Link]);
y = x.p // parent of x
How about Predecessor? Can
while (y ¹ null) and (x = [Link]) { you write a similar
x = y; procedure for Predecessor?
y = y.p;
}
return y;
} O(h)
Tree-Predecessor(x) {
if ([Link] ¹ null)
return Tree-Maximum([Link]);
y = x.p // parent of x
while (y ¹ null) and (x = [Link]) {
x = y;
y = y.p;
}
return y;
}
16
Insertion: insert a new element in the
8 < 11 tree such that the binary-search-
8
tree property is still maintained
60 > 11
5 60 e.g. Insert(11) ~ unsuccessful search
3 45>11 Tree-Insert(T, x){ // x.p=[Link]=[Link] = null
45 70 y = T; // Assume T points to the root
z = null;
4 Find where to insert
while (y ¹ null) {
11 z = y;
if ([Link] < [Link]) // insert to lefttree
y = [Link];
Do not handle else
the case for y = [Link]; // insert to righttree
null tree } Actual insertion
if (z = null) x.p = z;
T = x; if ([Link] < [Link]) // insert as left child
else [Link] = x;
if ([Link]....) else // insert as right child
[Link] = x;
}
O(h) 17
Deletion: delete an element from T while
maintaining the binary-search-tree property.
Yes, we can always reorganize all
8 elements. But can we do better?
5 60 e.g. Delete(45); Delete(4); Delete(80)
3 Easy! Just remove the node as long as
45 70
it’s a leaf
4
Remark: Do not handle
80 tree with only one node!
Case 1 (The node to be deleted is a leaf):
Delete(T, z) { // z points to a leaf to be deleted
if ([Link] = z) [Link] = null;
else [Link] = null;
delete z; // delete the node and reclaim space
}
18
Deletion: delete an element from T while maintaining
the binary-search-tree property. e.g. Delete(5); Delete(3); Delete(70)
Link up the parent and your only child!
8
8 8
5 60 3
60 5 60
3
45 70 4
4 45 70 45 70
4
After Delete(5)
80 After Delete(3)
80 80
Case 2 (The node to be deleted has only one child):
Delete(T, z) { // z points to a node to be deleted Delete(8) 8
if ([Link] = null) x = [Link];
else x = [Link]; Special case: 5
if ([Link] = z) [Link] = x; Delete the root
else [Link] = x; 3
x.p = z.p;
delete z; // delete the node and reclaim space} 4
19
8 e.g. Delete(8); Delete(60)
Delete(8): it’s easy if we can find someone
5 60 to replace 8. But it has to be greater than
3 all nodes in the left subtree and smaller
45 70 than all nodes in the right subtree!
4
Successor 45
of 8 80
How about 60? 5 60
Similarly, the successor of 60 is 70
So, copy 70 to 60 and delete 70. 3
70
70 has only one child, so it is easy
(Case 2). 4
8
Effectively, you 80
5 70 replace the
content of 8 by
3
45 80 45 and delete the
node with 45
4
(Case 1) 20
Ok, will the successor has two children instead of just one?
No, according to the following [MIT Book 12.2-5, p.293]:
If a node in a binary search tree has two children, its
successor has no left child.
8
Rough idea:
5 60 Delete 8 => successor of 8
(i) 8 has two children, thus right
3 subtree exists;
45 70
(ii) Where is the successor?
4 Leftmost node of right subtree
80
x y
If 45 has two children, then will 45 be the
successor of 8? Which will be the successor of 8?
21
Ok, will the successor has two children instead of just one?
No, according to the following [MIT Book 12.2-5, p.293]:
If a node in a binary search tree has two children, its
successor has no left child.
Idea of proof:
Let u be the node (to be deleted) that has two children and
let v be the successor of u.
The node v must be in the right subtree of u.
If v has a left child w,
then w is smaller than v, but larger than u.
It contradicts that v is the successor of u.
So, let’s summary what we have to do for this case:
Let u be the node to be deleted. Find Successor(u) and let it
be v.
Replace content of u by v.
Delete v:
If v has no child, Case (1)
If v has one child, Case (2)
22
Case 3 (The node to be deleted has two children):
Delete(T, z) { // z points to a node to be deleted
x = Tree-Successor(z);
[Link] = [Link];
if x has no child
delete x as in Case 1;
else
delete x as in Case 2;
} O(h)
In the MIT book, the three cases are combined
and handled in one algorithm.
Summary
All the operations Minimum, Maximum, Successor,
Predecessor, Search, Insert, Delete run in O(h) time where
h is the height of the tree.
23
What will be h? (worst case, average case, best case)
Reminder: Worst case Best case Average case
70 50 The expected height of
a randomly built binary
h=n search tree on n keys is
60 30 70 O(log n)
50 20 40 60 80
The tree results
from inserting n
40 keys in random
h = log n order where each
of the n!
30 Note: if we allow delete and permutations of
insert keys randomly, the keys is equally
analysis is difficult and the likely
O(log n) result may not hold
24