class Algorithmable::DataStructs::Tree::BinarySearch

Public Class Methods

new(collection = []) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 8
def initialize(collection = [])
  @root = nil
  collection.each { |item| put item }
end

Public Instance Methods

balanced?(diff = 1) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 102
def balanced?(diff = 1)
  (max_depth - min_depth) <= diff
end
each(&block) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 45
def each(&block)
  each_with_dfs(&block)
end
each_with_bfs(&block) click to toggle source
# 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) click to toggle source
# 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?() click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 27
def empty?
  0 == size
end
flip!() click to toggle source
# 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) click to toggle source
# 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
height()
Alias for: max_depth
max() click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 40
def max
  return if empty?
  max_impl(@root).item
end
max_depth() click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 13
def max_depth
  max_height_of @root
end
Also aliased as: height
min() click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 35
def min
  return if empty?
  min_impl(@root).item
end
min_depth() click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 19
def min_depth
  min_height_of @root
end
put(object) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 31
def put(object)
  @root = put_impl @root, object
end
reverse!() click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 81
def reverse!
  @root = reverse_bang_impl @root
end
size() click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 23
def size
  size_of @root
end
to_print() click to toggle source
# 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

Private Instance Methods

collect_nodes_with_bfs(root) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 128
def collect_nodes_with_bfs(root)
  queue = new_fifo_queue
  stack = new_lifo_queue
  queue.enqueue root
  until queue.empty?
    node = queue.dequeue
    stack.push node.item
    queue.enqueue node.left if node.left
    queue.enqueue node.right if node.right
  end
  stack
end
collect_nodes_with_dfs(node) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 141
def collect_nodes_with_dfs(node)
  stack = []
  dfs_impl node, stack
  stack
end
dfs_impl(node, stack) click to toggle source

in-order traversal

# File lib/algorithmable/data_structs/tree/binary_search.rb, line 148
def dfs_impl(node, stack)
  dfs_impl node.left, stack if node.left
  stack.push node.item
  dfs_impl node.right, stack if node.right
end
make_node(object, size) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 183
def make_node(object, size)
  Node.new object, size
end
max_height_of(node) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 108
def max_height_of(node)
  return 0 unless node
  1 + [max_height_of(node.left), max_height_of(node.right)].max
end
max_impl(node) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 154
def max_impl(node)
  return node if node.right.nil?
  max_impl(node.right)
end
min_height_of(node) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 113
def min_height_of(node)
  return 0 unless node
  1 + [min_height_of(node.left), min_height_of(node.right)].min
end
min_impl(node) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 159
def min_impl(node)
  return node if node.left.nil?
  min_impl(node.left)
end
put_impl(node, object) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 164
def put_impl(node, object)
  return make_node(object, 1) unless node
  case object <=> node.item
  when -1
    node.left = put_impl(node.left, object)
  when 1
    node.right = put_impl(node.right, object)
  else
    node.item = object
  end
  node.size = 1 + size_of(node.left) + size_of(node.right)
  node
end
reverse_bang_impl(root) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 118
def reverse_bang_impl(root)
  return unless root
  reverse_bang_impl root.left
  reverse_bang_impl root.right
  tmp = root.left
  root.left = root.right
  root.right = tmp
  root
end
size_of(node) click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 178
def size_of(node)
  return 0 if node.nil?
  node.size
end