1
$\begingroup$

Let $T$ be a Splay Tree. For a given permutation $\sigma$ on a set $S = \{1,2,3,...n \}$ we defined the following function:

Splay-Insert-Permutation(σ)
{
FOR i := 1 TO n DO
    T.Tree-Insert(σ(i))
    T.Splay(σ(i))
ENDFOR
}

We basically insert the elements of some permutation on $S$ one by one and perform splay after each insertion.

For $n = 3$ and $n=7$, I have found the permutations $S_{3} = \{1,3,2 \}$ and $S_{7} = \{1, 7, 3, 5, 2, 6, 4 \}$ to give a Splay tree $T$ with minimum height (full binary tree).

Is it possible to have more than one unique permutation for a fixed $n$ that will give a minimum height splay tree after performing the above method? Can we generalize something about them? Thanks.

$\endgroup$
  • $\begingroup$ Why don't you try writing a program to try exhaustively all permutations, for $n=1,2,\dots,10$, and see what you find? $\endgroup$ – D.W. Jun 13 '18 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.