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_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