A Binary Search Tree Implementation - Data Structures and Abstractions with Java - page 663

After the loop ends, compute the average number of comparisons needed to insert values into each tree. (For
each tree, divide its comparisonSum by 1000. Note that 1000 is 100—the number of iterations—multiplied by
10—the number of values inserted in one iteration.) Also compute the average height of each tree after the
insertions. (Divide each heightSum variable by 100.) Display and record your results.
Run the program a second time, but instead add 100 random values between 0 and 8000 during each
iteration of the loop. Run it a third time, but instead add 1000 random values. Discuss your results and draw
a conclusion.

11.

A k d-tree , or k -dimensional tree , is a binary tree that organizes points in k -dimensional space. Every node
contains and represents a k -dimensional point. Every node N that is not a leaf corresponds to a hyperplane 1 that
divides the space into two portions. Points to the left of the hyperplane are in N 's left subtree, and points to the
right of the hyperplane are in N 's right subtree. The relationship between the k -dimensional space and a k d-tree
enables you to use the tree to find all points within a given range—a range search —or to find the closest point to
a given point—a nearest-neighbor search .
In this project, we will choose k to be 2 and consider two-dimensional space and a 2d-tree whose nodes
contain points in that space. In an attempt to avoid any confusion that the term “2d-tree” might cause, computer
scientists commonly would describe the tree as a “2-dimensional k d-tree.” We, however, will use the shorter name
“2d-tree” here.
A 2d-tree generalizes a binary search tree in that it positions each node according to either the x or y coordinate
of its data point. The coordinate choice depends on the level at which the node is inserted into the tree. The first point
you insert into an empty tree is placed into a node that becomes the tree's root. If the next point to be inserted has an
x -coordinate that is less than the x -coordinate of the point in the root, you place the new point into the left child of the
root. Otherwise, you place it into the root's right child. Insertions at the next level—level 3—compare y -coordinates;
insertions at level 4 compare x -coordinates, and so on.
For example, let's insert the points (50, 40), (40, 70), (80, 20), (90, 10), and (60, 30) into an initially empty
2d-tree. Figure 25-15 traces the construction of this tree. Part a shows the root containing the first point, (50, 40).
(For the moment, ignore the drawings beneath the trees.) To insert (40, 70) into a child of the root, you compare
40, the point's x -coordinate with 50, the x -coordinate of the point in the root. Since 40 is less than 50, the new
point goes into the left child of the root, as Figure 25-15b shows. Similarly, since 80 is greater than 50, you
place the next point, (80, 20), into the right child of the root (Figure 25-15c). To insert (90, 10), you begin at the
tree's root and compare x -coordinates. Since 90 is greater than 50, you move to the root's right child and
compare y -coordinates. We find that 10 is less than 20, so (90, 10) goes into the left child of the root's right
child, as shown in Figure 25-15d. The final point, (60, 30), is positioned using similar steps to obtain the tree in
Figure 25-15e.
The graphical significance of a 2d-tree is illustrated beneath the trees shown in Figure 25-15. We begin
with a square that contains all of the points in the tree. For example, a 100 by 100 square, as shown in
Figure 25-15a, will contain the five points in our example. By passing a vertical line through the x -coordinate
of the point in the root, we divide the square into two regions. Any points in the root's left subtree will be to the
left of this line, while points in the root's right subtree will lie to the right of the line. Figure 25-15b shows a
horizontal line through the point (40, 70). Points in the left subtree of the node containing (40, 70) lie above
this horizontal line and to the left of the vertical line; that is, they lie within the upper-left rectangle within the
original square.

1. A hyperplane in k -dimensional space is a ( k - 1)-dimensional surface, described by a single linear equation in k variables, that divides the space
into two regions. For example, in 2-dimensional space, a straight line divides the space and is described by a linear equation in the variables x and y .
In 3-dimensional space, a plane divides the space and is described by a linear equation in the variables x , y , and z .