class BinaryTree
Binary Search Tree data structure Worst-Case Space Complexity: O(n)
Attributes
root[RW]
Public Class Methods
new(data_set=[], root_val=nil)
click to toggle source
# File lib/algorithm_selector.rb, line 501 def initialize(data_set=[], root_val=nil) @root = BSTNode.new(root_val) data_set.each { |i| insert(i) } end
Public Instance Methods
insert(val)
click to toggle source
Insertion, Worst-Case Time Complexity: O(n)
# File lib/algorithm_selector.rb, line 523 def insert(val) new_node = BSTNode.new(val) @root = new_node and return unless @root.val insert_to_tree(@root, new_node) end
insert_to_tree(tree_node, new_node)
click to toggle source
# File lib/algorithm_selector.rb, line 529 def insert_to_tree(tree_node, new_node) tree_node = new_node and return if tree_node.nil? return tree_node if tree_node.val == new_node.val if new_node.val > tree_node.val insert_to_tree(tree_node.right, new_node) unless tree_node.right.nil? tree_node.right = new_node else insert_to_tree(tree_node.left, new_node) unless tree_node.left.nil? tree_node.left = new_node end end
search(target)
click to toggle source
Search, Worst-Case Time Complexity: O(n)
# File lib/algorithm_selector.rb, line 507 def search(target) return nil if @root.nil? return search_in_tree(@root, target) end
search_in_tree(tree_node, target)
click to toggle source
# File lib/algorithm_selector.rb, line 512 def search_in_tree(tree_node, target) return nil if tree_node.nil? return tree_node.val if target == tree_node.val if target < tree_node.val search_in_tree(tree_node.left, target) else search_in_tree(tree_node.right, target) end end