class AVLTree::AVLTree

Private Instance Methods

add_to_tree(item, node) click to toggle source

Calls superclass (BSTree) method passing in parameters recieved from caller. Passes in the returned value of BSTree#add_to_tree to :rebalance and returns final result.

Calls superclass method
# File lib/ruby-avl/avl_tree.rb, line 12
def add_to_tree(item, node)
  return rebalance(super(item, node))
end
balance_factor(node) click to toggle source

Calculates the height of the left subtree, then subtracts the height of the right subtree to produce the balance factor for the node.

# File lib/ruby-avl/avl_tree.rb, line 87
def balance_factor(node)
  node.nil? ? 0 : (height(node.left) - height(node.right))
end
double_rotate_left(node) click to toggle source

Right rotation performed on node's right subtree before node is rotated left.

# File lib/ruby-avl/avl_tree.rb, line 65
def double_rotate_left(node)
  node.right = rotate_right(node.right)
  return rotate_left(node)
end
double_rotate_right(node) click to toggle source

Left rotation performed on node's left subtree before node is rotated right.

# File lib/ruby-avl/avl_tree.rb, line 80
def double_rotate_right(node)
  node.left = rotate_left(node.left)
  return rotate_right(node)    
end
rebalance(node) click to toggle source

Checks the balance factor of the node and rotates the tree if inbalanced in any way. Balance algorithm: IF tree is right heavy

IF tree's right subtree is left heavy (Right Left Case)
   Perform Double Left rotation
ELSE (Right Right Case)
   Perform Single Left rotation

ELSE IF tree is left heavy

IF tree's left subtree is right heavy (Left Right Case)
   Perform Double Right rotation
ELSE (Left Left Case)
   Perform Single Right rotation

END IF

# File lib/ruby-avl/avl_tree.rb, line 37
def rebalance(node)
  if balance_factor(node) >= 2
    if (balance_factor(node.left) < 0)
      return double_rotate_right(node)
    else
      return rotate_right(node)
    end
  elsif balance_factor(node) <= -2
    if (balance_factor(node.right) > 0)
      return double_rotate_left(node)
    else
      return rotate_left(node)
    end
  else
    return node
  end
end
remove_from_tree(item, node) click to toggle source

Calls superclass (BSTree) method passing in parameters recieved from caller. Passes in the returned value of BSTree#remove_from_tree to :rebalance and returns final result.

Calls superclass method
# File lib/ruby-avl/avl_tree.rb, line 20
def remove_from_tree(item, node)    
  return rebalance(super(item, node))
end
rotate_left(node) click to toggle source

Node becomes the left subtree of it's right subtree.

# File lib/ruby-avl/avl_tree.rb, line 56
def rotate_left(node)
  new_node = node.right
  node.right = new_node.left
  new_node.left = node
  return new_node
end
rotate_right(node) click to toggle source

Node becomes the right subtree of it's left subtree.

# File lib/ruby-avl/avl_tree.rb, line 71
def rotate_right(node)
  new_node = node.left
  node.left = new_node.right
  new_node.right = node
  return new_node
end