Well, in the interest of science, I implemented both AVL and splay trees in Python based on their respective Wikipedia articles. Assuming that I was not mistaken somewhere, my conclusion is that there are no permutations {1, ..., 7} that produce the same AVL and splay tree . I assume that the same is true for all sets of size k> 3. As for the main reasons for this, I have no idea.
If someone wants to check my code, here it is:
##################### # Class definitions # ##################### class Node: ''' A binary tree node ''' def __init__(self, n, p=None, l=None, r=None): self.n = n self.p = p self.l = l self.r = r self.h = None def __str__(self): return "[%s %s %s]" % (self.n, (self.l if self.l else "-"), (self.r if self.r else "-")) def __eq__(self, other): if not isinstance(other, Node): return NotImplemented return self.n == other.n and self.l == other.l and self.r == other.r def __ne__(self, other): return not (self == other) class HNode(Node): ''' A binary tree node, with height ''' def __init__(self, n, p=None, l=None, r=None): super(HNode, self).__init__(n, p, l, r) self.hup() def lh(self): ''' Get height of left child ''' return self.lh if self.l else 0 def rh(self): ''' Get height of right child ''' return self.rh if self.r else 0 def hup(self): ''' Update node height ''' self.h = max(self.lh(), self.rh())+1 def __str__(self): return "[%s (%d) %s %s]" % (self.n, self.h, (self.l if self.l else "-"), (self.r if self.r else "-")) ######################### # Basic tree operations # ######################### # vu # / \ / \ # uc --> av # / \ / \ # abbc def rright(v): ''' Rotate right ''' u = vl ur, vl = v, ur if vl: vlp = v up, vp = vp, u return u # uv # / \ / \ # av --> uc # / \ / \ # bcab def rleft(u): ''' Rotate left ''' v = ur ur, vl = vl, u if ur: urp = u up, vp = v, up return v ###################### # AVL tree functions # ###################### def avl_lr(v): vl = rleft(vl) vllhup() vlhup() return avl_ll(v) def avl_ll(v): u = rright(v) urhup() u.hup() return u def avl_rl(v): vr = rright(vr) vrrhup() vrhup() return avl_rr(v) def avl_rr(v): u = rleft(v) ulhup() u.hup() return u def avl_insert(v, n, p=None): if v is None: return HNode(n, p) if n < vn: vl = avl_insert(vl, n, v) v.hup() if v.lh() > v.rh() + 1: return (avl_ll if (vllh() > vlrh()) else avl_lr)(v) else: return v else: vr = avl_insert(vr, n, v) v.hup() if v.rh() > v.lh() + 1: return (avl_rr if (vrrh() > vrlh()) else avl_rl)(v) else: return v def build_avl_tree(s): ''' Build an AVL tree from the given sequence ''' v = None for n in s: v = avl_insert(v, n) return v ######################## # Splay tree functions # ######################## two = lambda x: (x,x) def bst_insert(p, n, g=None): ''' Insert a value into a BST, returning a pair consisting of the root of the tree and the new node ''' if p is None: return two(Node(n,g)) if n < pn: pl, x = bst_insert(pl, n, p) else: pr, x = bst_insert(pr, n, p) return p, x def splay(x): ''' Percolate x to the root of its tree ''' if xp: p = xp g = pp if g: if pn < gn: if xn < pn: x = rright(rright(g)) else: gl = rleft(p) x = rright(g) else: if xn > pn: x = rleft(rleft(g)) else: gr = rright(p) x = rleft(g) p = xp if p: if xn < pn: pl = x else: pr = x return splay(x) else: if xn < pn: return rright(p) else: return rleft(p) else: return x def splay_insert(p, n, g=None): r, x = bst_insert(p, n, g) return splay(x) def build_splay_tree(s): ''' Build a splay tree from the given sequence ''' v = None for n in s: v = splay_insert(v, n) return v #################### # The Big Question # #################### from itertools import permutations def find_matches(n): ''' Generate all permutations of {1, ..., n} that produce matching AVL and splay trees ''' for s in permutations(range(1, n+1)): t1 = build_avl_tree(s) t2 = build_splay_tree(s) if t1 == t2: yield s def find_match(n): ''' Return a permutation of {1, ..., n} that produces matching AVL and splay trees, or None if no such permutation exists ''' return next(find_matches(n), None)