Search code examples
data-structurestree-balancingsplay-treetree-rotation

How to create the bottom up splay tree from the following sequence

This is the sequence 20,10,5,30,40,57,3,2,4,35,25,18,22,27 I've tried it by making every new inserted node as the root but it's not working. Can anybody give me step by step explanation?

Solution

  • Bottom-up splaying starts from a newly inserted node x and performs zig/zag operations until root is reached. The pseudo code is

    splay_up(x)
while p(x) != null
    if x = c_l(p(x))
        if p(p(x)) = null // zig
            rotate_right(p(x))
        elif p(x) = c_l(p(p(x))) // zig-zig
            rotate_right(p(p(x)))
            rotate_right(p(x))
        elif p(x) = c_r(p(p(x))) // zig-zag
            rotate_right(p(x))
            rotate_left(p(x))
    elif x = c_r(p(x))
        if p(p(x)) = null // zig
            rotate_left(p(x))
        elif p(x) = c_r(p(p(x))) // zig-zig
            rotate_left(p(p(x)))
            rotate_left(p(x))
    elif p(x) = c_l(p(p(x))) zig-zag
        rotate_left(p(x))
        rotate_right(p(x))

    where p(x) is parent of x, c_l(x) is left child of x, c_r(x) is right child of x, tree rotations are made as usual.

    In you case, for the first seven numbers it would go like on the attached "diagram": enter image description here