Chapter Eight/ Binary Search TreesPage 1
Chapter Eight – Binary Search Trees
Section 1– Trees
1.
a.The level of a binary search tree determines the maximum number of comparisons that are required to find an element in the tree.
b.100
c.7
2.c
3. b
4. N
5. There are five possible shapes of trees:
X X X X X
X X X X X X
X X X X
For each shape there are 6 ways of distributing the numbers 1, 2, 3 across the nodes.
So, the answer is 5 X 6 = 30.
6. We have the same five possible shapes as in number 5, but now there is only one way of distributing the numbers for each shape that maintains the binary search tree property. So, the answer is 5.
7.There are 5:
X X X X X
/ \ / \ / \ / \ / \
X X X X X X X X X X
/ \ / \ / \ / \ / \ / \
X X X X X X X X X X X X
/ \ / \ / \ / \
X X X X X X X X
8.
a.Q, K, and M
b.B, D, J, M, P, and N
c.8
d.16
eBDJKMNPQRTWY
fBJDNPMKRWYTQ
gQKDBJMPNTRYW
9.
a. 4
b. 11, 29, 62
c. 0, 1
d. 12 - there are 13 nodes; they can be arranged in a degenerate tree, in increasing order from root to leaf, using only the right links
e. 3 - a balanced tree
f. 11, 22, 23, 29, 30, 47, 49, 56, 59, 61, 62, 64, 69
g. 56, 47, 22, 11, 29, 23, 30, 49, 69, 59, 62, 61, 64
h. 11, 23, 30, 29, 22, 49, 47, 61, 64, 62, 59, 69, 56
10False
Section 3 – The Application Level
15.
int countLess(BinarySearchTree<Golfer> tree, Golfer maxValue)
{
int treeSize;
int numNodes = 0;
treeSize = tree.reset(BinarySearchTree.INORDER);
for (int count = 1; count <= treeSize; count++)
{
if ((tree.getNext(BinarySearchTree.INORDER).compareTo(maxValue))
<= 0)
numNodes = numNodes + 1;
}
return numNodes;
}
Section 5 – Iterative versus Recursive Method Implementations
20.Can really just return root
25. The question just asked for a “design” so these answers are in algorithmic form.
a.The minimum element is the leftmost element:
public min: returns T
// Precondition: this tree is not empty
//
// Returns the minimum node of this tree.
Set currNode to root
While currNode.getLeft() != null
Set currNode to currNode.getLeft()
return currNode
b. As with our other recursive approaches we have a public and a private method:
public min: returns T
// Precondition: this tree is not empty
//
// Effect: returns the minimum node of this tree
return recMin(root)
private recMin (tree): returns T
if (tree.getLeft() != null)
return recMin(tree.getLeft())
else
return tree
c. Both approaches are straightforward. They have the same Big-Oh efficiency. It is probably better to use the iterative version since it has less time overhead and does not require space to store activation records.
Section 6 – The Implementation Level: Remaining Operations
28.
a.add, recAdd, recAdd, recAdd, recAdd, recAdd
b.add, recAdd, recAdd, recAdd, recAdd
c.add, recAdd, recAdd, recAdd, recAdd, recAdd
d.remove, recRemove, recRemove, recRemove, removeNode
e.remove, recRemove, removeNode, getPredecessor, recRemove, recRemove, recRemove, removeNode
f.remove, recRemove, recRemove, recRemove, removeNode
29.
30.
31.
a. The path would go through the nodes containing 56, 69, 59, 62, and 61.
b. The path would go through the nodes containing 56, 47, 22, 29, and 23, before determining that 28 is not in the tree.
32.
33.
56
4769
224959 77
11 29 48 62 76
9 23 30 61 64
10 63
38.Inorder
39. Preorder
Section 7 – Comparing Binary Search Trees and Linear Lists
41.Elements inserted in random order:
Sorted linked list: O(N)
Binary search tree: O(log2N)
42. Elements inserted in increasing order:
Sorted linked list: O(N)
Binary search tree: O(N) [this would be a “degenerate” tree]
Section 8 – Balancing a Binary Search Tree
45.The postorder is 1 5 7 12 18 15 10. Inserting these in index order gives
1
57
12
15 18
10
46.a.
15
619
391729
b.
15
619
391729
37
c.
3
324
137
2
3
3
3
3
3
Section 9 – A Nonlinked Representation of Binary Trees
48.
a. e
b. b, d, e
c. b, e
50.
.numElements / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 1511 / 60 / 53 / 3 / 49 / 46 / 1 / 2 / 48 / 16 / 25 / 40 / -1 / -1 / -1 / -1 / -1
51.
15
10 12
347 83
20 17 8
Chapter Nine – Priority Queues, Heaps, and Graphs
Section 1 – Priority Queues
1
a.
protected LLNode<T> list; // first node on the list
b. The code is the same as for the add method of the RefSortedList class as presented in Chapter 6, page 444, except we must reverse the relational operator so that the elements are stored from largest to smallest.
c.
public T dequeue() throws PriQUnderflowException
// Throws PriQUnderflowException if this priority queue is empty;
// otherwise, removes element with highest priority from this
// priority queue and returns it.
{
T hold; // element to be dequeued and returned
if (list == null)
throw new PriQUnderflowException("Priority queue is empty");
else
{
hold = list.getInfo(); // remember element to be returned
list = list.getLink(); // reset start of list
return hold; // return largest element
}
}
Section 2 – Heaps
6.
a. No. Does not possess the shape property.
b. No. Does not possess the order property.
c. No. Does not possess the shape property.
d. Yes.
e. No. Does not possess the order property.
f. No. Does not possess the shape property.
11.
a.
b.x = 56, y = 42, z = 40