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
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
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