Performance of an AVL Tree in C#

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)
        {
     开发者_如何学JAVA   }


        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;
        }
    }

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).

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.