Algorithms: Sequential, Parallel and Distributed 4-13
endif
end PostOrder2
The above pseudocode is spaghetti indeed! After pondering its action awhile
(or by pondering the action of a postorder traversal directly), the following
Push(Stack, Root,1)
Root ← Root→LeftChild
endwhile
if Root→RightChild ≠ null .and.
RetFlag ≠ 2 then
Visit(Root→Info)
Pop(Stack, Root, RetFlag)
endwhile
endif
endif
4.28
procedure InsertBinSrchTreeRec(Root, x) recursive
Input: Root (pointer to a nonempty binary search tree T)
x (key to be inserted in T)
Algorithms: Sequential, Parallel and Distributed 4-14
P→Info ← x
Root→LeftChild ← P
else
InsertBinSrchTreeRec(Root → LeftChild, x)
endif
4.29 a) On p. 143 in the text we give pseudocode for the algorithm CreateBinSrchTree that
creates a binary search tree when duplicate keys are allowed to be inserted. In this problem we
b)
Algorithms: Sequential, Parallel and Distributed 4-15
c) Inserting the keys in increasing or decreasing order will build a completely right or left
d) The ordering 27, 22, 1, 0, 11, 23, 72, 55, 108 builds the complete tree building the left
4.30 We use induction on the number n of nodes in the tree T.
Basis step: n = 1. Trivial.
Induction step: Assume that the result is tree for all binary trees having k < n nodes, and
4.32 Pseudocode for an altered SearchBinSrchTree that determines the locations of both the
search element and its parent results from adding the output parameter Parent to the
4.33 a)
procedure InsertBinSrchTree2(Root, x)
Input: Root (pointer to a binary search tree T)
R ← R→RightChild
endif
b) If x and y are two keys having the same value, and x is inserted before y, then when y is
inserted using the move-to–the-right rule, it will eventually reach the node containing x and
then move to the right. In other words, y will be inserted into the right subtree of the node
4.34 We assume that the nodes in the m-way search tree have a similar but simplified structure
to that for B-trees as discussed in Chapter 21, and have the following structure:
m-wayTreeNode = record
4.35
procedure m-wayTreeSearch(Root, X, Found, Location, Index)
Input: Root (pointer to m-way search tree), X (a search element)
Algorithms: Sequential, Parallel and Distributed 4-17
Output: Found (.true. if X is found, .false. otherwise), Location (pointer to node where X is
4.36 We prove that an inorder traversal of the binary search tree visits the keys in increasing
order by induction on the number n of nodes in the tree.
Basis step: n = 1. Trivial.
4.37 This requires that duplicate keys are inserted using the move-to-the-right rule discussed in
4.38 It should be noted that it is understood that the a path here means that no node has two
children. For the “only if” part, if Tπ is not a path, then there is a node in Tπ with two children
that are roots of nonempty subtrees, say, L and R. Clearly you can add all the elements in L
before adding any elements in R, or vice-versa. Thus the permutation building Tπ is not unique.
4.39 The best-case complexity of CreateBinSrchTree occurs when a complete tree is built.
Now the complete tree on n nodes has depth d = log2n. When a given node is inserted,
no more than d comparisons are made, so that B(n) ≤ nd
O(nlogn). On the other hand,
4.41 We show the state of the array after each insertion, and only show as a figure the final
heap.
i
Insert
0
1
2
3
4
5
6
7
8
A[i]
5
23
65
108
2
73
41
52
34
A[i]
23
23
5
65
108
2
73
41
52
34
A[i]
65
65
5
23
108
2
73
41
52
34
A[i]
108
108
65
23
5
2
73
41
52
34
A[i]
2
108
65
23
5
2
73
41
52
34
A[i]
73
108
65
73
5
2
23
41
52
34
A[i]
41
108
65
73
5
2
23
41
52
34
A[i]
52
108
65
73
52
2
23
41
5
34
A[i]
34
108
65
73
52
2
23
41
5
34
4.42 We show the final result of each adjustment state, and show a figure with the final heap.
i
0
1
2
3
4
5
6
7
8
A[i]
5
23
65
108
2
73
41
52
34
A[i]
5
23
65
108
2
73
41
52
34
A[i]
5
23
73
108
2
65
41
52
34
A[i]
5
108
73
52
2
65
41
23
34
A[i]
108
52
73
34
2
65
41
23
5
4.43 If the new value v for x is larger, then we let v fall to a proper position in the subtree
rooted at x. Otherwise, we follow a path up the path from x to the root until we find a
proper position for the new value v. The pseudocode follows, where we assume that the
min-heap is implemented as a complete binary tree, and the parameter i is the index of
where x occurs in the tree. Clearly ChangePriority has O(logn) worst-case complexity.
//(j –1)/2 is a proper position for v
while j ≥ n .and. .not. Found do
if j < n – 1.and. A[j] < A[j + 1] then //then move to right child j + 1
j ← j + 1 //path finder updated to right child
endif
j ← (i – 1)/2
while j ≥ 0 .and. A[j] > v do
A[i] ← A[j] //move parent down one position in path
i ← j //move v up one position in path
j ← (j – 1)/2
4.44 a) This exercise is a straightforward generalization of the array implementation of a
heap using a complete binary tree to using a complete k-ary tree. One merely notes that the
formula for the parent of a node with index i is given by
−
k
i1
, whereas the children of
Algorithms: Sequential, Parallel and Distributed 4-21
k−+
b) When inserting an element into a heap implemented as a complete k-ary tree, the worst-
case occurs when the element follows a path all the way to the root, so that d
c) When deleting a key from a heap implemented as a complete k-ary tree, in the worst
case the last element that was elevated to the root must trickle down all the way to the
d) The k-ary heapsort is the straightforward generalization of the case k = 2. After creating
the heap in linear time, we then sort the array by interchanging the top element with the
4.45 We prove Proposition 4.7.1 with the strengthened conclusion that the depth of any tree in
F having j vertices is at most
 
j
2
log
. We prove the result by a (strong) induction on j.
Basis step: When j = 1, the result is immediate, since the depth of a tree with one vertex is 0
4.46 a)
b)
Algorithms: Sequential, Parallel and Distributed 4-23