Class: BinarySearchTree

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(logger = nil) ⇒ BinarySearchTree

Returns a new instance of BinarySearchTree.



12
13
14
15
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 12

def initialize logger=nil
  @logger = logger
  clear
end

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.



2
3
4
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 2

def root
  @root
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



2
3
4
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 2

def size
  @size
end

Instance Method Details

#==(other_bst) ⇒ Object 



63
64
65
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 63

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

#balanced? ⇒ Boolean

Returns:

  • (Boolean) 


4
5
6
7
8
9
10
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 4

def balanced?
  if -1 == compute_and_check_height(@root)
    false
  else
    true
  end
end

#clear ⇒ Object 



17
18
19
20
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 17

def clear
  @root = nil
  @size = 0
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


22
23
24
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 22

def empty?
  @root.nil?
end

#find(key) ⇒ Object 



26
27
28
29
30
31
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 26

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

#find_value(value) ⇒ Object 



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

def find_value value
  find_value_ex @root, value
end

#insert(element, value) ⇒ Object 



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

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

#max ⇒ Object 



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

def max
  @max ||= locate_max @root
end

#min ⇒ Object 



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

def min
  @min ||= locate_min @root
end

#nodes ⇒ Object 



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

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

#remove(node_or_key) ⇒ Object 



49
50
51
 
# File 'lib/binary_search_tree/binary_search_tree.rb', line 49

def remove node_or_key
  delete node_or_key
end

#remove_min ⇒ Object 



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

def remove_min
  delete min
end