class WindingPolygon::AVLTree
Attributes
root[RW]
Public Class Methods
new(array = [])
click to toggle source
# File lib/winding-polygon/avltree.rb, line 4 def initialize(array = []) #create root @root = nil array.each do |n| insert n end end
Public Instance Methods
delete(v)
click to toggle source
# File lib/winding-polygon/avltree.rb, line 60 def delete(v) d = search(v) return nil if d.nil? if @root.height==1 && @root.value==v @root = nil return nil end if d.left == nil or d.right == nil n = d else #both children exist n = d.next end if !n.left.nil? b = n.left else b = n.right end b.parent = n.parent unless b.nil? if n.parent.nil? @root = b elsif n == n.parent.left n.parent.left = b else n.parent.right = b end d.value = n.value unless n == d if b.nil? n.parent.update_height if !n.parent.nil? @root = n.balance else b.update_height @root = b.balance end n end
insert(v)
click to toggle source
# File lib/winding-polygon/avltree.rb, line 12 def insert(v) i_node = create_node(v) prev_node = nil curr_node = @root while !curr_node.nil? prev_node = curr_node if i_node.value < curr_node.value curr_node = curr_node.left else curr_node = curr_node.right end end if prev_node.nil? @root = i_node else i_node.parent = prev_node if i_node.value < prev_node.value prev_node.left = i_node else prev_node.right = i_node end end i_node.update_height @root = i_node.balance i_node end
max()
click to toggle source
# File lib/winding-polygon/avltree.rb, line 118 def max @root.max end
min()
click to toggle source
# File lib/winding-polygon/avltree.rb, line 114 def min @root.min end
print()
click to toggle source
# File lib/winding-polygon/avltree.rb, line 103 def print result = sort puts result.inspect end
scan(v)
click to toggle source
# File lib/winding-polygon/avltree.rb, line 45 def scan(v) current_node = @root while !current_node.nil? return current_node if current_node.value == v current_node = current_node.next end current_node = @root.prev while !current_node.nil? return current_node if current_node.value == v current_node = current_node.prev end current_node end
search(v)
click to toggle source
# File lib/winding-polygon/avltree.rb, line 41 def search(v) search_node(@root, v) end
sort()
click to toggle source
# File lib/winding-polygon/avltree.rb, line 108 def sort result = Array.new sort_node(@root, result ) result end
Private Instance Methods
create_node(v = nil)
click to toggle source
# File lib/winding-polygon/avltree.rb, line 125 def create_node(v = nil) n = AVLNode.new(:value => v) end
search_node(n, v)
click to toggle source
# File lib/winding-polygon/avltree.rb, line 137 def search_node(n, v) if !n.nil? if n.value == v return n elsif v < n.value search_node(n.left,v) else search_node(n.right,v) end end end
sort_node(n, array)
click to toggle source
# File lib/winding-polygon/avltree.rb, line 129 def sort_node(n, array) if !n.nil? sort_node(n.left, array) array.push(n.value) sort_node(n.right, array) end end