Java Reference
In-Depth Information
3.
Consider the implementation of the method
rebalance
for an AVL tree, as given in Segment 27.11. The perfor-
mance of this method depends on the cost of a rotation and the cost of the method
getHeightDifference
.
a.
Assume that the tree has height
h
and that
nodeN
is at height
k
. What is the cost, using Big O notation, of
each of the following tasks?
•
A rotation
•
Executing the method
getHeightDifference
•
Executing the method
rebalance
b.
Suppose that a node is added at the bottom of the tree by the method
add
. How many times will
rebalance
be called? Give a Big Oh expression for the cost of adding a node.
4.
Design and implement a class of nodes that you can use in the implementation of an AVL tree. You can derive this
class from
BinaryNode
. Each node, as the root of a subtree, should contain the height of this subtree. Implement a
class of AVL trees using your new class of nodes.
5.
Design a class of nodes that you can use in the implementation of a 2-4 tree. Is one class enough, or will you need
several?
6.
Implement a class of 2-4 trees in which only additions and retrievals are permitted.
7.
Implement a class of red-black trees that permit only additions and retrievals.
8.
Implement a class of sets that stores its entries in an instance of the class of red-black trees defined in the previous
project. You can omit the methods
remove
and
clear
from your class. Recall that Chapter 1 defined a set as a bag
that does not permit duplicate entries.
9.
Design and carry out an experiment to compare the heights of ordinary binary search trees with the heights of
either AVL trees or red-black trees. You first will need to complete either Project 2 or Project 7.
10.
Design a class
BTreeNode
of nodes for a B-tree of order
m
. Consider operations that allow you to
•
Get a particular value from the node
•
Insert a value into the node while maintaining the links to subtrees (remember that the B-tree is a
search tree)
•
Get a count of the number of values in the node
•
Replace a value in the node, if the search tree is maintained
•
Replace a subtree
•
Split a node into two nodes, each containing half the values
•
Give an algorithm for adding a new value to a B-tree whose implementation uses your definition of
BTreeNode
.
11.
Implement a priority queue by using one of the balanced search trees in this chapter.
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
Node
N
contains 60, and node
C
contains 50.
T
1
is the one-node subtree containing 20.
T
2
and
T
3
are empty.
2.
Since we had a binary search tree before the rotation, the value in node
N
is less than the value in node
C
and all
the values in
T
2
. Moreover, all values in
T
2
are less than the value in node
C
. These relationships are maintained
after the rotation, since node
N
is a le'ft child of node
C
, and
T
2
is a right subtree of node
N
. Also, the subtrees
T
1
and
T
3
have their original parents in the new tree. Thus, the resulting tree is a binary search tree.
