Efficient AVL Tree in C#

The AVL tree is a rigorously balance binary search tree with very fast and stable insert, delete and search times. I like the various .NET dictionaries but have been unimpressed by their performance. So, after researching efficient dictionary algorithms, I stumbled upon AVL trees and decided to code a really efficient implementation (performance being my main concern). In this post I will discuss the techniques I used to create a highly optimised AVL tree that can be used like a dictionary (although I don't implement IDictionary for brevity) with very fast and reliable performance under varied usage scenarios.

There are roughly two ways to code this algorithm: with or without recursion. The non-recursive way is more efficient as the CLR does not have to keep pushing and popping its call stack (which is quite slow). The non-recursive way is unfortunately harder to code. So the challenge was on!

There are also two ways to keep track of the balance of each tree node, indirectly by storing the height, or directly by storing the balance. Again, storing the balance directly is harder to code as a full understanding of how rotations affect the balance of each node in the rotation is needed (useful and reliable information on the internet is hard to find on how to keep track of balances directly for deletion). Challenge number two!

I will discuss the full implementation of an AVL tree in C# which tracks balance by storing the balances directly and doesn’t use recursion. It out performs Microsoft’s generic SortedDictionary<TKey, TValue> (which is actually a red-black tree) by a factor of 2 for inserts and a factor of 4 for searches.

The complete source code can be obtained from my github (link at the bottom of this post) so you don’t have to piece together the code from my walk through.

Node Height

Although I don’t use height in my AVL tree, it is useful to understand the definition of height for the AVL algorithm. The height of a node is measured by how many generations of descendents it has. The root node will therefore increase in height as descendants are added to it:

    R
   / \
  A   B
 /
C

The root node R has a height of 2; nodes A and B have a height of 1; node C has a height of 0.

Node Balance

I keep track of each node’s balance in my AVL tree. The balance of a node is the difference in height between its left and right sub-tree.

    R
   / \
  A   B
   \
    C

The root node R has a balance of 1; node A has a balance of -1; nodes B and C have a balance of 0.

Node Ordering

The nodes in an AVL tree are ordered so that a left child is always smaller than its parent and a right child is always greater than its parent.

The C# AVL Tree

I’ll introduce the code as I go, so for now, let’s look at the AVL tree class and node class:

public class AvlTree<TKey, TValue> : IEnumerable<TValue>
{
   private IComparer<TKey> _comparer;
   private AvlNode _root;

   sealed class AvlNode
   {
      public AvlNode Parent;
      public AvlNode Left;
      public AvlNode Right;
      public TKey Key;
      public TValue Value;
      public int Balance;
   }

   public AvlTree(IComparer<TKey> comparer)
   {
      _comparer = comparer;
   }

   public AvlTree()
      : this(Comparer<TKey>.Default)
   {

   }

   //...
}

Notice that the node class stores its parent, this isn’t necessary, but if you don’t you’ll need to keep track of the parents as the tree is traversed which would make the algorithm slower, but lighter on memory.

Node Insertion

When a new node is added to an AVL tree, it must be added in the right place to make sure the tree remains ordered. The sequence at which nodes are added to an AVL tree will affect the structure (i.e. two trees with the same nodes might have different structures).

Consider these two trees:

    5
   / \
  3   6
   \
    4
    4
   / \
  3   6
     /
    5

These AVL trees are valid, they both have the same node values, and they are both in order. Due to the order in which the nodes were added, however, their structures are slightly different.

The algorithm for adding a new node is this:

public void Insert(TKey key, TValue value)
{
   if (_root == null)
   {
      _root = new AvlNode { Key = key, Value = value };
   }
   else
   {
      AvlNode node = _root;

      while (node != null)
      {
         int compare = _comparer.Compare(key, node.Key);

         if (compare < 0)
         {
            AvlNode left = node.Left;

            if (left == null)
            {
               node.Left = new AvlNode { Key = key, Value = value, Parent = node };

               InsertBalance(node, 1);

               return;
            }
            else
            {
               node = left;
            }
         }
         else if (compare > 0)
         {
            AvlNode right = node.Right;

            if (right == null)
            {
               node.Right = new AvlNode { Key = key, Value = value, Parent = node };

               InsertBalance(node, -1);

               return;
            }
            else
            {
               node = right;
            }
         }
         else
         {
            node.Value = value;

            return;
         }
      }
   }
}

Balancing after Insertion

The method InsertBalance is necessary for rebalancing the tree after an insertion. If the balance of a node becomes 2 or -2 it must be rotated. There are four types of rotation: left, right, left-right and right-left:

Left Rotation

       (5)                   (4)
      /   \                 /   \
     (4)   S               /     \
    /   \        ==>     (3)     (5)
   (3)   R               / \     / \
  /   \                 /   \   /   \
 P     Q               P     Q R     S

Left Right Rotation

This involves a left rotation with 3 and 4 followed by a right rotation with 4 and 5.

       (5)                  (5)                 (4)
      /   \                /   \               /   \
     (3)   S              (4)   S             /     \
    /   \        ==>     /   \       ==>    (3)     (5)
   P    (4)             (3)   R             / \     / \
       /   \           /   \               /   \   /   \
      Q     R         P     Q             P     Q R     S

Right Rotation

     (3)                     (4)
    /   \                   /   \
   P   (4)                 /     \
      /   \      ==>     (3)     (5)
     Q   (5)             / \     / \
        /   \           /   \   /   \
       R     S         P     Q R     S

Right Left Rotation

This involves a right rotation with 4 and 5 followed by a left rotation with 3 and 4.

     (3)                 (3)                     (4)
    /   \               /   \                   /   \
   P   (5)             P   (4)                 /     \
      /   \      ==>      /   \      ==>     (3)     (5)
    (4)    D             Q   (5)             / \     / \
   /   \                    /   \           /   \   /   \
  B     C                  R     S         P     Q R     S

There are two rules that allow the balancing for insertions to be optimised

  • After a rotation, the node will have a balance of 0 (this is not obvious from the rotation code for the left and right case and doesn't hold true for deletion)
  • If a node’s balance is 0 you can stop traversing back up the tree

It also follows that you can stop traversing back up the tree if you perform a rotation. These rules do not hold true for deletion.

The method InsertBalance:

private void InsertBalance(AvlNode node, int balance)
{
   while (node != null)
   {
      balance = (node.Balance += balance);

      if (balance == 0)
      {
         return;
      }
      else if (balance == 2)
      {
         if (node.Left.Balance == 1)
         {
            RotateRight(node);
         }
         else
         {
            RotateLeftRight(node);
         }

         return;
      }
      else if (balance == -2)
      {
         if (node.Right.Balance == -1)
         {
            RotateLeft(node);
         }
         else
         {
            RotateRightLeft(node);
         }

         return;
      }

      AvlNode parent = node.Parent;

      if (parent != null)
      {
         balance = parent.Left == node ? 1 : -1;
      }

      node = parent;
   }
}

The balancing methods (notice how the balance is affected by rotation):

private AvlNode RotateLeft(AvlNode node)
{
    AvlNode right = node.Right;
    AvlNode rightLeft = right.Left;
    AvlNode parent = node.Parent;

    right.Parent = parent;
    right.Left = node;
    node.Right = rightLeft;
    node.Parent = right;

    if (rightLeft != null)
    {
        rightLeft.Parent = node;
    }

    if (node == _root)
    {
        _root = right;
    }
    else if (parent.Right == node)
    {
        parent.Right = right;
    }
    else
    {
        parent.Left = right;
    }

    right.Balance++;
    node.Balance = -right.Balance;

    return right;
}

private AvlNode RotateRight(AvlNode node)
{
    AvlNode left = node.Left;
    AvlNode leftRight = left.Right;
    AvlNode parent = node.Parent;

    left.Parent = parent;
    left.Right = node;
    node.Left = leftRight;
    node.Parent = left;

    if (leftRight != null)
    {
        leftRight.Parent = node;
    }

    if (node == _root)
    {
        _root = left;
    }
    else if (parent.Left == node)
    {
        parent.Left = left;
    }
    else
    {
        parent.Right = left;
    }

    left.Balance--;
    node.Balance = -left.Balance;

    return left;
}

private AvlNode RotateLeftRight(AvlNode node)
{
    AvlNode left = node.Left;
    AvlNode leftRight = left.Right;
    AvlNode parent = node.Parent;
    AvlNode leftRightRight = leftRight.Right;
    AvlNode leftRightLeft = leftRight.Left;

    leftRight.Parent = parent;
    node.Left = leftRightRight;
    left.Right = leftRightLeft;
    leftRight.Left = left;
    leftRight.Right = node;
    left.Parent = leftRight;
    node.Parent = leftRight;

    if (leftRightRight != null)
    {
        leftRightRight.Parent = node;
    }

    if (leftRightLeft != null)
    {
        leftRightLeft.Parent = left;
    }

    if (node == _root)
    {
        _root = leftRight;
    }
    else if (parent.Left == node)
    {
        parent.Left = leftRight;
    }
    else
    {
        parent.Right = leftRight;
    }

    if (leftRight.Balance == -1)
    {
        node.Balance = 0;
        left.Balance = 1;
    }
    else if (leftRight.Balance == 0)
    {
        node.Balance = 0;
        left.Balance = 0;
    }
    else
    {
        node.Balance = -1;
        left.Balance = 0;
    }

    leftRight.Balance = 0;

    return leftRight;
}

private AvlNode RotateRightLeft(AvlNode node)
{
    AvlNode right = node.Right;
    AvlNode rightLeft = right.Left;
    AvlNode parent = node.Parent;
    AvlNode rightLeftLeft = rightLeft.Left;
    AvlNode rightLeftRight = rightLeft.Right;

    rightLeft.Parent = parent;
    node.Right = rightLeftLeft;
    right.Left = rightLeftRight;
    rightLeft.Right = right;
    rightLeft.Left = node;
    right.Parent = rightLeft;
    node.Parent = rightLeft;

    if (rightLeftLeft != null)
    {
        rightLeftLeft.Parent = node;
    }

    if (rightLeftRight != null)
    {
        rightLeftRight.Parent = right;
    }

    if (node == _root)
    {
        _root = rightLeft;
    }
    else if (parent.Right == node)
    {
        parent.Right = rightLeft;
    }
    else
    {
        parent.Left = rightLeft;
    }

    if (rightLeft.Balance == 1)
    {
        node.Balance = 0;
        right.Balance = -1;
    }
    else if (rightLeft.Balance == 0)
    {
        node.Balance = 0;
        right.Balance = 0;
    }
    else
    {
        node.Balance = 1;
        right.Balance = 0;
    }

    rightLeft.Balance = 0;

    return rightLeft;
}

Deletion

When a node is deleted from an AVL tree, it must be removed correctly to make sure the tree remains ordered. The logic to delete a node is somewhat harder to implement than the code for insertion and I struggled for a while to understand the AVL algorithm sufficiently so that I could not only code the delete portion of the tree, but also ensure it was optimal.

My implementation of delete considers each edge case separately so that no unnecessary operations are performed:

public bool Delete(TKey key)
{
   AvlNode node = _root;

   while (node != null)
   {
      if (_comparer.Compare(key, node.Key) < 0)
      {
         node = node.Left;
      }
      else if (_comparer.Compare(key, node.Key) > 0)
      {
         node = node.Right;
      }
      else
      {
         AvlNode left = node.Left;
         AvlNode right = node.Right;

         if (left == null)
         {
            if (right == null)
            {
               if (node == _root)
               {
                  _root = null;
               }
               else
               {
                  AvlNode parent = node.Parent;

                  if (parent.Left == node)
                  {
                     parent.Left = null;

                     DeleteBalance(parent, -1);
                  }
                  else
                  {
                     parent.Right = null;

                     DeleteBalance(parent, 1);
                  }
               }
            }
            else
            {
               Replace(node, right);

               DeleteBalance(node, 0);
            }
         }
         else if (right == null)
         {
            Replace(node, left);

            DeleteBalance(node, 0);
         }
         else
         {
            AvlNode successor = right;

            if (successor.Left == null)
            {
               AvlNode parent = node.Parent;

               successor.Parent = parent;
               successor.Left = left;
               successor.Balance = node.Balance;

               if (left != null)
               {
                  left.Parent = successor;
               }

               if (node == _root)
               {
                  _root = successor;
               }
               else
               {
                  if (parent.Left == node)
                  {
                     parent.Left = successor;
                  }
                  else
                  {
                     parent.Right = successor;
                  }
               }

               DeleteBalance(successor, 1);
            }
            else
            {
               while (successor.Left != null)
               {
                  successor = successor.Left;
               }

               AvlNode parent = node.Parent;
               AvlNode successorParent = successor.Parent;
               AvlNode successorRight = successor.Right;

               if (successorParent.Left == successor)
               {
                  successorParent.Left = successorRight;
               }
               else
               {
                  successorParent.Right = successorRight;
               }

               if (successorRight != null)
               {
                  successorRight.Parent = successorParent;
               }

               successor.Parent = parent;
               successor.Left = left;
               successor.Balance = node.Balance;
               successor.Right = right;
               right.Parent = successor;

               if (left != null)
               {
                  left.Parent = successor;
               }

               if (node == _root)
               {
                  _root = successor;
               }
               else
               {
                  if (parent.Left == node)
                  {
                     parent.Left = successor;
                  }
                  else
                  {
                     parent.Right = successor;
                  }
               }

               DeleteBalance(successorParent, -1);
            }
         }

         return true;
      }
   }

   return false;
}

Balancing after Deletion

The added complexity of rebalancing a deletion is the possibility of more than a single rotation to restore the tree to balance.

There are several rules that allow the balancing for deletions to be optimised:

  • After a right rotation, the node will have a balance of 0 or -1
  • After a left rotation, the node will have a balance of 0 or 1
  • After a left-right or right-left rotation, the node will have a balance of 0
  • If a node’s balance is 1 or -1 you can stop traversing back up the tree

It follows that you must continue traversing and rebalancing up the tree even after a rotation unless the last rule is met which is why we can end up with more than one rotation during a deletion.

Although deletion has many edge cases, the balancing portion of the code is similar in complexity to insertion, however it is different (note that I have heavily optimised the code so that no unnecessary operations are performed, for instance after a rotate right, I only need to check for a balance of -1 to quit rebalancing as the 1 case cannot occur due to the rules above):

private void DeleteBalance(AvlNode node, int balance)
{
   while (node != null)
   {
      balance = (node.Balance += balance);

      if (balance == 2)
      {
         if (node.Left.Balance >= 0)
         {
            node = RotateRight(node);

            if (node.Balance == -1)
            {
               return;
            }
         }
         else
         {
            node = RotateLeftRight(node);
         }
      }
      else if (balance == -2)
      {
         if (node.Right.Balance <= 0)
         {
            node = RotateLeft(node);

            if (node.Balance == 1)
            {
               return;
            }
         }
         else
         {
            node = RotateRightLeft(node);
         }
      }
      else if (balance != 0)
      {
         return;
      }

      AvlNode parent = node.Parent;

      if (parent != null)
      {
         balance = parent.Left == node ? -1 : 1;
      }

      node = parent;
   }
}

Here is the Replace method that is used by the Delete method:

private static void Replace(AvlNode target, AvlNode source)
{
   AvlNode left = source.Left;
   AvlNode right = source.Right;

   target.Balance = source.Balance;
   target.Key = source.Key;
   target.Value = source.Value;
   target.Left = left;
   target.Right = right;

   if (left != null)
   {
      left.Parent = target;
   }

   if (right != null)
   {
      right.Parent = target;
   }
}

The final non-trivial task involving my pursuit of an efficient AVL tree is in-order traversal of the tree structure without using recursion or a temporary stack. As long as the parent of each node is available, it’s actually possible to write an extremely efficient solution to this problem using .NET:

IEnumerator IEnumerable.GetEnumerator()
{
   return GetEnumerator();
}

public IEnumerator<TValue> GetEnumerator()
{
   return new AvlNodeEnumerator(_root);
}

In my AvlTree class, this enumerator is nested inside it, and so the TValue generic parameter is inherited from AvlTree<TKey, TValue>:

sealed class AvlNodeEnumerator : IEnumerator<TValue>
{
   private AvlNode _root;
   private Action _action;
   private AvlNode _current;
   private AvlNode _right;

   public AvlNodeEnumerator(AvlNode root)
   {
      _right = _root = root;
      _action = _root == null ? Action.End : Action.Right;
   }

   public bool MoveNext()
   {
      switch (_action)
      {
         case Action.Right:
            _current = _right;

            while (_current.Left != null)
            {
               _current = _current.Left;
            }

            _right = _current.Right;
            _action = _right != null ? Action.Right : Action.Parent;

            return true;

         case Action.Parent:
            while (_current.Parent != null)
            {
               AvlNode previous = _current;

               _current = _current.Parent;

               if (_current.Left == previous)
               {
                  _right = _current.Right;
                  _action = _right != null ? Action.Right : Action.Parent;

                  return true;
               }
            }

            _action = Action.End;

            return false;

         default:
            return false;
      }
   }

   public void Reset()
   {
      _right = _root;
      _action = _root == null ? Action.End : Action.Right;
   }

   public TValue Current
   {
      get
      {
         return _current.Value;
      }
   }

   object IEnumerator.Current
   {
      get
      {
         return Current;
      }
   }

   public void Dispose()
   {
   }

   enum Action
   {
      Parent,
      Right,
      End
   }
}

Finally here's the Search method:

public bool Search(TKey key, out TValue value)
{
   AvlNode node = _root;

   while (node != null)
   {
      if (_comparer.Compare(key, node.Key) < 0)
      {
         node = node.Left;
      }
      else if (_comparer.Compare(key, node.Key) > 0)
      {
         node = node.Right;
      }
      else
      {
         value = node.Value;

         return true;
      }
   }

   value = default(TValue);

   return false;
}

And the Clear method:

public void Clear()
{
   _root = null;
}

So there you have it, a complete AVL tree that doesn't use recursion and is a whole lot faster for it! I hope you enjoy it, this one took me a while figure out but it was worth it. I also wrote a lot of tests to ensure the code is rock solid.

Source code on github