Class: Algorithmable::DataStructs::Tree::BinarySearch

Inherits:
Object
  • Object
show all
Includes:
Algorithmable::DataStructs, Enumerable
Defined in:
lib/algorithmable/data_structs/tree/binary_search.rb

Instance Method Summary collapse

Methods included from Algorithmable::DataStructs

#new_bag, #new_deque_queue, #new_fifo_queue, #new_lifo_queue, #new_max_priority_queue, #new_min_priority_queue, #new_ordered_symbol_table, #new_priority_queue

Methods included from Algorithmable::DataStructs::Tree

#new_ordered_binary_tree

Methods included from LinkedList

#new_doubly_linked_list, #new_singly_linked_list

Constructor Details

#initialize(collection = []) ⇒ BinarySearch

Returns a new instance of BinarySearch.



8
9
10
11
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 8

def initialize(collection = [])
  @root = nil
  collection.each { |item| put item }
end

Instance Method Details

#balanced?(diff = 1) ⇒ Boolean

Returns:

  • (Boolean) 


102
103
104
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 102

def balanced?(diff = 1)
  (max_depth - min_depth) <= diff
end

#each(&block) ⇒ Object 



45
46
47
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 45

def each(&block)
  each_with_dfs(&block)
end

#each_with_bfs(&block) ⇒ Object 



54
55
56
57
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 54

def each_with_bfs(&block)
  tmp = collect_nodes_with_bfs(@root).to_a
  block_given? ? tmp.each(&block) : tmp
end

#each_with_dfs(&block) ⇒ Object 



49
50
51
52
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 49

def each_with_dfs(&block)
  tmp = collect_nodes_with_dfs(@root).to_a
  block_given? ? tmp.each(&block) : tmp
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


27
28
29
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 27

def empty?
  0 == size
end

#flip! ⇒ Object 



85
86
87
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 85

def flip!
  @root = flip_bang_imp! @root, 0
end

#flip_bang_imp!(n, count) ⇒ Object 



89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 89

def flip_bang_imp!(n, count)
  return unless n
  return n unless n.left && n.right
  new_head = flip_bang_imp! n.left, count + 1
  n.left.left = n.right
  n.left.right = n
  if count == 0
    n.left = nil
    n.right = nil
  end
  new_head
end

#max ⇒ Object 



40
41
42
43
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 40

def max
  return if empty?
  max_impl(@root).item
end

#max_depth ⇒ Object Also known as: height 



13
14
15
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 13

def max_depth
  max_height_of @root
end

#min ⇒ Object 



35
36
37
38
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 35

def min
  return if empty?
  min_impl(@root).item
end

#min_depth ⇒ Object 



19
20
21
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 19

def min_depth
  min_height_of @root
end

#put(object) ⇒ Object 



31
32
33
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 31

def put(object)
  @root = put_impl @root, object
end

#reverse! ⇒ Object 



81
82
83
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 81

def reverse!
  @root = reverse_bang_impl @root
end

#size ⇒ Object 



23
24
25
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 23

def size
  size_of @root
end

#to_print ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/algorithmable/data_structs/tree/binary_search.rb', line 59

def to_print
  return if empty?
  queue = new_fifo_queue
  level = 0
  next_level = 1
  out = []
  queue.enqueue @root
  until queue.empty?
    level += 1
    node = queue.dequeue
    out << node.item << ' '
    queue.enqueue node.left if node.left
    queue.enqueue node.right if node.right

    if level == next_level
      next_level += queue.size
      out << "\n"
    end
  end
  out.join
end