data-structurestreebinary-search-treeavl-treesplay-tree

A sequence that forms the same AVL and splay trees?


Is there such a sequence of numbers (1-7, all numbers used, only once each), that would form equal AVL and splay tree?


Solution

  • 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)