# Splay Tree - Insert Permutation

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.

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