Java Reference
In-Depth Information
73 }
74
75 // post: prints in reversed preorder the tree with given
76 // root, indenting each line to the given level
77
private void
printSideways(IntTreeNode root,
int
level) {
78
if
(root != null) {
79 printSideways(root.right, level + 1);
80
for
(
int
i = 0; i < level; i++) {
81 System.out.print(" ");
82 }
83 System.out.println(root.data);
84 printSideways(root.left, level + 1);
85 }
86 }
87 }
Each level of a binary search tree can hold twice as many nodes as the level above it.
The one root node can have two children, four grandchildren, eight great-grandchildren,
and so on. As a result, we can store a lot of values in a tree that has a relatively small
number of levels.
The number of nodes and the number of levels have an important relationship. If
you have
k
levels in a tree, then you can store approximately 2
k
values in the tree.
Going in the other direction, if you want to include
N
nodes in a tree, you will need
approximately log
N
levels for the tree. We normally use this second way of thinking
about the relationship.
It may not seem immediately obvious how powerful this is because you may not
realize how much smaller log
N
is than
N
. Consider some examples. To store a thou-
sand values, you would need around 10 levels. Increase the number of values to a
million, and you need 20 levels. Increase the number to a billion, and you need
30 levels. To store a trillion values, you need only 40 levels for the tree. As a result,
binary search trees tend to be relatively short in height, even when they store vast
amounts of data.
It is also important to realize that the insertion algorithm we have developed in this
chapter does not guarantee that the tree will store data efficiently in the minimum
number of levels. While it's true that you can store a trillion values with just 40 levels,
you might end up with considerably more levels than that. Consider, for example,
what happens if the data are inserted in sorted order. If you build a binary search tree
by inserting the sequential numbers 1 through 1000, you end up with a tree that looks
like this one:
Search WWH ::
Custom Search