AVL TREES - Introduction to Java Programming: Comprehensive Version - page 967

LL rotation: An LL imbalance occurs at a node A , such that A has a balance factor of -2
and a left child B with a balance factor of -1 or 0 , as shown in Figure 26.2a. This type of
imbalance can be fixed by performing a single right rotation at A , as shown in Figure 26.2b.
RR rotation: An RR imbalance occurs at a node A , such that A has a balance factor of
+2 and a right child B with a balance factor of +1 or 0 , as shown in Figure 26.3a. This type
of imbalance can be fixed by performing a single left rotation at A , as shown in Figure 26.3b.

LL rotation
LL imbalance

RR rotation
RR imbalance

A

2

0 or 1 B

1 or 0 B A 0 or 1

h

T3

h 1

T1

h h h

T2 T2 T3

h 1

T1

T2's height is h or
h 1

T2's height is h or
h 1

(a) (b)

F IGURE 26.2

An LL rotation fixes an LL imbalance.

0 or 1

A 2 B

B

1 or 0

0 or 1 A

h

T3

h 1

T1

h h

h

T3 T2

T2

h 1

T1

T2's height is
h or h

T2's height is
h or h

1 1

(a) (b)

F IGURE 26.3

An RR rotation fixes an RR imbalance.

LR rotation: An LR imbalance occurs at a node A , such that A has a balance factor of -2
and a left child B with a balance factor of +1 , as shown in Figure 26.4a. Assume B 's right child
is C . This type of imbalance can be fixed by performing a double rotation (first a single left
rotation at B and then a single right rotation at A ), as shown in Figure 26.4b.
RL rotation: An RL imbalance occurs at a node A , such that A has a balance factor of +2
and a right child B with a balance factor of -1 , as shown in Figure 26.5a. Assume B 's left child
is C . This type of imbalance can be fixed by performing a double rotation (first a single right
rotation at B and then a single left rotation at A ), as shown in Figure 26.5b.

LR rotation
LR imbalance

RL rotation
RL imbalance

26.1

✓ ✓

What is an AVL tree? Describe the following terms: balance factor, left-heavy, and
right-heavy.

Check

Point

26.2

Show the balance factor of each node in the trees shown in Figure 26.6.

26.3

Describe LL rotation, RR rotation, LR rotation, and RL rotation for an AVL tree.