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.
