AVL tree performance in C #

Question

AVL tree performance in C #

I 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 the performance good for the AVL tree or do I need to revise the algorithm or code refactoring?

Edit: Elements are integers from 0 to # elements The 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 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 right child has no left child, then current 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 right child has a left child, replace current with current's
                //          right child 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;
        }
    }

+1

performance .net data-structures avl-tree

Anindya chatterjee Sep 08 '10 at 13:49

source share

2 answers

100/500 1000/5000, ( ) 5- . , O (n) O (nlogn).

5.000 10.000, 5- . .

, . , , .

, , () node. AVL ( ).

+2

Henk Holterman 08 . '10 14:10

LBushkin · Accepted Answer · 2010-09-08T14:47:24+0000

The Benchmarking code in .NET requires you to take JIT compile time into account. The easiest way to do this is to check that your test code runs the code twice and discards the first synchronization results.

- , -, , O (log n) AVL-.

, , BinaryTreeNode<>. , - , Depth ToEnumerable.

AVL tree performance in C #

AVLTree

More articles: