AVL FAQ

In an AVL Tree, you have a lot of nodes with pointers to other nodes. Whenever it comes time to add or remove nodes, you have to change what these pointers point to. However, if you simply pass a pointer into an add or remove function, you will pass a copy of the pointer instead of the original one. Then, when you try to change what the pointer points to, you will end up only changing the copy, while the original pointer (and therefore, the entire tree) remains unchanged. Passing a pointer by reference allows you to change the original pointer instead of making a copy.

Writing a function that accepts a reference to a pointer is simple. All you need to do is add an ampersand character (&) immediately following the asterisk (*). If I have the following function:

bool insert(Node* node);

Changing it to accept a reference to a pointer is as simple as adding an ampersand:

bool insert(Node*& node);

Passing to a function that accepts a reference to a pointer has the exact same syntax as passing to a function that takes a pointer.

Removing a node with a single child is a simple process. You simply replace it with its child. However, removing a node with two children is slightly more involved.

Removing a node with two children can be done in several ways, but for the sake of consistency, we will all do it the same way for this class.

The first thing to do is to find the "inorder predecessor." In other words, this means finding the largest node on the left side of the tree. To do this, go to the left child of the node you are trying to delete, and then recursively go to each right child until there are no more right children. The last right child is the inorder predecessor.

Once this is done, you will replace the node you are trying to delete with the inorder predecessor. After moving the inorder predecessor, be sure to balance every node you visited to find the inorder predecessor (this can be done on the way back up from the recursion). If the inorder predecessor had a left child before you moved it, the left child will take its original place.

There is a link to an AVL simulator on the main lab page that will allow you to see this process visually.

First, let's consider left imbalances. A left imbalance is any case where the height of the left side of a node is greater than the height of the right side. It is a critical imbalance if the difference between the heights is greater than 1.

A "left-right" imbalance is a left imbalance where the height of the right side of the left child is greater than the height of the left side of the left child. To fix this imbalance, we first convert it into a "left-left" imbalance by rotating the left child of the imbalanced node to the left. Then, simply rotate the imbalanced node to the right.

A "left-left" imbalance is a left imbalance where the height of the left side of the left child is greater than or equal to the height of the right side of the left child. This type of imbalance can be fixed by simply rotating the imbalanced node to the right.

Now, let's consider right imbalances. A right imbalance is any case where the height of the right side of a node is greater than the height of the left side. It is a critical imbalance if the difference between the heights is greater than 1.

A "right-left" imbalance is a right imbalance where the height of the left side of the right child is greater than the height of the right side of the right child. To fix this imbalance, we first convert it into a "right-right" imbalance by rotating the right child of the imbalanced node to the right. Then, simply rotate the imbalanced node to the left.

A "right-right" imbalance is a right imbalance where the height of the right side of the right child is greater than or equal to the height of the left side of the right child. This type of imbalance can be fixed by simply rotating the imbalanced node to the left.

Assuming you've done the recursion correctly (refer to the powerpoint for BST to make sure) you should check in the following places:

• Immediately after the recursive call when you successfully insert a node returns.
• Immediately after the recusrive call when you successfully delete a node returns.
• Immediately after you delete a node with one child.
• Immediately after the recursive call returns when deleting a node with two children.