Immutable and very fast AVL based HashTree in C#

HashTree.cs

/// <summary>Delegate for changing value from old one to some new based on provided new value.</summary>
/// <typeparam name="V">Type of values.</typeparam>
/// <param name="oldValue">Existing value.</param>
/// <param name="newValue">New value passed to Update.. method.</param>
/// <returns>Changed value.</returns>
public delegate V Update<V>(V oldValue, V newValue);

/// <summary>Immutable http://en.wikipedia.org/wiki/AVL_tree where actual node key is hash code of <typeparamref name="K"/>.</summary>
/// <remarks>Does not support Remove, though it easy to implement based on Eric Lippert's http://blogs.msdn.com/b/ericlippert/archive/2008/01/21/immutability-in-c-part-nine-academic-plus-my-avl-tree-implementation.aspx.
/// You may emulate Remove by updating key value to null.
/// </remarks>
public sealed class HashTree<K, V>
{
    /// <summary>Empty tree to start with. The <see cref="Height"/> of the empty tree is 0.</summary>
    public static readonly HashTree<K, V> Empty = new HashTree<K, V>();

    /// <summary>Key of type K that should support <see cref="object.Equals(object)"/> and <see cref="object.GetHashCode"/>.</summary>
    public readonly K Key;

    /// <summary>Value of any type V.</summary>
    public readonly V Value;

    /// <summary>Hash calculated from <see cref="Key"/> with <see cref="object.GetHashCode"/>. Hash is stored to improve speed.</summary>
    public readonly int Hash;

    /// <summary>In case of <see cref="Hash"/> conflicts for different keys contains conflicted keys with their values.</summary>
    public readonly KV<K, V>[] Conflicts;

    /// <summary>Left subtree/branch, or empty.</summary>
    public readonly HashTree<K, V> Left;

    /// <summary>Right subtree/branch, or empty.</summary>
    public readonly HashTree<K, V> Right;

    /// <summary>Height of longest subtree/branch. It is 0 for empty tree, and 1 for single node tree.</summary>
    public readonly int Height;

    /// <summary>Returns true is tree is empty.</summary>
    public bool IsEmpty { get { return Height == 0; } }

    /// <summary>Returns new tree with added key-value. If value with the same key is exist, then
    /// if <paramref name="update"/> is not specified: then existing value will be replaced by <paramref name="value"/>;
    /// if <paramref name="update"/> is specified: then update delegate will decide what value to keep.</summary>
    /// <param name="key">Key to add.</param><param name="value">Value to add.</param>
    /// <param name="update">(optional) Delegate to decide what value to keep: old or new one.</param>
    /// <returns>New tree with added or updated key-value.</returns>
    public HashTree<K, V> AddOrUpdate(K key, V value, Update<V> update = null)
    {
        return AddOrUpdate(key.GetHashCode(), key, value, update, updateOnly: false);
    }

    /// <summary>Looks for <paramref name="key"/> and replaces its value with new <paramref name="value"/>, or 
    /// it may use <paramref name="update"/> for more complex update logic. Returns new tree with updated value,
    /// or the SAME tree if key is not found.</summary>
    /// <param name="key">Key to look for.</param>
    /// <param name="value">New value to replace key value with.</param>
    /// <param name="update">(optional) Delegate for custom update logic, it gets old and new <paramref name="value"/>
    /// as inputs and should return updated value as output.</param>
    /// <returns>New tree with updated value or the SAME tree if no key found.</returns>
    public HashTree<K, V> Update(K key, V value, Update<V> update = null)
    {
        return AddOrUpdate(key.GetHashCode(), key, value, update, updateOnly: true);
    }
    
    /// <summary>Searches for key in tree and returns the value if found, or <paramref name="defaultValue"/> otherwise.</summary>
    /// <param name="key">Key to look for.</param> <param name="defaultValue">Value to return if key is not found.</param>
    /// <returns>Found value or <paramref name="defaultValue"/>.</returns>
    public V GetValueOrDefault(K key, V defaultValue = default(V))
    {
        var t = this;
        var hash = key.GetHashCode();
        while (t.Height != 0 && t.Hash != hash)
            t = hash < t.Hash ? t.Left : t.Right;
        return t.Height != 0 && (ReferenceEquals(key, t.Key) || key.Equals(t.Key))
            ? t.Value : t.GetConflictedValueOrDefault(key, defaultValue);
    }

