Please note the following errors in the AVL handout:
- Overall the pseudocode assumes that there's always a node above the ones
we're changing. This will break if we need to rotate the root of the
tree
FIX: Make sure to mention the idea of a 'sentinel node' or 'dummy node' that
will always be the root of the tree (so this algorithm works without a
complete copy of the code for just the root case); mention also ref
parameters (which can also fix this problem)
- On Page 3 it mentions a tree off to the right - this is drawn on page 6
- On page 4, under "//Case 2a", line should be:
AVLNode B = parent.Right;
- Similarly, on page 5 under case "2b", define B as parent.Left;
- On page 5, under "case 1B"
There's no code to adjust the balances (there's a comment about this
instead)