Is there such a sequence of numbers (1-7, all numbers used, only once each), that would form equal AVL and splay tree?
Asked
Active
Viewed 486 times
6
templatetypedef
- 362,284
- 104
- 897
- 1,065
Issak
- 96
- 1
- 8
-
Are you only allowed to do insertions? Or can you do lookups after insertions? – templatetypedef Jan 28 '13 at 17:11
-
It doesn't specify, I think professor would be impressed if I complicate things. It just says 'procedure' for each tree. I guess the input and final result is what matters. – Issak Jan 28 '13 at 18:06
-
if you put 1-2-3-4-5-6-7 in avl tree and then put 1-3-5-7-2-6-4 in splay tree , the result is the same , is it your mean ? – Erfan Tavakoli Jan 29 '13 at 08:34
-
No, the sequence should be the same for AVL and Splay tree, and resulting in same tree. Thanks for you answer though. – Issak Jan 29 '13 at 10:28
-
@ErfanTavakoli: shouldn't it be 1-3-2-5-7-6-4 in splay tree? – arunmoezhi Mar 07 '14 at 19:40
-
4if I were you, I would rather impress your professor with a solution found by you, instead of one found by the SO people. That would also be the best way to learn something – Walter Tross Mar 08 '14 at 16:04
-
@WalterTross: I have thought of solutions, but I don't think there is one because of the ways avl and splay trees are defined and reshaped. It was a question on an old exam, not even worth many points, and after thinking about it, I thought it might be interesting for others too. Thank you for your concern, but don't worry about me impressing professors, I've done a lot of that already. I only went to SO after a long thinking about the problem and after solving other 100 myself. – Issak Mar 08 '14 at 20:13
-
1Could always use brute force. Building 7! trees with only 7 elements in the tree won't take very long at all. Although, it might require a custom algorithm to compare the trees. – Nuclearman Mar 08 '14 at 23:44
-
@Nuclearman: even less than that, because, in an AVL tree only 3, 4 or 5 can be at the root, which for a splay tree means that one of these must be the last number added. Of course, brute force would not yield an interesting answer, because the code would be too much, and the resulting sequence(s) too little. Let's see if an interesting answer arises. – Walter Tross Mar 09 '14 at 00:05
-
I was referring to brute forcing each combination of insertion orders. Still, you do raise a point about 3, 4 and 5, which does reduce the need for a brute force solution. That combined with how a splay tree insert works, seems (I don't have implementations handy, so I haven't tried it) to give a rather straightforward approach to solving it. Seems like there are roughly, but not more than 2^5 solutions. – Nuclearman Mar 09 '14 at 01:25
-
@Nuclearman Brute force proved quite feasible without any special optimization -- see my answer below. – augurar Mar 14 '14 at 08:34
-
@augurar Indeed. I posted my by hand solution. If there are solutions, that should yield them. If there aren't solutions it should be possible to use that to prove whether or not solutions exist. They exist if the splay tree behaves as expected (based on last insert being the new root of the splay tree), and do not exist if the splay tree does not. – Nuclearman Mar 14 '14 at 17:09
-
Removed answer as it seems like the latter is the case, which makes solutions extremely few if any. – Nuclearman Mar 14 '14 at 18:24
1 Answers
5
Well, in the interests of science, I implemented both AVL and splay trees in Python based on their respective Wikipedia articles. Assuming I didn't make a mistake somewhere, my finding is that there are no permutations of {1, ..., 7} that produce the same AVL and splay tree. I conjecture the same is true for all sets of size k > 3. As to the fundamental reasons for this, I have no idea.
If someone would like to vet 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.l.h if self.l else 0
def rh(self):
''' Get height of right child '''
return self.r.h 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 #
#########################
# v u
# / \ / \
# u c --> a v
# / \ / \
# a b b c
def rright(v):
''' Rotate right '''
u = v.l
u.r, v.l = v, u.r
if v.l:
v.l.p = v
u.p, v.p = v.p, u
return u
# u v
# / \ / \
# a v --> u c
# / \ / \
# b c a b
def rleft(u):
''' Rotate left '''
v = u.r
u.r, v.l = v.l, u
if u.r:
u.r.p = u
u.p, v.p = v, u.p
return v
######################
# AVL tree functions #
######################
def avl_lr(v):
v.l = rleft(v.l)
v.l.l.hup()
v.l.hup()
return avl_ll(v)
def avl_ll(v):
u = rright(v)
u.r.hup()
u.hup()
return u
def avl_rl(v):
v.r = rright(v.r)
v.r.r.hup()
v.r.hup()
return avl_rr(v)
def avl_rr(v):
u = rleft(v)
u.l.hup()
u.hup()
return u
def avl_insert(v, n, p=None):
if v is None:
return HNode(n, p)
if n < v.n:
v.l = avl_insert(v.l, n, v)
v.hup()
if v.lh() > v.rh() + 1:
return (avl_ll if (v.l.lh() > v.l.rh()) else avl_lr)(v)
else:
return v
else:
v.r = avl_insert(v.r, n, v)
v.hup()
if v.rh() > v.lh() + 1:
return (avl_rr if (v.r.rh() > v.r.lh()) 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 < p.n:
p.l, x = bst_insert(p.l, n, p)
else:
p.r, x = bst_insert(p.r, n, p)
return p, x
def splay(x):
''' Percolate x to the root of its tree '''
if x.p:
p = x.p
g = p.p
if g:
if p.n < g.n:
if x.n < p.n:
x = rright(rright(g))
else:
g.l = rleft(p)
x = rright(g)
else:
if x.n > p.n:
x = rleft(rleft(g))
else:
g.r = rright(p)
x = rleft(g)
p = x.p
if p:
if x.n < p.n:
p.l = x
else:
p.r = x
return splay(x)
else:
if x.n < p.n:
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)
augurar
- 12,081
- 6
- 50
- 65