Immutable AVL Tree in C#

I recently decided that I needed an immutable dictionary but after some experimentation decided that wasn’t as easy as it sounded. After doing some searching online I came to the conclusion that the most reasonable alternative was to implement an immutable AVL Tree where the nodes were key/value pairs.

The AVL Tree has O(log N) lookup and insertion times, which means at most it will look at nodes equal to the depth of the tree and the tree is strictly balanced at all times. Surprisingly, I had a hard time finding a really clear example online in a language. So I would like to post my solution here since I feel like it’s reasonably clean and terse (insertion only so far).

The trick to understanding AVL trees is to understand that the tree is to always remain balanced. Which is to say that the height of any Left branch of a node should at most be no more than 1 higher than the Height of its Right branch. If you find that the height difference is 2 or –2 then you have an imbalanced tree. This is expressed in the Add method after insertion like so:

var lh = n.Left == null ? 0 : n.Left.Height;
var rh = n.Right == null ? 0 : n.Right.Height;
var b = lh - rh;

if (Math.Abs(b) == 2) // 2 or -2 means unbalanced
{
  // rebalance
}

If the value is 2 then your Left branch is unbalanced if the value is –2 then the Right branch is unbalanced.

if (Math.Abs(b) == 2) // 2 or -2 means unbalanced
{
    if (b == 2) // L
    {
        // balance Left branch
    }
    else // R
    {
        // balance Right branch
    }
}

The next thing to do is to check the balance of the unbalanced branch, who’s balance should be either 1 or –1, like in the case of an unbalanced Left branch below:

var llh = n.Left.Left == null ? 0 : n.Left.Left.Height;
var lrh = n.Left.Right == null ? 0 : n.Left.Right.Height;
var lb = llh - lrh;
if (lb == 1) // LL
{
    // rotate right
}
else // LR
{
    // rotate left // rotate right
}

So given this there are actually four cases we need to cover for any tree:

And the solution to rebalance the tree is to “rotate” the nodes, in the cases of LL and RR you only need to rotate the unbalanced Right or Left branch but in the case of LR or RL you need to rotate twice, first the branch then the node itself. Here is the matching table for the rotations:

It took me a while to understand it but the Wikipedia article actually has a pretty good diagram showing these rotations.

Here is the Left and Right rotation algorithms in C# (complete with awesome ascii art comments!):

private static Node<TKey, TValue> RotateRight(Node<TKey, TValue> node)
{ 
    //       (5)            4     
    //       / \           / \    
    //      4   D         /   \   
    //     / \           3     5  
    //    3   C    -->  / \   / \ 
    //   / \           A   B C   D
    //  A   B                     
    
    var L = node.Left.Left;
    var R = new Node<TKey, TValue>(node.Key, node.Value, node.Left.Right, node.Right);
    var N = new Node<TKey, TValue>(node.Left.Key, node.Left.Value, L, R);
    return N;
}

private static Node<TKey, TValue> RotateLeft(Node<TKey, TValue> node)
{ 
    //    (3)               4     
    //    / \              / \    
    //   A   4            /   \   
    //      / \          3     5  
    //     B   5   -->  / \   / \ 
    //        / \      A   B C   D
    //       C   D                      
    
    var L = new Node<TKey, TValue>(node.Key, node.Value, node.Left, node.Right.Left);
    var R = node.Right.Right;
    var N = new Node<TKey, TValue>(node.Right.Key, node.Right.Value, L, R);
    return N;
}

Notice that we’re always creating new nodes rather than mutating the existing nodes. This is crucial to maintain immutability. These trees can now be safely used across threads since their states are never mutated.

Download the full sample: Map.zip

Author: justinmchase

I'm a Software Developer from Minnesota. View all posts by justinmchase