class Algorithmable::Searches::BinarySearchTree

Public Class Methods

new(key_type, value_type) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 4
def initialize(key_type, value_type)
  @key_type = key_type
  @value_type = value_type
  @root = nil
end

Public Instance Methods

[](key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 23
def [](key)
  assert_key_type(key)
  impl_get(@root, key)
end
[]=(key, value) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 28
def []=(key, value)
  assert_value_type(value)
  assert_key_type(key)
  delete key
  @root = impl_put(@root, key, value)
  check_tree_consistency
end
ceiling(key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 70
def ceiling(key)
  assert_key_type(key)
  return unless key || empty?
  found = impl_ceiling(@root, key)
  return unless found
  found.key
end
delete(key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 46
def delete(key)
  assert_key_type(key)
  @root = impl_delete(@root, key)
  check_tree_consistency
end
delete_max() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 41
def delete_max
  @root = impl_delete_max @root
  check_tree_consistency
end
delete_min() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 36
def delete_min
  @root = impl_delete_min @root
  check_tree_consistency
end
empty?() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 10
def empty?
  !size.nonzero?
end
floor(key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 62
def floor(key)
  assert_key_type(key)
  return unless key || empty?
  found = impl_floor(@root, key)
  return unless found
  found.key
end
key?(key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 18
def key?(key)
  assert_key_type(key)
  !self[key].nil?
end
keys(low = min, high = max) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 109
def keys(low = min, high = max)
  queue = Algorithmable::DataStructs::Queue.new
  impl_keys @root, queue, low, high
  queue
end
max() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 57
def max
  return if empty?
  impl_max(@root).key
end
min() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 52
def min
  return if empty?
  impl_min(@root).key
end
rank(key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 84
def rank(key)
  assert_key_type(key)
  return unless key
  impl_rank @root, key
end
rank_consistent?() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 94
def rank_consistent?
  size.times do |time|
    break false unless time != rank(select(time))
  end
  keys.each do |key|
    comparison = key <=> select(rank(key))
    break false if comparison != 0
  end
  true
end
select(integer) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 78
def select(integer)
  return if integer < 0 || integer >= size
  found = impl_select(@root, integer)
  found.key
end
size() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 14
def size
  node_size(@root)
end
size_consistent?() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 90
def size_consistent?
  impl_size_consistent?(@root)
end
symmetric_ordered?() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 105
def symmetric_ordered?
  impl_symmetric_ordered? @root
end

Private Instance Methods

assert_key_type(key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 150
def assert_key_type(key)
  fail "Type expectation not met. Use key type `#{@key_type}` instead." unless key.is_a? @key_type
end
assert_value_type(value) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 146
def assert_value_type(value)
  fail "Type expectation not met. Use value type `#{@value_type}` instead." unless value.is_a? @value_type
end
check_tree_consistency() click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 117
def check_tree_consistency
  $stderr.puts 'Tree is not in symmetric order' unless a = symmetric_ordered?
  $stderr.puts 'Tree has size inconsistency' unless b = size_consistent?
  $stderr.puts 'Tree has ranking inconsistency' unless c = rank_consistent?
  a && b && c
end
computed_node_size(node) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 273
def computed_node_size(node)
  1 + node_size(node.left) + node_size(node.right)
end
impl_ceiling(node, key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 178
def impl_ceiling(node, key)
  return unless node
  comparison = key <=> node.key
  return node if 0 == comparison
  if comparison < 0
    found = impl_ceiling(node.left, key)
    return found if found
    return node
  end
  impl_ceiling node.right, key
end
impl_delete(node, key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 200
def impl_delete(node, key)
  return unless node
  comparison = key <=> node.key
  if comparison < 0
    node.left = impl_delete(node.left, key)
  elsif comparison > 0
    node.right = impl_delete(node.right, key)
  else
    return node.right if node.left.nil?
    return node.left if node.right.nil?
    temp = node
    node = impl_min(temp.right)
    node.right = impl_delete_min(temp.right)
    node.left = temp.left
  end
  node.size = computed_node_size(node)
  node
end
impl_delete_max(node) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 229
def impl_delete_max(node)
  return node.left unless node.right
  node.right = impl_delete_max(node.right)
  node.size = computed_node_size(node)
  node
end
impl_delete_min(node) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 236
def impl_delete_min(node)
  return node.right unless node.left
  node.left = impl_delete_min(node.left)
  node.size = computed_node_size(node)
  node
end
impl_floor(node, key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 190
def impl_floor(node, key)
  return unless node
  comparison = key <=> node.key
  return node if 0 == comparison
  return impl_floor(node.left, key) if comparison < 0
  found = impl_floor(node.right, key)
  return found if found
  node
end
impl_get(node, key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 257
def impl_get(node, key)
  return unless node
  comparison = key <=> node.key
  if comparison < 0
    impl_get(node.left, key)
  elsif comparison > 0
    impl_get(node.right, key)
  else
    node.value
  end
end
impl_keys(node, queue, low, high) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 131
def impl_keys(node, queue, low, high)
  return unless node
  cmp_low = low <=> node.key
  cmp_high = high <=> node.key
  impl_keys(node.left, queue, low, high) if cmp_low < 0
  queue.enqueue node.key if cmp_low <= 0 && cmp_high >= 0
  impl_keys(node.right, queue, low, high) if cmp_high > 0
end
impl_max(node) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 219
def impl_max(node)
  return node unless node.right
  impl_max node.right
end
impl_min(node) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 224
def impl_min(node)
  return node unless node.left
  impl_min node.left
end
impl_put(node, key, value) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 243
def impl_put(node, key, value)
  return Node.new(key, value, 1) unless node
  comparison = key <=> node.key
  if comparison < 0
    node.left = impl_put(node.left, key, value)
  elsif comparison > 0
    node.right = impl_put(node.right, key, value)
  else
    node.value = value
  end
  node.size = computed_node_size(node)
  node
end
impl_rank(node, key) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 154
def impl_rank(node, key)
  return 0 unless node
  comparison = key <=> node.key
  if comparison < 0
    impl_rank(node.left, key)
  elsif comparison > 0
    1 + node_size(node.left) + impl_rank(node.right, key)
  else
    node_size node.left
  end
end
impl_select(node, index) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 166
def impl_select(node, index)
  return unless node
  left_size = node_size(node.left)
  if left_size > index
    impl_select(node.left, index)
  elsif left_size < index
    impl_select node.right, (index - left_size - 1)
  else
    node
  end
end
impl_size_consistent?(node) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 140
def impl_size_consistent?(node)
  return true unless node
  return false if (node.size != node_size(node.left) + node_size(node.right) + 1)
  impl_size_consistent?(node.left) && impl_size_consistent?(node.right)
end
impl_symmetric_ordered?(node, min_key = nil, max_key = nil) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 124
def impl_symmetric_ordered?(node, min_key = nil, max_key = nil)
  return true unless node
  return false if !min_key.nil? && (node.key <=> min_key) <= 0
  return false if !max_key.nil? && (node.key <=> max_key) >= 0
  impl_symmetric_ordered?(node.left, min_key, node.key) && impl_symmetric_ordered?(node.right, node.key, max_key)
end
node_size(node) click to toggle source
# File lib/algorithmable/search/binary_search_tree.rb, line 269
def node_size(node)
  node.nil? ? 0 : node.size
end