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

FOR i := 1 TO n DO

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.

  • $\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.