red-black-tree.rb

class RedBlackTree
  RED = :red
  BLACK = :balck
  Node = Struct.new(:value, :parent, :left, :right, :color, keyword_init: true)
  NUL = Node.new(value: nil, parent: nil, left: nil, right: nil, color: BLACK)

  def initialize
    @tree = []
    @root = NUL
  end

  def min
    node = @root

    while node.left != NUL
      node = node.left
    end

    node
  end

  def max
    node = @root

    while node.right != NUL
      node = node.right
    end

    node
  end

  def insert(value)
    node = build_node(value)
    y = NUL
    x = @root

    while x != NUL
      y = x

      if node.value < x.value
        x = x.left
      else
        x = x.right
      end
    end

    node.parent = y

    if y == NUL
      @root = node
    elsif node.value < y.value
      y.left = node
    else
      y.right = node
    end

    node.color = RED

    insert_fixup(node)
  end

  def delete(value)
    z = find(value)

    return if z == NUL

    x = NUL
    y = z
    y_original_color = y.color

    if z.left == NUL
      x = z.right
      transparent(z, z.right)
    elsif z.right == NUL
      x = z.left
      transparent(z, z.left)
    else
      y = tree_minimum(z.right)
      y_original_color = y.color
      x = y.right

      if y.parent == z
        x.parent = y
      else
        transparent(y, y.right)
        y.right = z.right
        y.right.parent = y
      end

      transparent(z, y)
      y.left = z.left
      y.left.parent = y
      y.color = z.color
    end

    if y_original_color == BLACK
      delete_fixup(x)
    end
  end

  def walk(node = @root)
    if node.left != NUL
      walk(node.left)
    end

    puts node.value

    if node.right != NUL
      walk(node.right)
    end
  end

  private

  def find(value)
    node = @root

    while node != NUL && node.value != value
      if value < node.value
        node = node.left
      else
        node = node.right
      end
    end

    node
  end

  def delete_fixup(x)
    while x != @root && x.color == BLACK
      if x == x.parent.left
        w = x.parent.right

        if w.color == RED
          w.color = BLACK
          x.parent.color = RED
          left_rotate(x.parent)
          w = x.parent.right
        end

        if w.left.color == BLACK && w.right.color == BLACK
          w.color = RED
          x = x.parent
        elsif w.right.color == BLACK
          w.left.color = BLACK
          w.color = RED
          right_rotate(w)
          w = x.parent.right
        else
          w.color = x.parent.color
          x.parent.color = BLACK
          w.right.color = BLACK
          left_rotate(x.parent)
          x = @root
        end
      else
        w = x.parent.left

        if w.color == RED
          w.color = BLACK
          x.parent.color = RED
          right_rotate(x.parent)
          w = x.parent.left
        end

        if w.right.color == BLACK && w.left.color == BLACK
          w.color = RED
          x = x.parent
        elsif w.left.color == BLACK
          w.right.color = BLACK
          w.color = RED
          left_rotate(w)
          w = x.parent.left
        else
          w.color = x.parent.color
          x.parent.color = BLACK
          w.left.color = BLACK
          right_rotate(x.parent)
          x = @root
        end
      end
    end

    x.color = BLACK
  end

  def tree_minimum(node)
    while node.left != NUL
      node = node.left
    end

    node
  end

  def build_node(value)
    Node.new(value: value, parent: nil, left: NUL, right: NUL, color: BLACK)
  end

  def transparent(u, v)
    if u.parent == NUL
      @root = v
    elsif u == u.parent.left
      u.parent.left = v
    else
      u.parent.right = v
    end

    v.parent = u.parent
  end

  def insert_fixup(node)
    while node.parent.color == RED
      if node.parent == node.parent.parent.left
        y = node.parent.parent.right

        if y.color == RED
          node.parent.color = BLACK
          y.color = BLACK
          node.parent.parent.color = RED
          node = node.parent.parent
        elsif node == node.parent.right
          node = node.parent
          left_rotate(node)
        else
          node.parent.color = BLACK
          node.parent.parent.color = RED
          right_rotate(node.parent.parent)
        end
      else
        y = node.parent.parent.left

        if y.color == RED
          node.parent.color = BLACK
          y.color = BLACK
          node.parent.parent.color = RED
          node = node.parent.parent
        elsif node == node.parent.left
          node = node.parent
          right_rotate(node)
        else
          node.parent.color = BLACK
          node.parent.parent.color = RED
          left_rotate(node.parent.parent)
        end
      end
    end

    @root.color = BLACK
  end

  def left_rotate(node)
    y = node.right
    node.right = y.left

    if y.left != NUL
      y.left.parent = node
    end

    y.parent = node.parent

    if node.parent == NUL
      @root = y
    elsif node.parent.left == node
      node.parent.left = y
    else
      node.parent.right = y
    end

    y.left = node
    node.parent = y
  end

  def right_rotate(node)
    y = node.left
    node.left = y.right

    if y.right != NUL
      y.right.parent = node
    end

    y.parent = node.parent

    if node.parent == NUL
      @root = y
    elsif node.parent.right == node
      node.parent.right = y
    else
      node.parent.left = y
    end

    y.right = node
    node.parent = y
  end
end