Splay trees - Data Structures and Problem Solving Using Java - page 860

figure 22.12
Steps in a top-down
splay (accessing 19 in
the top tree)

Empty

12

Empty

25

5

20

30

15

24

13 18

16

Empty

12 25

Simplified zig-zag

20

30

5

15

24

13 18

16

Zig-zig

12

15 20

13 18

25

5

16

24 30

Zig

12

20

18

16 25

5 15

24 30

Reassemble

13

18

12

20

25

5 15

13 16 24 30

implementation of
top-down splay trees

22.6

The splay tree class skeleton is shown in Figure 22.13. We have the usual
methods, except that find is a mutator rather than an accessor. The BinaryNode
class is our standard package-visible node class that contains data and two
child references, but it is not shown. To eliminate annoying special cases,