Learning Objectives
By the end of this class, you should know...

  • What is an AVL Tree?
  • What is the definition of a balanced tree according to the AVL tree property?
  • How do AVL trees maintain their balance?
  • What is the pseudocode for AVL insert?


AVL Trees

  • An AVL tree (Georgy Adelson-Velsky and Evgenii Landis tree) is a self-balancing BST.


AVL Tree Property

  • Requires that the heights of the left and right children of every node differ by at most one.
|left.height - right.height| <= 1
  • Maintains a balanced tree to achieve O(log n) time for ALL operations.
    • Review: What is the Big-O runtime of BST operations in best, worst and average cases?


AVL Tree Insert

  • We need to insert nodes in such a way that the AVL tree property is satisfied.
  • Thus, inside of our BST Nodes we are going to keep track of the height of the nodes.

struct Node
{
    bstdata data;

    int height;

    Node* left;
    Node* right;

    Node(): left(NULL), right(NULL), height(0){}
    Node(bstdata newdata): left(NULL), right(NULL), data(newdata), height(0){}
};

  • Insertion has 2 steps:
  1. Call BST insert
  2. Rebalance the Tree
  • To balance the tree we use what are called "rotations" to alter the location of certain nodes.


AVL Insert Pseudocode (Partial)

Node avlInsert(Node root, int value)
    //BST style insertion
if (root == NULL)
    return new Node(value)
else if(root.data >= value)
    root->left = avlInsert(root->left, value)
else
    root->right = avlInsert(root->right, value)
//value has now been inserted
//Is the resulting tree unbalanced?
int balance = root->left->height - root->right->height
if (balance > 1 || balance < -1)
    //re-balance the tree using rotations
    //to be filled in later in class

AVL Trees Maintain Balance by Readjusting the Tree -- i.e. doing what are called "Rotations" -- upon insertion and deletion.



https://a67f228e-a-62cb3a1a-s-sites.googlegroups.com/site/deanzacollegecis/cis22c/22c-class-schedule/avlrbtrees/Screen%20Shot%202016-05-24%20at%2012.16.15%20PM.png?attachauth=ANoY7crB7nJ5cAvOVizrQDLbOqoeB-PM4WuK39hTgNXm-wZb-2V9TOZNsD2Uq_eB2aWNBzk1SbviM4gn5ZuyROMlEuwFODtnOPlZifc-SJ48Zys8IuFYErW4EVHZiGtnvEFd1UM0Ne-a2Zfgg43ZhkGR2bCqc_gC_RBnS8K2fwmtPvW8u36M3ShWwkUtBw1ajLcX4Mux3CTPC5AEeBNFmbhuBleYke0AtTWXTHeZTfANPoD9lM8TPPXRKxgE6rzoUAJvC9IgYaa5IjzqOh6YGFC66z0rZdJlob0sHUo54_1iRPyGfVfMshLIdebddt5L5dgRl9Se9k37&attredirects=0https://a67f228e-a-62cb3a1a-s-sites.googlegroups.com/site/deanzacollegecis/cis22c/22c-class-schedule/avlrbtrees/Screen%20Shot%202016-05-24%20at%2012.17.20%20PM.png?attachauth=ANoY7cpMHXw1SZluw5wUxYDNb0kjkF9DWr8gTJBPeSYiDgOQ7rjDEE0K_v-lYWfzqjR0R8_vAKv9EGoR3zC_2yMD_etXMMIerpfZ9bpxpmgiEshSo3NMrmsEukNHMnfr_t-AGJK7YtT2k_imlqvf_PREytZIAYk_MAoLm5pqWHQhqxgo8xrkbaQuLbhwyqrWBk1IVJlLUq0nlmLqVY0s1yZH7VwQActFro0h9xK_t5DlLP_KnzJe2stwYvYOFcmMy-OCl6yte4iR1AdCSnABm80xTgDP9j7UBEeTUBid3Js67kpfX-Q5O-OQA0ewPCwSnEIfwykuKG5j&attredirects=0

Rotations

generalrotations.png


  • With rotations, we want the height of the tree to become shorter (tree looks less like a linked list)
  • Important: These rotations maintain the order of the BST: T1 < A < T2 < B < T3.
Simple Examples

Tree rotation.png

Image source.

Right Rotation



        Before Rotation        After Rotation


  • Note that the upper case letters represent nodes in the tree, while the lower case letters represent possible subtrees.
  • What happened to subtree c during the rotation?


Example Right Rotation




Right Rotation Pseudocode


Nodeptr Right-Rotate(Nodeptr root)
Nodeptr newRoot = root->left
root->left = newRoot->right
newRoot->right = root
root->height = maxHeight(root->left, root->right) + 1
newRoot->height = maxHeight(newRoot->left, newRoot->right) + 1
return newRoot

Left Rotation 

                    Before Left Rotation                               After Left Rotation


Example Left Rotation



Image source.

Double Rotations

  • Sometimes a single rotation is not enough to balance a tree.
  • Consider the following example:
    • Our reaction might be to right rotate it, like so:
    • However, we are now no better off than when we started.
    • In cases like these (zig-zag pattern), we need to use a double rotation.
    • We will need to do either a left-right rotation or a right-left rotation, depending on the situation.
    • If the left subree is "right heavy" (i.e. left.height - right.height < -1)
      • rotate left then rotate right
    • If the right subtree is "left heavy" (i.e. left.height - right.height > 1)
      • rotate right then rotate left
    • In the example above, we have a left heavy right subtree.
    • Therefore, we will do a left-right rotation.

    Step 1: Rotate left around the root.left, i.e. node A (to get a familar shape)

    Step 2: Rotate right around the root, i.e. B (to get a balanced tree)

    Image:DoubleRightRotation.png

    Example of left-right rotation


    Image source.
    • If we have the opposite situation, where the right subtree is left heavy:
    • Then, we must perform a right-left rotation.

    Step 1: Rotate right around root.right, i.e. A (to get a familar shape)

    Step 2: Rotate left around root, i.e. B (to get a balanced tree)

    Image:DoubleLeftRotation.png

    Example of right-left rotation


    Image source.

    For More Information: Double Rotation Videos


AVL Insert Pseudocode (Full)

Nodeptr avlInsert(Nodeptr root, int value)
{
    //BST style insertion
    if (root == NULL)
        return(newNode(value));
 
    if (value < root.data)
        root->left  = avlInsert(root->left, value);
    else
        root->right = avlInsert(root->right, value);
 
    //Check the balance
    int balance = height(root->left) - height(root->right);
 
   //Check for 4 cases
 

    // Simple Right Rotation
    if (balance > 1 && value < root->left->data)
        return rightRotate(root);
 
    // Simple Left Rotation
    else if (balance < -1 && value > root->right->data)
        return leftRotate(root);
 
    // Left Right Case Double Rotation
    else if (balance > 1 && value > root->left->value)
        root->left =  leftRotate(root->left);
        return rightRotate(root);
 
    // Right Left Case Double Rotation
    else if (balance < -1 && value < root->right->data)
        root->right = rightRotate(root->right);
        return leftRotate(root);
   
    //return the node pointer

    return root;


For More Information: Video