Last active
September 25, 2020 11:14
-
-
Save JessyGreben/c0531be777558a45269d to your computer and use it in GitHub Desktop.
Binary Search Tree - Ruby
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
If you add .rb
to the filename it will automatically highlight the syntax
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
Hi, there's a missing
end
in the last method.