TRAKLA2 - AVL-tree insertion

AVL-tree insertion

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions 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. The keys can be inserted by drag & dropping them from the Stream of Keys into the correct position in the tree below. If necessary, balance the tree after each insertion by selecting the node and correct rotation button.
AVL-Tree-Insert 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: if (`p.left == q`) and (`p.left.left == r`), single rotation right in p; if (`p.right == q`) and (`p.right.right == r`), single rotation left in p; if (`p.left == q`) and (`p.left.right == r`), LR-double rotation in p; or if (`p.right == q`) and (`p.right.left == r`), RL-double rotation in p.