M-1) NOW
/ \
/ \
IS THE
/ / \
/ / \
FOR STUDENTS TIME
/ \ / \ \
/ \ / \ \
ALL GOOD STRUCTURES STUDY TO
\ \
\ \
DATA WELL
M-2) BEN
/ \
/ \
ABE PETE
/
/
DAN
\
\
DON
N-1) a) B b) C
/ \ / \
/ \ / \
D A A F
\ / \
\ / \
C B E
/ \ /
/ \ /
E F D
c) A d) A
/ \ / \
/ \ / \
D C B F
\ / \ / /
\ / \ / /
B E F D C
/
/
E
N-2) D NOTE: This is a trick tree! FIRST,
/ \ rotate left at B, then rotate right at E.
/ \ If you just rotate right at E, the
B E resulting tree will also be unbalanced!
/ \ \
/ \ \
A C F
N-3) D
/ \
/ \
B E
\ \
\ \
C F
N-4) D
/ \
/ \
B E
\
\
C
O-1) Threads should be: from D to B
from B to A
from F to C
from C to A
O-2) Threads should be: from D to A
from D to B
from B to A
from E to A
from F to E
from F to C
from C to A