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