class AVLTree
Attributes
height[RW]
left[RW]
right[RW]
value[RW]
Public Class Methods
new(&block)
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 5 def initialize(&block) empty! end
Public Instance Methods
ancestors(node)
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 41 def ancestors(node) node.empty? ? [] : case [@value, @value.object_id] <=> [node.value, node.value.object_id] when +1 then [*@left.ancestors(node), self] when 0 then [] when -1 then [*@right.ancestors(node), self] end end
balance()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 25 def balance empty? ? 0 : @left.height - @right.height end
delete(value)
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 94 def delete(value) case [@value, @value.object_id] <=> [value, value.object_id] when +1 then @left.delete value when 0 @value.tap do case when leaf? then empty! when @left.empty? node = @right.first_node @value = node.value node.replace_with node.right ancestors(node).each(&:rebalance) unless node.empty? else node = @left.last_node @value = node.value node.replace_with node.left ancestors(node).each(&:rebalance) unless node.empty? end end when -1 then @right.delete value end.tap { rebalance } unless empty? end
each(&block)
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 121 def each(&block) unless empty? @left.each &block block.call @value @right.each &block end end
empty!()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 13 def empty! @value, @left, @right, @height = nil, nil, nil, 0 end
empty?()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 9 def empty? @value.nil? end
first_node()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 33 def first_node empty? || @left.empty? ? self : @left.first_node end
insert(value)
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 75 def insert(value) if empty? @value, @left, @right = value, AVLTree.new, AVLTree.new else case [@value, @value.object_id] <=> [value, value.object_id] when +1 then @left.insert value when 0 then @value = value when -1 then @right.insert value end end rebalance end
Also aliased as: <<
last_node()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 37 def last_node empty? || @right.empty? ? self : @right.last_node end
leaf?()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 17 def leaf? [@left, @right].all?(&:empty?) end
merge(values)
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 89 def merge(values) values.each { |value| insert value } self end
pop()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 117 def pop delete first_node.value unless empty? end
rebalance()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 63 def rebalance update_height case balance when +2 @left.rotate_left if @left.balance == -1 rotate_right when -2 @right.rotate_right if @right.balance == 1 rotate_left end unless empty? end
replace_with(node)
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 21 def replace_with(node) @value, @left, @right, @height = node.value, node.left, node.right, node.height end
rotate_left()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 49 def rotate_left a, b, c, v, @value = @left, @right.left, @right.right, @value, @right.value @left = @right @left.value, @left.left, @left.right, @right = v, a, b, c [@left, self].each(&:update_height) end
rotate_right()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 56 def rotate_right a, b, c, v, @value = @left.left, @left.right, @right, @value, @left.value @right = @left @left.value, @left, @right.left, @right.right = v, a, b, c [@right, self].each(&:update_height) end
update_height()
click to toggle source
# File lib/nswtopo/avl_tree.rb, line 29 def update_height @height = empty? ? 0 : [@left, @right].map(&:height).max + 1 end