AVL Tree Balance Factor

AVL Trees Balance Factor video (33 minutes) (Spring 2021)

An AVL tree is a balanced BST, where at each node, the height of the right subtree and the height of the left subtree are within 1.

The Balance Factor of an AVL node is the Right Subtree Height minus the Left Subtree Height.

Balance Factor = Height(Right Subtree) - Height(Left Subtree)

Visual Examples

    O balanceFactor = 2
     \
      O balanceFactor = 1
       \
        O balanceFactor = 0

    O balanceFactor = -1
   /
  O balanceFactor = 0

    O balanceFactor = 0
   / \
  O   O

Tracking Balance Factor as the tree changes

A balance factor integer is maintained at each node in an AVL tree.

Balance factor changes if the height of a node's subtree changes.

Changes in balance factor may recursively propagate up the tree.

For an insert, balance factor will either change by 1, or stay the same.

If the absolute value of the balance factor of a node increases, that is an indication that the height of one of the node's subtree changed.

Note, there is NOT a guarantee that insert affects height of a subtree! If the subtree had a left child, and insert created a right child, that would not affect height of the subtree

Code Updates

Our BinarySearchTree class has been updated to implement balance factor.

Node struct changes

int balance_factor added to Node struct, to track this info at each Node

...
struct Node {
    Key key;
    Value value;
    int balance_factor;
    Node *left, *right;
...

Node::insert() function is updated, to increment or decrement balance factor depending on if insert affects height of a subtree.

    bool insert(const Key& new_key, const Value& new_value) {
      if (new_key == key) {
        return false;
      } else if  (new_key < key) {  // Need to insert to the left
        if (left == nullptr) {
          --balance_factor;
          left = new Node(new_key, new_value);
          return true;
        } else {
          int prev_left_bf = left->balance_factor;
          bool result = left->insert(new_key, new_value);
          int cur_left_bf = left->balance_factor;
          // if the left subtree is bigger after the insert ...
          if (abs(cur_left_bf) > abs(prev_left_bf)) {
            --balance_factor;
          }
          return result;
        }
      } else { // if (new_key > key)  Need to insert to the right
        if (right == nullptr) {
          ++balance_factor;
          right = new Node(new_key, new_value);
          return true;
        } else {
          int prev_right_bf = right->balance_factor;
          bool result = right->insert(new_key, new_value);
          int cur_right_bf = right->balance_factor;
          // if the right subtree is bigger after the insert ...
          if (abs(cur_right_bf) > abs(prev_right_bf)) {
            ++balance_factor;
          }
          return result;
        }
      }
    }

Thanks

Thanks to Brian Foster for writing up these notes based on the video lectures.