Menu
Is there such a sequence of numbers (1-7, all numbers used, only once each), that would form equal AVL and splay tree?
680
Splay trees are more memory-efficient than AVL trees, because they do not need to store balance information in the nodes. However, AVL trees are more useful in multithreaded environments with lots of lookups, because lookups in an AVL tree can be done in parallel while they can't in splay trees.
Zig rotation: This rotation is similar to the right rotation in the A V L AVL AVL tree. In zig rotation, every node moves one position to the right of its current position. We use Zig rotation when the item which is to be searched is either a root node or a left child of the root node.
Splay trees are useful if you want fast access to recently-used items. Red-black trees are useful if insertion/deletion are a lot more frequent than lookup. AVL trees are useful if lookup is a lot more common than insertion/deletion.
Splay trees are a lot like other binary search trees. They have nodes, and each node has two children, one left and one right. There is a root node that serves at the begining of the tree. The main difference, though, is that the root node is always the last element that was accessed.
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
