Performance of an AVL Tree in C#

Question

I have implemented an AVL tree in C# whose insertion matrix is as follows

Number of Elements          Time taken to insert (sec)
------------------------------------------------------
10                        0.067
100                       0.073
200                       0.112
500                       0.388
900                       1.205
1000                          1.466
5000                         44.314
10000                       195.435

Now my question is, is it a good performance for an AVL tree or do I have to re-consider changing the algorithm or refactoring the code?

---

Edit: The elements are integer starting from 0 to #of elements Test code is as follows

   [Test]
    public void InsertionTest()
    {
        AVLTree<int> _tree = new AVLTree<int>();
        _stopWatch.Start();
        for (int i = 0; i < 5000; i++) {
            _tree.Add(i);
        }
        _stopWatch.Stop();

        Console.WriteLine("Time taken = " + _stopWatch.Elapsed);
    }   

---

Edit: Implementation code

BinarySearchTree

[Serializable]
    public class BinarySearchTree<T> : ICollection<T>
    {
        private readonly Comparer<T> _comparer = Comparer<T>.Default;

        public BinarySearchTree()
        {
        }

        public BinarySearchTree(IEnumerable<T> collection)
        {
            AddRange(collection.ToArray());
        }

        public BinarySearchTree(Comparer<T> comparer)
        {
            _comparer = comparer;
        }

        public BinaryTreeNode<T> Root { get; protected set; }

        #region ICollection<T> Members

        /// <summary>
        ///   Adds an item to the <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        /// <param name = "value">The object to add to the <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </param>
        /// <exception cref = "T:System.NotSupportedException">The <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only.
        /// </exception>
        public virtual void Add(T value)
        {
            var n = new BinaryTreeNode<T>(value);
            int result;

            BinaryTreeNode<T> current = Root, parent = null;
            while (current != null)
            {
                result = _comparer.Compare(current.Value, value);
                if (result == 0)
                {
                    parent = current;
                    current = current.Left;
                }
                if (result > 0)
                {
                    parent = current;
                    current = current.Left;
                }
                else if (result < 0)
                {
                    parent = current;
                    current = current.Right;
                }
            }

            Count++;
            if (parent == null)
                Root = n;
            else
            {
                result = _comparer.Compare(parent.Value, value);
                if (result > 0)
                    parent.Left = n;
                else
                    parent.Right = n;
            }
        }

        /// <summary>
        ///   Removes all items from the <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        /// <exception cref = "T:System.NotSupportedException">The <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only. 
        /// </exception>
        public void Clear()
        {
            Root = null;
            Count = 0;
        }

        /// <summary>
        ///   Determines whether the <see cref = "T:System.Collections.Generic.ICollection`1" /> contains a specific value.
        /// </summary>
        /// <returns>
        ///   true if <paramref name = "item" /> is found in the <see cref = "T:System.Collections.Generic.ICollection`1" />; otherwise, false.
        /// </returns>
        /// <param name = "item">The object to locate in the <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </param>
        public virtual bool Contains(T item)
        {
            BinaryTreeNode<T> current = Root;
            while (current != null)
            {
                int result = _comparer.Compare(current.Value, item);
                if (result == 0)
                    return true;
                if (result > 0)
                    current = current.Left;
                else if (result < 0)
                    current = current.Right;
            }

            return false;
        }

        public void CopyTo(T[] array, int index)
        {
            CopyTo(array, index, BinaryTreeTraversalType.InOrder);
        }

        /// <summary>
        ///   Removes the first occurrence of a specific object from the <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        /// <returns>
        ///   true if <paramref name = "item" /> was successfully removed from the <see cref = "T:System.Collections.Generic.ICollection`1" />; otherwise, false. This method also returns false if <paramref name = "item" /> is not found in the original <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </returns>
        /// <param name = "item">The object to remove from the <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </param>
        /// <exception cref = "T:System.NotSupportedException">The <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only.
        /// </exception>
        public virtual bool Remove(T item)
        {
            if (Root == null)
                return false;

            BinaryTreeNode<T> current = Root, parent = null;
            int result = _comparer.Compare(current.Value, item);
            while (result != 0)
            {
                if (result > 0)
                {
                    parent = current;
                    current = current.Left;
                }
                else if (result < 0)
                {
                    parent = current;
                    current = current.Right;
                }

                if (current == null)
                    return false;
                result = _comparer.Compare(current.Value, item);
            }

            Count--;

            // We now need to "rethread" the tree
            // CASE 1: If current has no right child, then current's left child becomes
            //         the node pointed to by the parent
            if (current.Right == null)
            {
                if (parent == null)
                    Root = current.Left;
                else
                {
                    result = _comparer.Compare(parent.Value, current.Value);
                    if (result > 0)
                        parent.Left = current.Left;
                    else if (result < 0)
                        parent.Right = current.Left;
                }

                // CASE 2: If current's right child has no left child, then current's right child
                //         replaces current in the tree
            }
            else if (current.Right.Left == null)
            {
                current.Right.Left = current.Left;

                if (parent == null)
                    Root = current.Right;
                else
                {
                    result = _comparer.Compare(parent.Value, current.Value);
                    if (result > 0)
                        parent.Left = current.Right;
                    else if (result < 0)
                        parent.Right = current.Right;
                }

                // CASE 3: If current's right child has a left child, replace current with current's
                //          right child's left-most descendent
            }
            else
            {
                BinaryTreeNode<T> leftmost = current.Right.Left, lmParent = current.Right;
                while (leftmost.Left != null)
                {
                    lmParent = leftmost;
                    leftmost = leftmost.Left;
                }

                lmParent.Left = leftmost.Right;

                leftmost.Left = current.Left;
                leftmost.Right = current.Right;

                if (parent == null)
                    Root = leftmost;
                else
                {
                    result = _comparer.Compare(parent.Value, current.Value);
                    if (result > 0)
                        parent.Left = leftmost;
                    else if (result < 0)
                        parent.Right = leftmost;
                }
            }

            current.Left = current.Right = null;

            return true;
        }

        /// <summary>
        ///   Gets the number of elements contained in the <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </summary>
        /// <returns>
        ///   The number of elements contained in the <see cref = "T:System.Collections.Generic.ICollection`1" />.
        /// </returns>
        public int Count { get; private set; }

        /// <summary>
        ///   Gets a value indicating whether the <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only.
        /// </summary>
        /// <returns>
        ///   true if the <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only; otherwise, false.
        /// </returns>
        public bool IsReadOnly
        {
            get { return false; }
        }

        #endregion

        public void AddRange(IEnumerable<T> items)
        {
            foreach (var item in items)
            {
                Add(item);
            }
        }

        public void CopyTo(T[] array, int index, BinaryTreeTraversalType traversalType)
        {
            Root.ToEnumerable(traversalType).Select(x => x.Value).ToArray().CopyTo(array, index);
        }

        public BinaryTreeNode<T> Find(T value)
        {
            BinaryTreeNode<T> current = Root;
            while (current != null)
            {
                int result = _comparer.Compare(current.Value, value);
                if (result == 0)
                    return current;
                if (result > 0)
                    current = current.Left;
                else if (result < 0)
                    current = current.Right;
            }

            return null;
        }

        #region Implementation of IEnumerable

        /// <summary>
        ///   Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        ///   A <see cref = "T:System.Collections.Generic.IEnumerator`1" /> that can be used to iterate through the collection.
        /// </returns>
        /// <filterpriority>1</filterpriority>
        public IEnumerator<T> GetEnumerator()
        {
            return Root.ToEnumerable(BinaryTreeTraversalType.InOrder).Select(x => x.Value).GetEnumerator();
        }

        /// <summary>
        ///   Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns>
        ///   An <see cref = "T:System.Collections.IEnumerator" /> object that can be used to iterate through the collection.
        /// </returns>
        /// <filterpriority>2</filterpriority>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion
    }

