Transcript Review Session

Data Structures Review
Session 2
Ramakrishna, PhD student.
Grading Assistant for this course
CS 307 Fundamentals of
Computer Science
1
Binary Search Trees
A binary tree is a tree where each node has at most
two children, referred to as the left and right child
A binary search tree is a binary tree where every
node's left subtree holds values less than the
node's value, and every right subtree holds values
greater.
A new node is added as a leaf.
root
17
left child 11
CS 307 Fundamentals of
Computer Science
parent
19 right child
2
Problems
Problem 1:
How do you sort n numbers using a binary
Search tree ?? What are the best, worst and
Average case time complexities ??
CS 307 Fundamentals of
Computer Science
3
Binary Search Tree properties
 All dynamic-set operations (Search, Insert, Delete, Min,
Max, successor, predecessor) can be supported in O(h)
time.
 h = (lg n) for a balanced binary tree (and for an
average tree built by adding nodes in random order.)
 h = (n) for an unbalanced tree that resembles a linear
chain of n nodes in the worst case.
 Red-black trees are a variation of binary search trees to
ensure that the tree is balanced.
 Height is O (log n), where n is the number of
nodes.
CS 307 Fundamentals of
Computer Science
4
Balance of Binary Trees
 A binary tree can be balanced, such that one branch of the tree is about the
same size and depth as the other.
 In order to find out if a tree node is balanced, you need to find out the maximum
height level of both children in each node, and if they differ by more than one
level, it is considered unbalanced.
 If the number is -1, 0, or 1, the node is balanced. If the difference is anything
else, then it is unbalanced. Note that a balanced binary tree requires every node
in the tree to have the balanced property.
CS 307 Fundamentals of
Computer Science
5
Sorting Using BST
Inorder traversal of a binary search tree always gives a sorted
sequence of the values. This is a direct consequence of the BST
property.
Given a set of unordered elements, the following method can be
used to Sort the elements:
 construct a binary search tree whose keys are those
elements, and then
 perform an inorder traversal of this tree.
