class TreeHandler::Tree

Attributes

data[RW]
root[RW]

Public Class Methods

new(array) click to toggle source
# File lib/tree_handler.rb, line 8
def initialize(array)
  @data = array.uniq
  @root = build_tree
end

Public Instance Methods

balanced?(root = @root) click to toggle source
# File lib/tree_handler.rb, line 136
def balanced?(root = @root)
  left_height = depth(root.left_child)
  right_height = depth(root.right_child)
  (-1..1).include?(left_height - right_height)
end
build_tree(array = @data.dup) click to toggle source
# File lib/tree_handler.rb, line 13
def build_tree(array = @data.dup)
  root = Node.new(array.shift)
  array.each do |value|
    node = Node.new(value)
    compare(root, node)
  end
  root
end
delete(value, parent_pointer = @root) click to toggle source
# File lib/tree_handler.rb, line 32
def delete(value, parent_pointer = @root)
  @data.delete(value)
  node = find(value)
  return nil if node.nil?

  unless node == @root
    parent = find_parent(value)
    parent_pointer =
      value < parent.value ? parent.left_child : parent.right_child
  end

  if node.left_child.nil?
    return parent_pointer = node.right_child
  elsif node.right_child.nil?
    return parent_pointer = node.left_child
  else
    parent_pointer = node.left_child
    compare(parent_pointer, node.right_child)
  end
end
depth(node) click to toggle source
# File lib/tree_handler.rb, line 132
def depth(node)
  node.nil? ? 0 : level_order([node]).size
end
find(value, node = @root) click to toggle source
# File lib/tree_handler.rb, line 53
def find(value, node = @root)
  if value == node.value
    return node
  elsif value < node.value
    return nil if node.left_child.nil?
    find(value, node.left_child)
  elsif value > node.value
    return nil if node.right_child.nil?
    find(value, node.right_child)
  end
end
find_parent(value) click to toggle source
# File lib/tree_handler.rb, line 65
def find_parent(value)
  value == @root.value ? nil : find_parent_rec(value)
end
find_parent_rec(value, node = @root) click to toggle source
# File lib/tree_handler.rb, line 69
def find_parent_rec(value, node = @root)
  value_left_child = node.left_child.nil? ? nil : node.left_child.value
  value_right_child = node.right_child.nil? ? nil : node.right_child.value

  if value == value_left_child || value == value_right_child
    return node
  elsif value < node.value
    value_left_child.nil? ? nil : find_parent_rec(value, node.left_child)
  elsif value > node.value
    value_right_child.nil? ? nil : find_parent_rec(value, node.right_child)
  end
end
insert(value) click to toggle source
# File lib/tree_handler.rb, line 22
def insert(value)
  unless @data.include? value
    @data.push(value)
    node = Node.new(value)
    compare(root, node)
  else
    raise "The same value can't be inserted twice"
  end
end
level_order(queue = [@root], no_block = []) { |map(&:value)| ... } click to toggle source
# File lib/tree_handler.rb, line 82
def level_order(queue = [@root], no_block = [])
  until queue.empty?
    if block_given?
      yield(queue.map(&:value))
    else
      no_block.push(queue.map(&:value))
    end
    (0...queue.count).each do
      next_node = queue.shift
      queue.push(next_node.left_child) unless next_node.left_child.nil?
      queue.push(next_node.right_child) unless next_node.right_child.nil?
    end
  end
  no_block
end
level_order_rec(queue = [@root], no_block = [], &block) click to toggle source
# File lib/tree_handler.rb, line 98
def level_order_rec(queue = [@root], no_block = [], &block)
  queue_child = []
  if block_given?
    block.call(queue.map(&:value))
  else
    no_block.push(queue.map(&:value))
  end

  queue.each do |node|
    queue_child.push(node.left_child) unless node.left_child.nil?
    queue_child.push(node.right_child) unless node.right_child.nil?
  end
  level_order_rec(queue_child, no_block, &block) unless queue_child.empty?
  no_block
end
rebalance!() click to toggle source
# File lib/tree_handler.rb, line 142
def rebalance!
  result = rebalance_ordering(@data.dup.sort)
  @root = build_tree(result)
end
rebalance_ordering(tree, result = []) click to toggle source
# File lib/tree_handler.rb, line 147
def rebalance_ordering(tree, result = [])
  return if tree.size == 0
  middle = tree.size / 2
  result.push tree.slice!(middle)
  rebalance_ordering(tree[0...middle], result)
  rebalance_ordering(tree[(middle)..-1], result)
  result
end