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

19.4.3 double rotation

The single rotation has a problem: As Figure 19.28 shows, it does not work
for case 2 (or, by symmetry, for case 3). The problem is that subtree Q is too
deep, and a single rotation does not make it any less deep. The double rotation
that solves the problem is shown in Figure 19.29.
The fact that subtree Q in Figure 19.28 has had an item inserted into it
guarantees that it is not empty. We may assume that it has a root and two
(possibly empty) subtrees, so we may view the tree as four subtrees con-
nected by three nodes. We therefore rename the four trees A, B, C, and D . As
Figure 19.29 suggests, either subtree B or subtree C is two levels deeper
than subtree D (unless both are empty, in which case both are), but we can-
not be sure which one. Actually it does not matter; here, both B and C are
drawn at 1.5 levels below D .
To rebalance, we cannot leave k 3 as the root. In Figure 19.28 we showed
that a rotation between k 3 and k 1 does not work, so the only alternative is to

The single rotation
does not fix the
inside cases (2 and
3). These cases
require a double
rotation, involving
three nodes and
four subtrees.

figure 19.28
Single rotation does
not fix case 2.

k 2 k 1

k 1 k 2

R P

R

P

Q Q

(a) Before rotation (b) After rotation

figure 19.29
Left-right double
rotation to fix case 2

k 3 k 2

k 1 k 1 k 3

k 2

D

B C

A

A D

B C

(a) Before rotation (b) After rotation