rb_delete.py

def replace(self, u, v):
  if u.parent == None:
      self.root = v
  elif u == u.parent.left:
      u.parent.left = v
  else:
      u.parent.right = v
  if v:
      v.parent = u.parent

def delete(self, v):
  node = self.root
  # find the node containing v
  match = None
  while node != None:
      if node.v == v:
          match = node
          break
      if node.v <= v:
          node = node.right
      else:
          node = node.left

  if match == None:
      print("Couldn't find v in the tree")
      return

  rep = match
  rep_original_color = rep.color
  if match.left == None:
      child = match.right
      self.replace(match, match.right)
  elif match.right == None:
      child = match.left
      self.replace(match, match.left)
  else:
      rep = self.minimum(match.right)
      rep_original_color = rep.color
      child = rep.right
      if rep.parent != match:
          self.replace(rep, rep.right)
          rep.right = match.right
          rep.right.parent = rep

      self.replace(match, rep)
      rep.left = match.left
      rep.left.parent = rep
      rep.color = match.color

      while child and child != self.root and rep_original_color == "black" and child.color == "black":
          if child == child.parent.left:
              sibling = child.parent.right
              if sibling.color == "red":
                  # case 3.1
                  sibling.color = "black"
                  child.parent.color = "red"
                  self.left_rotate(child.parent)
                  sibling = child.parent.right

              if sibling.left.color == "black" and sibling.right.color == "black":
                  # case 3.2
                  sibling.color = "red"
                  child = child.parent
              else:
                  if sibling.right.color == "black":
                      # case 3.3
                      sibling.left.color = "black"
                      sibling.color = "red"
                      self.right_rotate(sibling)
                      sibling = child.parent.right

                  # case 3.4
                  sibling.color = child.parent.color
                  child.parent.color = "black"
                  sibling.right.color = "black"
                  self.left_rotate(child.parent)
                  child = self.root
          else:
              sibling = child.parent.left
              if sibling.color == "red":
                  # case 3.1
                  sibling.color = "black"
                  child.parent.color = "red"
                  self.right_rotate(child.parent)
                  sibling = child.parent.left

              if sibling.right.color == "black" and sibling.right.color == "black":
                  # case 3.2
                  sibling.color = "red"
                  child = child.parent
              else:
                  if sibling.left.color == "black":
                      # case 3.3
                      sibling.right.color = "black"
                      sibling.color = "red"
                      self.left_rotate(sibling)
                      sibling = child.parent.left 

                  # case 3.4
                  sibling.color = child.parent.color
                  child.parent.color = "black"
                  sibling.left.color = "black"
                  self.right_rotate(child.parent)
                  child = self.root

        if child: child.color = "black"