Java Reference
In-Depth Information
We perform a single rotation (because 50 is an outside node) between 60 and
70, thus making 60 the black root of 30's right subtree and making 70 red, as
shown in Figure 19.40. We then continue, performing an identical action if we
see other nodes on the path that contain two red children. It happens that there
are none.
When we get to the leaf, we insert 45 as a red node, and as the parent is
black, we are done. The resulting tree is shown in Figure 19.41. Had the par-
ent been red, we would have needed to perform one rotation.
As Figure 19.41 shows, the red-black tree that results is frequently well
balanced. Experiments suggest that the number of nodes traversed during an
average red-black tree search is almost identical to the average for AVL trees,
even though the red-black tree's balancing properties are slightly weaker. The
advantage of a red-black tree is the relatively low overhead required to perform
insertion and the fact that, in practice, rotations occur relatively infrequently.
19.5.3
java implementation
An actual implementation is complicated, not only by many possible rota-
tions, but also by the possibility that some subtrees (such as the right subtree
of the node containing 10 in Figure 19.41) might be empty and by the special
figure 19.40
Result of single
rotation that fixes the
violation at node 50
30
15
60
10
20
50
70
5
40
55
65
85
80
90
figure 19.41
Insertion of 45 as a
red node
30
15
60
10
20
50
70
5
40
55
65
85
45
80
90
Search WWH ::
Custom Search