AVL-tree insertion

Hide text Hide pseudo-code

Insert the given keys into the initially empty AVL-tree. If there are equal keys they are always inserted into the right branch of the existing node.

Some additional problems.

1 Do Binary Search Tree Insert (recursive algorithm)

2 While the recursion returns, keep track of

  • node p,
  • p's child q and
  • p's grandchild r within the path from inserted node to p.

3 If p is unbalanced, do one of the following rotations:

  1. if (p.left == q) and (p.left.left == r), single rotation right in p;
  2. if (p.right == q) and (p.right.right == r), single rotation left in p;
  3. if (p.left == q) and (p.left.right == r), LR-double rotation in p; or
  4. if (p.right == q) and (p.right.left == r), RL-double rotation in p.

  Created Fri Oct 30 13:52:51 EET 2009 - Powered by SVG-hut