    /// <summary>Depth-first in-order traversal as described in http://en.wikipedia.org/wiki/Tree_traversal
    /// The only difference is using fixed size array instead of stack for speed-up (~20% faster than stack).</summary>
    /// <returns>Sequence of enumerated key value pairs.</returns>
    public IEnumerable<KV<K, V>> Enumerate()
    {
        if (Height == 0)
            yield break;

        var parents = new HashTree<K, V>[Height];

        var tree = this;
        var parentCount = -1;
        while (tree.Height != 0 || parentCount != -1)
        {
            if (tree.Height != 0)
            {
                parents[++parentCount] = tree;
                tree = tree.Left;
            }
            else
            {
                tree = parents[parentCount--];
                yield return new KV<K, V>(tree.Key, tree.Value);

                if (tree.Conflicts != null)
                    for (var i = 0; i < tree.Conflicts.Length; i++)
                        yield return tree.Conflicts[i];

                tree = tree.Right;
            }
        }
    }

    #region Implementation

    private HashTree() { }

    private HashTree(int hash, K key, V value, KV<K, V>[] conficts, HashTree<K, V> left, HashTree<K, V> right)
    {
        Hash = hash;
        Key = key;
        Value = value;
        Conflicts = conficts;
        Left = left;
        Right = right;
        Height = 1 + (left.Height > right.Height ? left.Height : right.Height);
    }

    private HashTree<K, V> AddOrUpdate(int hash, K key, V value, Update<V> update, bool updateOnly)
    {
        return Height == 0 ? (updateOnly ? this : new HashTree<K, V>(hash, key, value, null, Empty, Empty))
            : (hash == Hash ? UpdateValueAndResolveConflicts(key, value, update, updateOnly)
            : (hash < Hash
                ? With(Left.AddOrUpdate(hash, key, value, update, updateOnly), Right)
                : With(Left, Right.AddOrUpdate(hash, key, value, update, updateOnly))).KeepBalanced());
    }

    private HashTree<K, V> UpdateValueAndResolveConflicts(K key, V value, Update<V> update, bool updateOnly)
    {
        if (ReferenceEquals(Key, key) || Key.Equals(key))
            return new HashTree<K, V>(Hash, key, update == null ? value : update(Value, value), Conflicts, Left, Right);

        if (Conflicts == null) // add only if updateOnly is false.
            return updateOnly ? this
                : new HashTree<K, V>(Hash, Key, Value, new[] { new KV<K, V>(key, value) }, Left, Right);

        var found = Conflicts.Length - 1;
        while (found >= 0 && !Equals(Conflicts[found].Key, Key)) --found;
        if (found == -1)
        {
            if (updateOnly) return this;
            var newConflicts = new KV<K, V>[Conflicts.Length + 1];
            Array.Copy(Conflicts, 0, newConflicts, 0, Conflicts.Length);
            newConflicts[Conflicts.Length] = new KV<K, V>(key, value);
            return new HashTree<K, V>(Hash, Key, Value, newConflicts, Left, Right);
        }

        var conflicts = new KV<K, V>[Conflicts.Length];
        Array.Copy(Conflicts, 0, conflicts, 0, Conflicts.Length);
        conflicts[found] = new KV<K, V>(key, update == null ? value : update(Conflicts[found].Value, value));
        return new HashTree<K, V>(Hash, Key, Value, conflicts, Left, Right);
    }

    private V GetConflictedValueOrDefault(K key, V defaultValue)
    {
        if (Conflicts != null)
            for (var i = 0; i < Conflicts.Length; i++)
                if (Equals(Conflicts[i].Key, key))
                    return Conflicts[i].Value;
        return defaultValue;
    }

    private HashTree<K, V> KeepBalanced()
    {
        var delta = Left.Height - Right.Height;
        return delta >= 2 ? With(Left.Right.Height - Left.Left.Height == 1 ? Left.RotateLeft() : Left, Right).RotateRight()
            : (delta <= -2 ? With(Left, Right.Left.Height - Right.Right.Height == 1 ? Right.RotateRight() : Right).RotateLeft()
            : this);
    }

    private HashTree<K, V> RotateRight()
    {
        return Left.With(Left.Left, With(Left.Right, Right));
    }

    private HashTree<K, V> RotateLeft()
    {
        return Right.With(With(Left, Right.Left), Right.Right);
    }

    private HashTree<K, V> With(HashTree<K, V> left, HashTree<K, V> right)
    {
        return left == Left && right == Right ? this : new HashTree<K, V>(Hash, Key, Value, Conflicts, left, right);
    }

    #endregion
}