Class: BinaryTree

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithm_selector.rb

Overview

Binary Search Tree data structure Worst-Case Space Complexity: O(n)

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(data_set = [], root_val = nil) ⇒ BinaryTree

Returns a new instance of BinaryTree.



501
502
503
504
 
# 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

Instance Attribute Details

#root ⇒ Object

Returns the value of attribute root.



499
500
501
 
# File 'lib/algorithm_selector.rb', line 499

def root
  @root
end

Instance Method Details

#insert(val) ⇒ Object

Insertion, Worst-Case Time Complexity: O(n)



523
524
525
526
527
 
# 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) ⇒ Object 



529
530
531
532
533
534
535
536
537
538
539
 
# 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) ⇒ Object

Search, Worst-Case Time Complexity: O(n)



507
508
509
510
 
# 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) ⇒ Object 



512
513
514
515
516
517
518
519
520
 
# 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