SHARE
TWEET

Untitled

a guest Nov 4th, 2015 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def rot_left(p, li):
  2.     ri = 1 - li
  3.     l = p.lr[li]
  4.     r = p.lr[ri]
  5.     new_p = p.Clone()
  6.     new_r = r.Clone()
  7.  
  8.     new_p.lr[li] = l
  9.     new_p.lr[ri] = r.lr[li]
  10.  
  11.     new_r.lr[li] = new_p
  12.     new_r.lr[ri] = r.lr[ri]
  13.  
  14.     return new_p, new_r
  15.  
  16. def rot_right(p, li):
  17.     return rot_left(p, 1 - li)
  18.  
  19. def is_black(n):
  20.     return n == None or n.color == 'BLACK'
  21.  
  22. def is_red(n):
  23.     return not is_black(n)
  24.  
  25.  
  26. def remove_black_node_with_one_black_child(n, parents):
  27.     # cases numbered according to 2015/Oct/03 wiki RB-tree article
  28.     # https://en.wikipedia.org/w/index.php?title=Red%E2%80%93black_tree&oldid=686983620#Removal
  29.     while 1:
  30.         if not parents:
  31.             return n
  32.         p, li = parents.pop()
  33.         ri = 1 - li
  34.         s = p.lr[ri] # sibling
  35.         sl = s.lr[li]
  36.         sr = s.lr[ri]
  37.         if s.color == 'RED':
  38.             # wiki case 2
  39.             new_p, new_s = rot_left(p, li)
  40.             new_s.color = 'BLACK'
  41.             new_p.lr[li] = n
  42.             new_p.color = 'RED'
  43.             parents.append((new_s, li))
  44.             parents.append((new_p, li))
  45.         elif p.color == s.color and is_black(sl) and is_black(sr):
  46.             # wiki case 3
  47.             new_s = s.Clone()
  48.             new_s.color = 'RED'
  49.             new_p = clone_and_replace(li, n, new_s, p)
  50.             n = new_p
  51.         elif p.color == 'RED' and is_black(s) and is_black(sl) and is_black(sr):
  52.             # wiki case 4
  53.             new_s = s.Clone()
  54.             new_s.color = 'RED'
  55.             new_p = clone_and_replace(li, n, new_s, p, 'BLACK')
  56.             return new_p
  57.         else:
  58.             assert s.color == 'BLACK'
  59.             if is_red(sl) and is_black(sr):
  60.                 assert sl and is_black(sl.lr[li]) and is_black(sl.lr[ri])
  61.                 # wiki case 5
  62.                 new_s, new_sl = rot_right(s, li)
  63.                 assert is_black(new_sl.lr[li])
  64.                 new_p = clone_and_replace(li, p.lr[li], new_sl, p)
  65.                 new_s.color = 'RED'
  66.                 new_sl.color = 'BLACK'
  67.                 assert is_black(new_sl.lr[li])
  68.                 p, s = new_p, new_sl
  69.                 sl, sr = s.lr[li], s.lr[ri]
  70.             assert is_red(sr)
  71.             # wiki case 6
  72.             new_p, new_s = rot_left(p, li)
  73.             new_p.color, new_s.color = new_s.color, new_p.color
  74.             new_sr = sr.Clone()
  75.             new_sr.color = 'BLACK'
  76.             new_s.lr[ri] = new_sr
  77.             new_p.lr[li] = n
  78.             return new_s
  79.     return n
  80.  
  81. def recreate_path_to_new_node(parents, node):
  82.     assert node == None or isinstance(node, TreeNode)
  83.     result = node
  84.     while parents:
  85.         p, ichild = parents.pop()
  86.         result = clone_and_replace(ichild, result, p.lr[1-ichild], p)
  87.     return result
  88.  
  89.  
  90. def remove_node(node, parents):
  91.     if node.lr[0] and node.lr[1]:
  92.         new_n = node.Clone()
  93.         parents.append((new_n, 0))
  94.         n = new_n.lr[0]
  95.         while n.lr[1]:
  96.             parents.append((n, 1))
  97.             n = n.lr[1]
  98.         new_n.key = n.key
  99.         new_n.value = n.value
  100.         node_to_remove = n
  101.         ichild = 0
  102.     else:
  103.         node_to_remove = node
  104.         ichild = int(node.lr[0] == None)
  105.  
  106.     child = node_to_remove.lr[ichild]
  107.     # simple cases with red node - just delete/recolor red node
  108.     if node_to_remove.color == 'RED':
  109.         return recreate_path_to_new_node(parents, child)
  110.     elif node_to_remove.color == 'BLACK':
  111.         if child and child.color == 'RED':
  112.             new_child = child.Clone()
  113.             new_child.color = 'BLACK'
  114.             return recreate_path_to_new_node(parents, new_child)
  115.         else:
  116.             remove_done_node = remove_black_node_with_one_black_child(child, parents)
  117.             return recreate_path_to_new_node(parents, remove_done_node)
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