BST:

Insert:

void insert(const T& entry);

Compare the item you need to insert with the item at the root. If it's larger, recursively, call the insert of the right subtree, call the insert function of the left subtree otherwise.

Print:

void print(const tree_node<T>* root, int level = 0; ostream& outs = cout);

It is very useful to have a print function that recursively prints the tree right subtree first, then, the root (spaced according to level) and then recursively print the left subtree. This will show the tree sideways and makes it easy to see what the tree actually looks like.

When printing the node, cout<<setw(level * 4)<<""<<root->item<<endl;

and when printing the right and left subtrees, call print with level + 1 so that the function knows how much to add before printing the root of each subtree:

        / right subtree
root
       \ left subtree

Search:

bool search(const T& target, tree_node<T>*& found_ptr);

• if root is null, then return false. The key is not in this tree.
• compare the key to the current node:
  • if the key is equal to the current item, then  you found it: return true
  • if the key is less than the current node, search the left subtree, otherwise, search the right subtree

Erase:

void erase(const T& target);

• 1. root is null:  the item is not in the tree
• 2. target is larger than the current node: recursively, call erase on the right subtree
• 3. target is smaller than the current node: recursively, call erase on the left subtree
• 4. target is equal to the current node:
  • 4a. the current node DOES NOT have a left subtree: point root to the right subtree, bypassing (and deleting) the target node.
  • 4b. the current DOES have a left subtree: replace the item with left subtree's rightmost node (deleting the rightmost node)

AVL Trees

AVL trees are self-balancing trees where the balance factor of each node is less than 1, 0 or -1.

Balance Factor is the height of the left subtree minus the height of the right subtree. When balance factor is >0, the tree is "left heavy" and when the balance factor is <0, the tree is "right heavy"

In order to keep the tree balanced, two types of operations are added to the BST: 

Rotate Left: where x is "right heavy", and so, y becomes parent of x and x becomes the left child of y (and a sibling to z) and therefore, y (and the rest of the tree) becomes balanced:

    /*
     *  x                   y
     *   \                 / \
     *    y     ==>       x   z
     *     \
     *      z
     */

Rotate Right: where x is "left heavy", and so, y becomes parent of x and x becomes the right child of y (and a sibling to z) and therefore, y (and the rest of the tree) becomes balanced:

    /*
     *      x               y
     *     /              /   \
     *    y     ==>      z     x
     *   /
     *  z
     */

 Balancing:

Armed with these two basic operations, we can balance all the four types of imbalance:

The balancing operation must take place after inserting or erasing elements from a binary tree

    if (root->balance_factor() == -2){
        /*  a: rotate left   b: rotate right (at Y) and then rotate left (at X)
         *  x                   x
         *   \                   \
         *    y                    y
         *     \                  /
         *      z               z
         */
    else if(root->balance_factor() == +2){
        /*  c: rotate right  d: rotate left (at Y) and then rotate right (at X)
         *          x           x
         *        /            /
         *      y             y
         *     /               \
         *    z                 z
         */