binary tree set

binary-tree-set.rb

class BinaryTreeSet
  class Node
    attr_accessor :value
    attr_accessor :parent
    attr_accessor :right
    attr_accessor :left

    def initialize(value = nil)
      @value = value
    end

    def inspect
      @value.inspect
    end
  end

  attr_reader :root

  def initialize
    @root = nil
  end

  def insert(value)
    x = @root
    y = nil
    while !x.nil?
      y = x
      if x.value > value
        x = x.left
      elsif x.value < value
        x = x.right
      else
        return self
      end
    end
    node = Node.new(value)
    if y.nil?
      @root = node
    else
      if node.value < y.value
        y.left = node
        node.parent = y
      else
        y.right = node
        node.parent = y
      end
    end
    self
  end

  def find(value)
    node = @root
    while !node.nil? && value != node.value
      if value < node.value
        node = node.left
      else
        node = node.right
      end
    end
    return node
  end

  def delete(value)
    node = find(value)
    return if node.nil?
    if node.left.nil? || node.right.nil?
      y = node
    else
      y = successor(node)
    end
    if !y.left.nil?
      x = y.left
    else
      x = y.right
    end

    x.parent = y.parent if !x.nil?

    if y.parent.nil?
      @root = x
    else
      if y == y.parent.left
        y.parent.left = x
      else
        y.parent.right = x
      end
    end

    if y != node
      node = y.dup
    end

    return y
  end

  def min
    minimum @root
  end

  def max
    maximum @root
  end

  def succ(value)
    node = find(value)
    successor(node)
  end

  def pred(value)
    node = find(value)
    predecessor(node)
  end

  def each(&block)
    inorder(@root, &block)
  end

  private

  def inorder(node, &block)
    if !node.nil?
      inorder(node.left, &block)
      yield node.value
      inorder(node.right, &block)
    end
    self
  end

  def successor(node)
    return if node.nil?
    if !node.right.nil?
      return minimum(node.right)
    end
    p = node.parent
    while !p.nil? && node == p.right
      node = p
      p = p.parent
    end
    return p
  end
  
  def predecessor(node)
    return if node.nil?
    if !node.left.nil?
      return maximum(node.left)
    end
    p = node.parent
    while !p.nil? && node == p.left
      node = p
      p = p.parent
    end
    return p
  end

  def minimum(node)
    x = node
    while !x.left.nil?
      x = x.left
    end
    return x
  end

  def maximum(node)
    x = node
    while !x.right.nil?
      x = x.right
    end
    return x
  end
end