class BinarySearchTree

Public Class Methods

new() click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 5
def initialize
  @head = nil
end

Public Instance Methods

delete(value) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 29
def delete(value)
  delete_node(value, node=@head)
end

include?(value, node=@head) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 25
def include?(value, node=@head)
  !!search(value, node)
end

insert(value, node=@head) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 33
def insert(value, node=@head)
  if node.value < value
    insert_right(value, node)
  elsif node.value > value
    insert_left(value, node)
  else
    return false
  end
end

search(value, node=@head) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 13
def search(value, node=@head)
  if value == node.value
    return node.value
  elsif value < node.value
    search(value, node.left) unless node.left.nil?
  elsif value > node.value
    search(value, node.right) unless node.right.nil?
  else
    return nil
  end
end

set_head(value) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 9
def set_head(value)
  @head = Node.new({value: value, left: nil, right: nil})
end

Private Instance Methods

change_paretn(node) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 67
def change_paretn(node)
  node.value = successor_value(node.right)
  node.right = update(node.right)
  node
end

delete_node(value, node) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 45
def delete_node(value, node)
  if value == node
    remove(value)
  elsif node < value
    delete_node(value, node.left)
  else
    delete_node(value, node.right)
  end
end

insert_left(value, node) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 87
def insert_left(value, node)
  if node.left
    insert(value, node.left)
  else
    node.left = Node.new({value: value, left: nil, right: nil})
  end
end

insert_right(value, node) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 95
def insert_right(value, node)
  if node.right
    insert(value, node.right)
  else
    node.right = Node.new({value: value, left: nil, right: nil})
  end
end

remove(node) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 55
def remove(node)
  if node.left.nil? && node.right.nil?
    node = nil
  elsif !node.left.nil? && node.right.nil?
    node = node.left
  elsif node.left.nil? && !node.right.nil?
    node = node.right
  else
    node = change_parant(node)
  end
end

successor_value(node) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 73
def successor_value(node)
  unless node.left.nil?
    successor_value(node.left)
  end
  node.value
end

update(node) click to toggle source

# File lib/honey_mushroom/binary_search_tree.rb, line 80
def update(node)
  unless node.left.nil?
    node.left = update(node)
  end
  node.right
end