Binary search trees - Data Structures and Problem Solving Using Java - page 766

IN PRACTICE
19.15

Implement find , findMin , and findMax recursively.

Implement findKth nonrecursively, using the same technique used for
a nonrecursive find .

19.16

An alternative representation that allows the findKth operation is to
store in each node the value of 1 plus the size of the left subtree. Why
might this approach be advantageous? Rewrite the search tree class to
use this representation.

19.17

Write a binary search tree method that takes two keys, low and high ,
and prints all elements X that are in the range specified by low and high .
Your program should run in O( K + log N ) average time, where K is the
number of keys printed. Thus if K is small, you should be examining
only a small part of the tree. Use a hidden recursive method and do not
use an inorder iterator. Bound the running time of your algorithm.

19.18

Write a binary search tree method that takes two integers, low and high ,
and constructs an optimally balanced BinarySearchTreeWithRank that
contains all the integers between low and high , inclusive. All leaves
should be at the same level (if the tree size is 1 less than a power of 2)
or on two consecutive levels. Your routine should take linear time .
Test your routine by using it to solve the Josephus problem presented
in Section 13.1.

19.19

The routines for performing double rotations are inefficient because
they perform unnecessary changes to children links. Rewrite them to
avoid calls to the single rotation routine.

19.20

Give a nonrecursive top-down implementation of an AA-tree. Com-
pare the implementation with the text's for simplicity and efficiency.

19.21

Write the skew and split procedures recursively so that only one call
of each is needed for remove .

19.22

PROGRAMMING PROJECTS
19.23

Redo the BinarySearchTree class to implement lazy deletion. Note that
doing so affects all the routines. Especially challenging are findMin and
findMax , which must now be done recursively.

Implement the binary search tree to use only one two-way compari-
son per level for find , insert , and remove .

19.24

Write a program to evaluate empirically the following strategies for
removing nodes with two children. Recall that a strategy involves
replacing the value in a deleted node with some other value. Which

19.25