SHARE
TWEET

Dynamic Trees with Revert

a guest Mar 24th, 2014 581 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/python
  2.  
  3. class Node:
  4.   def __init__(self, left = None, right = None, parent = None):
  5.     self.left   = left
  6.     self.right  = right
  7.     self.parent = parent
  8.     self.link   = None
  9.     self.rev    = False
  10.     self.size   = 1
  11.  
  12. def size(v):
  13.   return 0 if v == None else v.size
  14.  
  15. def recomp(v):
  16.   v.size = 1 + size(v.left) + size(v.right)
  17.  
  18. def set_parent(child, parent):
  19.   if child != None:
  20.     child.parent = parent
  21.  
  22. def reverse(v):
  23.   if v != None:
  24.     v.rev ^= True
  25.  
  26. def push(v):
  27.   if v != None and v.rev:
  28.     v.left, v.right = v.right, v.left
  29.     v.rev = False
  30.     reverse(v.left)
  31.     reverse(v.right)
  32.    
  33.  
  34. def keep_parent(v):
  35.   set_parent(v.left, v)
  36.   set_parent(v.right, v)
  37.   recomp(v)
  38.  
  39. def rotate(parent, child):
  40.   """Rotates the parent-child nodes and keeps consistency of the tree"""
  41.   gparent = parent.parent
  42.   if gparent != None:
  43.     if gparent.left == parent:
  44.       gparent.left = child
  45.     else:
  46.       gparent.right = child
  47.  
  48.   if parent.left == child:
  49.     parent.left, child.right = child.right, parent
  50.   else:
  51.     parent.right, child.left = child.left, parent
  52.  
  53.   keep_parent(parent)
  54.   keep_parent(child)
  55.   child.parent = gparent
  56.  
  57. def splay(v):
  58.   if v.parent == None:
  59.     return v
  60.   parent = v.parent
  61.   gparent = parent.parent
  62.   if gparent == None:
  63.     rotate(parent, v)
  64.     return v    
  65.   else:
  66.     zigzig = (gparent.left == parent) == (parent.left == v)
  67.     if zigzig:
  68.       rotate(gparent, parent)
  69.       rotate(parent, v)
  70.     else:
  71.       rotate(parent, v)
  72.       rotate(gparent, v)
  73.     return splay(v)
  74.  
  75. def find(v, lhs):
  76.   if v == None:
  77.     return None
  78.   push(v)
  79.   threshold = size(v.left)
  80.   if lhs == threshold:
  81.     return splay(v)
  82.   if lhs < threshold and v.left != None:
  83.     return find(v.left, lhs)
  84.   if lhs > threshold and v.right != None:
  85.     return find(v.right, lhs - threshold - 1)
  86.   return splay(v)
  87.    
  88. def split(root, lhs):
  89.   if root == None:
  90.     return None, None
  91.   root = find(root, lhs)
  92.   if root.size <= lhs:
  93.     return root, None
  94.   set_parent(root.left, None)
  95.   root.left = None
  96.   recomp(root)
  97.   return root.left, root
  98.  
  99.  
  100. def merge(left, right):
  101.   if right == None:
  102.     return left
  103.   if left == None:
  104.     return right
  105.   right = find(right, 0)
  106.   right.left = left
  107.   keep_parent(right)
  108.   return right
  109.  
  110. def cleanup(v):
  111.   if v == None:
  112.     return
  113.   cleanup(v.parent)
  114.   push(v)
  115.  
  116. def supportRoot(v):
  117.   cleanup(v)
  118.   return splay(v)  
  119.  
  120. def cutout(v):
  121.   supportRoot(v)
  122.   left, right = split(v, size(v.left) + 1)
  123.   if right != None:
  124.     find(right, 0).link = v
  125.   return v
  126.  
  127. def expose(v):
  128.   v = find(cutout(v), 0)
  129.   while v.link != None:
  130.     nxt = cutout(v.link)
  131.     v.link = None
  132.     v = find(merge(nxt, v), 0)
  133.   return v
  134.  
  135. def depth(v):
  136.   expose(v)
  137.   return supportRoot(v).size - 1
  138.    
  139. def link(child, parent):
  140.   child.link = parent
  141.   return expose(child)
  142.  
  143. def cut(child, parent):
  144.   expose(parent)
  145.   child.link = None
  146.  
  147. def find_root(v):
  148.   return expose(v)
  149.  
  150. def revert(v):
  151.   root = expose(v)
  152.   reverse(supportRoot(root))
  153.  
  154. def dist(u, v):
  155.   revert(u)
  156.   w = expose(v)
  157.   if w != u:
  158.     return -1
  159.   return depth(v)
  160.    
  161. def add(u, v):
  162.   revert(u)
  163.   link(u, v)
  164.  
  165. def rem(u, v):
  166.   revert(v)
  167.   cut(u, v)
  168.  
  169. def main():
  170.   v = [Node() for i in range(10)]
  171.   link(v[1], v[0])
  172.   link(v[2], v[1])
  173.   link(v[3], v[2])
  174.   link(v[4], v[2])
  175.   revert(v[1])
  176.   print [depth(v[i]) for i in range(5)]
  177.  
  178. if __name__ == "__main__":
  179.   main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top