Question

. Perform splaying operation for the following node values: 12, 5, 7, 13, 9, 18, 4 added to a splay tree

Answer 1

A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.

Splay tree

Type

tree

Invented

1985

Invented by

Daniel Dominic Sleator and Robert Endre Tarjan

Time complexity in big O notation

Algorithm

Average

Worst case

Space

O(n)

O(n)

Search

O(log n)

amortized O(log n)

Insert

O(log n)

amortized O(log n)

Delete

O(log n)

amortized O(log n)

All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this with the basic search operation is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase.

Answer 2

Answer:

                                                 4

                                          5           18

                                       7          12    

                                                       13

This is the answer to the question. Please think that there are lines in between the nodes.

Explanation:

The main thing you should do is the element you are adding should become the main root. To make this we should do the rotations.