AVL - Adelson-Velski Landis

To maintain balance in AVL

• Travel branches, keep track of deepest node with balance of +1 or -1 (pivot node)
• From pivot node down, compute balance factors
• Look for any changes from 1 to 2 or -1 to -2
• If changes, manipulate pointers to rebalance tree

Four cases to consider:

• (LL) Insert into left subtree of left child of pivot
• (RR) Insert into right subtree of right child of pivot
• (LR) Insert into right subtree of left child of pivot
• (RL) Insert into left subtree of right child of pivot

LL Rotation

P = Node[Pivot].Left
Q = Node[P].Right
Node[P].Right = Pivot
Node[Pivot].Left = Q
Pivot = P
Node[Pivot].BF = 0
Node[Node[Pivot].Right].BF = 0

LR Rotation

X = Node[Pivot].Left
Y = Node[X].Right
Node[Pivot].Left = Node[Y].Right
Node[X].Right = Node[Y].Left
Node[Y].Left = X
Node[Y].Right = Pivot
Pivot = Y

if Node[Pivot].BF = 0 then
{
  Node[Node[Pivot].Left].BF = 0
  Node[Node[Pivot].Right].BF = 0
}
else if Node[Pivot].BF = 1 then
{
  Node[Pivot].BF = 0
  Node[Node[Pivot].Left.BF = 0
  Node[Node[Pivot].Right.BF = -1
}
else
{
  Node[Pivot].BF = 0
  Node[Node[Pivot].Left].BF = 1
  Node [Node[Pivot].Pivot].BF = 0
}

Return to CIS 350 Index Page