Language: EN FI

Exercises > AVL-tree insertion

These exercises demonstrate the content of the ByTheMark service. These are meant for private individuals for learning data structures and algorithms. If you want to try out more content, you can register to the ByTheMark Personal free of charge.

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.

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.

  Last modified Tue Mar 01 20:54:04 EET 2011