Class: BinarySearchTree

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(logger = nil) ⇒ BinarySearchTree

Returns a new instance of BinarySearchTree.



36
37
38
39
 
# File 'lib/binary_search_tree.rb', line 36

def initialize logger=nil
  @logger = logger
  clear
end

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.



34
35
36
 
# File 'lib/binary_search_tree.rb', line 34

def root
  @root
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



34
35
36
 
# File 'lib/binary_search_tree.rb', line 34

def size
  @size
end

Instance Method Details

#==(other_bst) ⇒ Object 



87
88
89
 
# File 'lib/binary_search_tree.rb', line 87

def == other_bst
  compare @root, other_bst.root
end

#clear ⇒ Object 



41
42
43
44
 
# File 'lib/binary_search_tree.rb', line 41

def clear
  @root = nil
  @size = 0
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


46
47
48
 
# File 'lib/binary_search_tree.rb', line 46

def empty?
  @root.nil?
end

#find(key) ⇒ Object 



50
51
52
53
54
55
 
# File 'lib/binary_search_tree.rb', line 50

def find key
  @num_comparisons = 0
  node = locate key, @root
  @logger.debug "find operation completed in #{@num_comparisons} lookups..." if @logger.present?
  node
end

#find_value(value) ⇒ Object 



57
58
59
 
# File 'lib/binary_search_tree.rb', line 57

def find_value value
  find_value_ex @root, value
end

#insert(element, value) ⇒ Object 



69
70
71
 
# File 'lib/binary_search_tree.rb', line 69

def insert element, value
  put element, value, @root, nil
end

#max ⇒ Object 



65
66
67
 
# File 'lib/binary_search_tree.rb', line 65

def max
  @max ||= locate_max @root
end

#min ⇒ Object 



61
62
63
 
# File 'lib/binary_search_tree.rb', line 61

def min
  @min ||= locate_min @root
end

#nodes ⇒ Object 



81
82
83
84
85
 
# File 'lib/binary_search_tree.rb', line 81

def nodes
  @nodes = []
  serialize_nodes @root
  @nodes
end

#remove(node_or_key) ⇒ Object 



73
74
75
 
# File 'lib/binary_search_tree.rb', line 73

def remove node_or_key
  delete node_or_key
end

#remove_min ⇒ Object 



77
78
79
 
# File 'lib/binary_search_tree.rb', line 77

def remove_min
  delete min
end