---

AVLTree

public class AVLTree<T> : BinarySearchTree<T>
    {
        public AVLTree()
        {
        }

        public AVLTree(IEnumerable<T> collection)
            : base(collection)
        {
        }

        public AVLTree(Comparer<T> comparer)
            : base(comparer)
        {
        }


        public override void Add(T value)
        {
            base.Add(value);
            var node = Find(value);

            AbstractNode<T> parentNode = node.Parent;

            while (parentNode != null)
            {
                int balance = GetBalance(parentNode as BinaryTreeNode<T>);
                if (Math.Abs(balance) == 2)
                {
                    BalanceAt(parentNode as BinaryTreeNode<T>, balance);
                }

                parentNode = parentNode.Parent;
            }
        }

        public override bool Remove(T item)
        {
            if (Root == null)
                return false;

            BinaryTreeNode<T> valueNode = Find(item);
            AbstractNode<T> parentNode = valueNode.Parent;

            bool removed = base.Remove(item);

            if (!removed)
                return false;

            while (parentNode != null)
            {
                int balance = GetBalance(parentNode as BinaryTreeNode<T>);

                if (Math.Abs(balance) == 1)
                    break;
                if (Math.Abs(balance) == 2)
                {
                    BalanceAt(parentNode as BinaryTreeNode<T>, balance);
                }

                parentNode = parentNode.Parent;
            }

            return true;
        }

        /// <summary>
        /// Balances an AVL Tree node
        /// </summary>
        protected virtual void BalanceAt(BinaryTreeNode<T> node, int balance)
        {
            if (balance == 2)
            {
                int rightBalance = GetBalance(node.Right);

                if (rightBalance == 1 || rightBalance == 0)
                {
                    RotateLeft(node);
                }
                else if (rightBalance == -1)
                {
                    RotateRight(node.Right);
                    RotateLeft(node);
                }
            }
            else if (balance == -2)
            {
                int leftBalance = GetBalance(node.Left);
                if (leftBalance == 1)
                {
                    RotateLeft(node.Left);
                    RotateRight(node);
                }
                else if (leftBalance == -1 || leftBalance == 0)
                {
                    RotateRight(node);
                }
            }
        }

        /// <summary>
        /// Determines the balance of a given node
        /// </summary>
        protected virtual int GetBalance(BinaryTreeNode<T> node)
        {
            if(node != null)
            {
                IEnumerable<BinaryTreeNode<T>> leftSubtree = null, righSubtree = null;

                if (node.Left != null)
                    leftSubtree = node.Left.ToEnumerable(BinaryTreeTraversalType.InOrder);

                if (node.Right != null)
                    righSubtree = node.Right.ToEnumerable(BinaryTreeTraversalType.InOrder);

// ReSharper disable AssignNullToNotNullAttribute
                var leftHeight = leftSubtree.IsNullOrEmpty() ? 0 : leftSubtree.Max(x => x.Depth) - node.Depth;
                var righHeight = righSubtree.IsNullOrEmpty() ? 0 : righSubtree.Max(x => x.Depth) - node.Depth;
// ReSharper restore AssignNullToNotNullAttribute

                return righHeight - leftHeight;
            }
            return 0;            
        }

        /// <summary>
        /// Rotates a node to the left within an AVL Tree
        /// </summary>
        protected virtual void RotateLeft(BinaryTreeNode<T> node)
        {
            if (node == null)
                return;

            BinaryTreeNode<T> pivot = node.Right;

            if (pivot == null)
                return;
            var rootParent = node.Parent as BinaryTreeNode<T>;
            bool isLeftChild = (rootParent != null) && rootParent.Left == node;
            bool makeTreeRoot = node == Root;

            node.Right = pivot.Left;
            pivot.Left = node;

            node.Parent = pivot;
            pivot.Parent = rootParent;

            if (node.Right != null)
                node.Right.Parent = node;

            if (makeTreeRoot)
                Root = pivot;

            if (isLeftChild)
                rootParent.Left = pivot;
            else if (rootParent != null)
                rootParent.Right = pivot;
        }

        /// <summary>
        /// Rotates a node to the right within an AVL Tree
        /// </summary>
        protected virtual void RotateRight(BinaryTreeNode<T> node)
        {
            if (node == null)
                return;

            BinaryTreeNode<T> pivot = node.Left;

            if (pivot == null)
                return;
            var rootParent = node.Parent as BinaryTreeNode<T>;
            bool isLeftChild = (rootParent != null) && rootParent.Left == node;
            bool makeTreeRoot = Root == node; 

            node.Left = pivot.Right;
            pivot.Right = node;

            node.Parent = pivot;
            pivot.Parent = rootParent;

            if (node.Left != null)
                node.Left.Parent = node;

            if (makeTreeRoot)
                Root = pivot;
            if (isLeftChild)
                rootParent.Left = pivot;
            else if (rootParent != null)
                rootParent.Right = pivot;
        }
    }

Answer 1

Benchmarking code in .NET requires that you take into account JIT compilation time. The easiest way to do this, is to have your test code run the code twice - and discard the first timing results.

That aside - your benchmark results seem to imply a growth rate worse than the expected O(log n) time for AVL tree insertion.

What you haven't posted here is the code for the BinaryTreeNode<> class. I suspect you may have a problem in the implementation of some of the methods there - I'm particularly suspicious of properties like Depth and ToEnumerable.

Answer 2

If I look at 100/500 and 1000/5000 I see (very roughly) a 5x increase in time. Not possible to say if this is O(n) or O(nlogn).

But when I look at 5.000 and 10.000 I see also an almost 5x increase. This makes me doubt your benchmarking code.

Anyway, without code this is hardly a real question. At the very least show how you measured.

---

Way too much code but I would guess it is your (iterative) way of determining the balance in a node. Traditional AVL trees cache this in a member (and keep it up to date).