class WindingPolygon::AVLNode

Constants

BAL_H

Attributes

height[RW]
left[RW]
parent[RW]
right[RW]
value[RW]

Public Class Methods

new(args) click to toggle source
# File lib/winding-polygon/avltree.rb, line 153
def initialize args
  @height = 0
  @left = nil
  @right = nil
  @value = nil
  @parent = nil
  args.each do |k,v|
    instance_variable_set("@#{k}", v) unless v.nil?
  end
end

Public Instance Methods

balance() click to toggle source
# File lib/winding-polygon/avltree.rb, line 164
def balance
  rotate if difference.abs > BAL_H
  return self if @parent.nil?
  @parent.balance
end
difference() click to toggle source
# File lib/winding-polygon/avltree.rb, line 235
def difference
  r_height = @right.nil? ? 0 : @right.height
  l_height = @left.nil? ? 0 : @left.height
  r_height - l_height
end
max() click to toggle source
# File lib/winding-polygon/avltree.rb, line 278
def max
  node = self
  while !node.right.nil?
    node = node.right
  end
  node
end
min() click to toggle source
# File lib/winding-polygon/avltree.rb, line 270
def min
  node = self
  while !node.left.nil?
    node = node.left
  end
  node
end
next() click to toggle source
# File lib/winding-polygon/avltree.rb, line 241
def next
  if not @right.nil?
    @right.min
  else
    curr_node = self
    p_node = @parent
    while p_node != nil && curr_node == p_node.right
      curr_node = p_node
      p_node = p_node.parent
    end
    p_node
  end
end
prev() click to toggle source
# File lib/winding-polygon/avltree.rb, line 255
def prev
  if not @left.nil?
    @left.max
  else
    curr_node = self
    p_node = @parent
    while p_node != nil && curr_node == p_node.left
      curr_node = p_node
      p_node = p_node.parent
    end
    p_node
  end
end
print() click to toggle source
print_node() click to toggle source
rotate() click to toggle source
# File lib/winding-polygon/avltree.rb, line 177
def rotate
  if difference >= BAL_H
    #check if children should rotate too
    @right.rotate if @right.difference <= -BAL_H
    rotate_left
  elsif difference <= - BAL_H
    #check if children should rotate too
    @left.rotate if @left.difference >= BAL_H
    rotate_right
  end
end
rotate_left() click to toggle source
# File lib/winding-polygon/avltree.rb, line 189
def rotate_left
  #the old right is now the root
  root = @right
  root.parent = @parent
  #update the parent to point to the new root
  if not @parent.nil?
    if @parent.right == self
      @parent.right = root
    else
      @parent.left = root
    end
  end

  #this node's right is now the root's left
  @right = root.left
  root.left.parent = self unless root.left.nil?

  #the root is now the parent of this node
  @parent = root
  #this node is now the root's left
  root.left = self
  root.left.update_height
  root
end
rotate_right() click to toggle source
# File lib/winding-polygon/avltree.rb, line 214
def rotate_right
  root = @left
  root.parent = @parent
  #update the parent to point to the new root
  if not @parent.nil?
    if @parent.right == self
      @parent.right = root
    else
      @parent.left = root
    end
  end

  @left = root.right
  root.right.parent = self unless root.right.nil?

  @parent = root
  root.right = self
  root.right.update_height
  root
end
to_s() click to toggle source
# File lib/winding-polygon/avltree.rb, line 303
def to_s
  @value.to_s
end
update_height() click to toggle source
# File lib/winding-polygon/avltree.rb, line 170
def update_height
  l_height = @left.nil? ? 0 : @left.height
  r_height = @right.nil? ? 0 : @right.height
  @height = ((l_height > r_height) ? l_height : r_height) + 1
  @parent.update_height unless @parent.nil?
end