Skip to content

Instantly share code, notes, and snippets.

@JessyGreben
Last active September 25, 2020 11:14
  • Star 7 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save JessyGreben/c0531be777558a45269d to your computer and use it in GitHub Desktop.
Binary Search Tree - Ruby
class Node
attr_reader :value
attr_accessor :left, :right
def initialize(value=nil)
@value = value
left = nil;
right = nil;
end
end
#Binary Search Tree
class BinarySearchTree
attr_accessor :root_node
def initialize(root_value=nil)
@root_node = Node.new(root_value)
end
#if you want to create a binary search tree
def create_binary_search_tree(size)
array_of_nums = (0..size).to_a.shuffle
new_tree = BinarySearchTree.new
array_of_nums.each do |num|
new_tree.insert(num)
end
return new_tree
end
def insert(node, value)
if node.value == value
return node
elsif value < node.value
insert(node.left, value)
elsif value > node.value
insert(node.right, value)
else
return node = Node.new(value)
end
end
def search(value, node)
return nil if node.nil?
if value == node.value
return node
elsif value > node.value
search(value, node.right)
else value < node.value
search(value, node.left)
end
end
def delete(value)
node = search(value)
if !node.nil?
remove(node)
end
end
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 = delete_node_with_two_children(node)
end
node
end
def delete_node_with_two_children(node)
min_node = find_min_node(node.right)
replace_value(min_node, node)
remove_min_node(min_node)
end
def find_min_node(node)
if node.left.nil?
min_node = node
return min_node
else
find_min(node.left)
end
end
def replace_value(min_node, node)
node.value = min_node.value
end
def remove_min_node(min_node)
min_node = nil
end
def BST_is_valid?(node, min=-1.0/0.0, max=1.0/0.0)
until node.left.nil? && node.right.nil?
if min > node.value || max < node.value
return false
else
BST_is_valid?(node.left, min, node.value)
BST_is_valid?(node.right, node.value, max)
end
return true
end
end
@budu
Copy link

budu commented May 12, 2018

Hi, there's a missing end in the last method.

@agush22
Copy link

agush22 commented Jul 27, 2018

If you add .rb to the filename it will automatically highlight the syntax

@ajit123jain
Copy link

bst = BinarySearchTree.new
bst.create_binary_search_tree(10) While I am doing this it is giving error like this
`insert': wrong number of arguments (given 1, expected 2) (ArgumentError)
can you please update it with some example

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment