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

Recall from Section 18.1 that the size of a node is the number of its descen-
dants (including itself). Suppose that we want to find the K th smallest element
and that K is at least 1 and at most the number of nodes in the tree. Figure 19.13
shows three possible cases, depending on the relation of K and the size of the
left subtree, denoted S L . If K equals S L + 1, the root is the K th smallest element
and we can stop. If K is smaller than S L + 1 (i.e., smaller than or equal to S L ), the
K th smallest element must be in the left subtree and we can find it recursively.
(The recursion can be avoided; we use it to simplify the algorithm descrip-
tion.) Otherwise, the K th smallest element is the ( K - S L - 1)th smallest ele-
ment in the right subtree and can be found recursively.
The main effort is maintaining the node sizes during tree changes.
These changes occur in the insert , remove , and removeMin operations. In prin-
ciple, this maintenance is simple enough. During an insert , each node on the
path to the insertion point gains one node in its subtree. Thus the size of each
node increases by 1, and the inserted node has size 1. In removeMin , each node
on the path to the minimum loses one node in its subtree; thus the size of each
node decreases by 1. During a remove , all nodes on the path to the node that is
physically removed also lose one node in their subtrees. Consequently, we can
maintain the sizes at the cost of only a slight amount of overhead.

We can implement
findKth by main-
taining the size of
each node as we
update the tree.

19.2.1 java implementation

Logically, the only changes required are the adding of findKth and the main-
tenance of a size data member in insert , remove , and removeMin . We derive a
new class from BinarySearchTree , the skeleton for which is shown in
Figure 19.14. We provide a nested class that extends BinaryNode and adds a
size data member.
BinarySearchTreeWithRank adds only one public method, namely findKth ,
shown at lines 31 and 32. All other public methods are inherited unchanged.
We must override some of the protected recursive routines (lines 36-41).

We derive a new
class that supports
the order statistic.

figure 19.13
Using the size data
member to implement
findKth

X X X

S L S R S L S R S L S R

K < S L + 1 K = S L + 1 K > S L + 1

(a) (b) (c)