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