Performance d'un arbre AVL en C #

Question

I ai mis en place un arbre AVL en C # insertion dont la matrice est la suivante

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

Maintenant, ma question est, est-il une bonne performance pour un arbre AVL ou dois-je à nouveau envisager de modifier l'algorithme ou refactorisation du code?

---

Edit: Les éléments commencent entier de 0 à #of éléments Le code de test est comme suit

   [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: Code de mise en œuvre

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

Code Benchmarking dans .NET exige que vous prenez en compte le temps de compilation JIT. La meilleure façon de le faire, est d'avoir votre code de test exécuter le code deux fois -. Et jeter les premiers résultats de synchronisation

A part ça -. Vos résultats de référence semblent impliquer un taux de croissance pire que le O attendu (log n) pour l'insertion d'arbre AVL

Ce que vous ne l'avez pas affiché ici est le code pour la classe BinaryTreeNode<>. Je soupçonne que vous pourriez avoir un problème dans la mise en œuvre de certaines des méthodes là-bas - je suis particulièrement méfiant des propriétés comme Depth et ToEnumerable

.

Answer 2

Si je regarde 100/500 et je vois 1000/5000 (très gros) une augmentation de 5 fois dans le temps. Impossible de dire si cela est O (n) ou O (n log n).

Mais quand je regarde et 10.000 5,000 Je vois aussi une augmentation de près de 5 fois. Cela me fait douter de votre code d'étalonnage.

De toute façon, sans le code c'est à peine une vraie question. À tout le moins montrent comment vous avez mesuré.

---

Way trop de code, mais je suppose que c'est votre (itérative) façon de déterminer l'équilibre dans un nœud. arbres traditionnels AVL cache dans ce membre (et le maintenir à jour).