Order Statistics Tree on top of Treap

I built an Order Statistics tree on top of a Treap in order to solve this HackerRank problem. It works (passed all test cases). Any comments whatsoever would be greatly appreciated.

class EmptyTreeError(Exception): def __init__(self): self.error = "Empty tree" class node(object): def __init__(self,val,prty,prnt=None,lchild=None,rchild=None): self.prnt = prnt self.lchild = lchild self.rchild = rchild self.val = val self.prty = prty self.size = 1 def __str__(self, *args, **kwargs): return str((self.val,self.prty,self.size,(self.prnt.val,self.prnt.prty) if self.prnt else None)) # size needs to be recalculated all the way up to the root on insertions and deletions def recalc_size(self): self.size = (self.lchild.size if self.lchild else 0) + (self.rchild.size if self.rchild else 0) + 1 # always need to keep track of the root because it potentially changes def find_root(self): p = self while p.prnt != None: p = p.prnt return p def ppprint(self): return self.pprint([],True,[]) # basically an inorder traversal # really clever def pprint(self,pref,isTail,sb): if self.rchild: t = pref + list("│ " if isTail else " ") self.rchild.pprint(t, False, sb) t = pref + list("└── " if isTail else "┌── ") + list(str(self)) sb.append(t) if self.lchild: t = pref + list(" " if isTail else "│ ") self.lchild.pprint(t, True, sb) return sb @total_ordering class End(object): def __lt__(self,other): return False BOT = End() def rotate_left(p,r): p.rchild = r.lchild # idiot - don't forget to reset child parent if p.rchild != None: p.rchild.prnt = p r.lchild = p # need to adjust child of parent of p if p.prnt: if p == p.prnt.lchild: p.prnt.lchild = r else: p.prnt.rchild = r r.prnt = p.prnt p.prnt = r p.recalc_size() r.recalc_size() def rotate_right(p,q): p.lchild = q.rchild if p.lchild != None: p.lchild.prnt = p q.rchild = p if p.prnt: if p.prnt.lchild and p == p.prnt.lchild: p.prnt.lchild = q else: p.prnt.rchild = q q.prnt = p.prnt p.prnt = q p.recalc_size() q.recalc_size() def bubble_up(p): while p.prnt and p.prty < p.prnt.prty: if p == p.prnt.lchild: rotate_right(p.prnt,p) else: rotate_left(p.prnt,p) def bubble_down(p): while (p.lchild and p.prty > p.lchild.prty) or (p.rchild and p.prty > p.rchild.prty): if p.lchild != None and (p.rchild == None or (p.lchild.prty < p.rchild.prty)): rotate_right(p,p.lchild) elif p.rchild != None and (p.lchild == None or (p.rchild.prty < p.lchild.prty)): rotate_left(p,p.rchild) def insert(root,key): # insert and remove traversal are different: insert needs to # keep going but remove needs to stop p = root while (p.lchild and key <= p.val) or (p.rchild and key > p.val): if p.lchild and key <= p.val: p = p.lchild else: p = p.rchild if key <= p.val: nod = node(key,myRand.uniform(0,1),p) p.lchild = nod else: nod = node(key,myRand.uniform(0,1),p) p.rchild = nod # recalculate tree decorations all the way up to the root p = nod while p != None: # find root p.recalc_size() p = p.prnt bubble_up(nod) def delete(p): p.prty = BOT bubble_down(p) if p.prnt: if p.prnt.lchild and p == p.prnt.lchild: p.prnt.lchild = None else: p.prnt.rchild = None while p != None: # find root p.recalc_size() p = p.prnt else: raise EmptyTreeError def select(p,i): try: rank = (p.lchild.size if p.lchild else 0) + 1 except: print(p,i) if i == rank: return p.val elif i < rank: return select(p.lchild,i) else: return select(p.rchild,i - rank) def remove(root,key): p = root while (p.lchild and key < p.val) or (p.rchild and key > p.val): if p.lchild and key < p.val: p = p.lchild else: p = p.rchild if p.val == key: delete(p) else: raise KeyError