BSTSort(A)
1. for each element in an array do
2. Insert element in the BST// Constructing a BST take O( log n)
time
3. Inorder-Traversal (root)
// Takes O(n) time
Best case running time of BSTSort(A) is O( n log n).
Worst case running time is O(n2) since each inserting could
CS take
307 Fundamentals
of in worst case.
O(n) time
6
Computer Science
Example Sorting Using BST
Input Sequence :- 2 3 8 4 5 7 6 1 2.5 2.4
Step 1 : Creating Binary Search Tree of above given input
sequence.
2
3
1
8
2.5
2.4
4
5
7
CS 307 Fundamentals of
Computer Science
6
7
Example Sorting Using BST (cont.)
Input Sequence :- 2 3 8 4 5
Step 2 : Perform Inorder-Traversal.
2
7
6
1
2.5
2.4
1
2
3
1
8
2.5
2.4
4
5
7
CS 307 Fundamentals of
Computer Science
6
8
Example Sorting Using BST (cont.)
Input Sequence :- 2 3 8 4 5 7 6 1 2.5
Step 2 : Perform Inorder-Traversal.
2
2.4
1
2
3
1
2.4
2.5
3
8
2.5
2.4
4
5
7
CS 307 Fundamentals of
Computer Science
6
9
Example Sorting Using BST (cont.)
Input Sequence :- 2 3 8 4 5
Step 2 : Perform Inorder-Traversal.
2
7
6
1
2.5
2.4
1
2
3
1
2.4
2.5
3
8
2.5
4
5
2.4
6
4
7
8
5
Sorted Array
7
CS 307 Fundamentals of
Computer Science
6
10
Worst cases
Input Sequence :- 8 4 3 2 and 2 3 8 10
Step 1 : Creating Binary Search Tree of above given input
sequence.
8
4
3
2
CS 307 Fundamentals of
Computer Science
2
3
8
10
11
Finding Min & Max
The binary-search-tree property guarantees that:
» The minimum is located at the left-most node.
» The maximum is located at the right-most node.
Tree-Minimum(x)
1. while left[x]  NIL
2. do x  left[x]
3. return x
Tree-Maximum(x)
1. while right[x]  NIL
2.
do x  right[x]
3. return x
Q: How long do they take?
CS 307 Fundamentals of
Computer Science
12
Algorithm LCA (Node v, Node w):
int vdpth  v.depth
int wdpth  w.depth
while vdpth > wdpth do
v  v.parent
vdpth  vdpth -1
end while
while wdpth > vdpth do
w  w.parent
wdpth  wdpth -1
end while
Note that LCA
algorithm is
applicable for
any tree
while v ≠ w do
v  v.parent
w  w.parent
end while
return v
CS 307 Fundamentals of
Computer Science
13
1. Give an efficient algorithm for converting an
infix arithmetic expression into its
equivalent postfix notation ?
(Hint: First convert the infix expression into its
equivalent binary tree representation)
CS 307 Fundamentals of
Computer Science
14
CS 307 Fundamentals of
Computer Science
15
Algorithm buildExpressionTree (E):
Input: Fully-parenthesized arithmetic Expression
Output: A binary Tree T representing Expression
S a new empty stack
For i 0 to n-1 do {
if E[i] is a variable or an operator then
T  new binary tree with E[i] as root
S.push(T)
else if E[i] = “(“ then continue;
else if E[i] = “)”
T2  S.pop()
T  S.pop()
T1  S.pop()
Attach T1 as T’s left subtree and T2 as its right subtree
S.push(T)
}
Return S.pop()
CS 307 Fundamentals of
Computer Science
16
Algorithm PostFix (E):
Input: Full-Parenthesized arithmetic Expression ,E.
Output: PostFix notation of E
T  buildExpressionTree (E)
Postorder-Traversal (T.root) // this gives the
Postfix notation of the expression
Preorder-Traversal (T.root) // this gives the
Prefix notation of the expression
Inorder-Traversal (T.root) // this gives the
Infix notation of the expression
CS 307 Fundamentals of
Computer Science
17
Representing Graphs
Assume V = {1, 2, …, n}
An adjacency matrix represents the graph as
a n x n matrix A:
– A[i, j] = 1 if edge (i, j)  E (or weight of edge)
= 0 if edge (i, j)  E
CS 307 Fundamentals of
Computer Science
18
Graphs: Adjacency Matrix
Example:
1
a
d
2
b
4
c
3
A
1
2
3
4
1
0
1
1
0
2
0
0
1
0
3
0
0
0
0
4
0
0
1
0
How much storage does the adjacency matrix
require?
A: O(V2)
CS 307 Fundamentals of
Computer Science
19
Graphs: Adjacency List
Adjacency list: for each vertex v  V, store a
list of vertices adjacent to v
Example:
– Adj[1] = {2,3}
– Adj[2] = {3}
– Adj[3] = {}
– Adj[4] = {3}
1
2
4
Variation: can also keep
a list of edges coming into vertex 3
Adjacency lists take O(V+E) storage
CS 307 Fundamentals of
Computer Science
20
Graph Problems
Given an adjacency-list representation of a
directed graph, how long does it take to
compute the out-degree and in-degree of
every vertex ? Also, how long is it going to
take if we use the adjacency matrix instead ?
CS 307 Fundamentals of
Computer Science
21
Solution
Given the adjacency-Matrix representation of a
graph the out and in-degree of every node can
easily be computed as follows.
For I  1 to v // v vertices
For J  1 to v // v vertices
if(A[I][J] == 1) then
outdegree[I]++;
indegree[J]++;
Time complexity : O(V2)
CS 307 Fundamentals of
Computer Science
22
Solution
Given the adjacency-List representation of a graph
the out and in-degree of every node can easily be
computed as follows.
For I  1 to v // n vertices
For J  1 to A[I].size() // neighbours of vertex I
n  A[i].get(J)
outdegree[I]++;
indegree[n]++;
Time complexity : O(V+E)
CS 307 Fundamentals of
Computer Science
23
Problem
The transpose of a directed graph G = (V,E)
is the graph G with all its edges reversed.
Describe efficient algorithms for computing
the transpose of G for both adjacency list
and matrix representations. What are the
running times ?
CS 307 Fundamentals of
Computer Science
24
Solution
Given the adjacency-Matrix representation of
a graph the transpose can be computed as
follows.
For I  1 to v // v vertices
For J  1 to v // v vertices
Transpose[I][J] = A[J][I]
Time complexity : O(V2)
CS 307 Fundamentals of
Computer Science
25
Solution
Given the adjacency-List representation of a
graph the transpose can be computed as
follows.
For I  1 to n // n vertices
For J  1 to A[I].size() // neighbours of vertex I
Transpose[I].add(A[J].get(I))
Time complexity : O(V+E)
CS 307 Fundamentals of
Computer Science
26
Predecessor and Successor in a
BST
Successor of node x is the node y such that key[y]
is the smallest key greater than key[x].
The successor of the largest key is NIL.
Search consists of two cases.
– If node x has a non-empty right subtree, then x’s
successor is the minimum in the right subtree of x.
– If node x has an empty right subtree, then:
• As long as we move to the left up the tree (move up through right
children), we are visiting smaller keys.
• x’s successor y is the node that x is the predecessor of (x is the
maximum in y’s left subtree).
• In other words, x’s successor y, is the lowest ancestor of x whose
left child is also an ancestor of x.
CS 307 Fundamentals of
Computer Science
27
Pseudo-code for Successor
Tree-Successor(x)
 if right[x]  NIL
2.
then return Tree-Minimum(right[x])
3. y  p[x]
4. while y  NIL and x = right[y]
5. do x  y
6.
y  p[y]
7. return y
56
26
28
18
12
200
190
213
24 27
Code for predecessor is symmetric.
Running time: O(h)
CS 307 Fundamentals of
Computer Science
28
Properties of Binary Trees
Note that external nodes are also called leaf nodes
Let
# leaf nodes = E, # internal nodes = I , Height = H, # nodes = N,
1) E = I + 1
2) N = E + I
3) (# nodes at level x) <= 2x
4) E <= 2H
5) H >= log2 I
6) A full binary tree has (2H+1 – 1) nodes.
7) (H+1) ≤ E ≤ 2H.
8) H≤ I ≤ 2H -1.
9) 2H+1 ≤ N ≤ 2H -1.
10) log2(N+1)-1 ≤ H ≤ (N-1)/2
11) log2(E) ≤ H ≤ E-1
12) log2(I+1) ≤ H ≤ I
CS 307 Fundamentals of
Computer Science
29