AVL 14.04

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AVLTree_03._03._23
{
    public class AVLTree<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>> where TKey : IComparable<TKey>
    {
        bool flagIfAddSecond;
        public int Count { get; private set; }
        private Node<TKey, TValue> _root; //корень

        public AVLTree()
        {
            Count = 0;
        }
        //private int FindHightTheTree(Node<TKey, TValue> root)
        //{
        //    if (root == null) { return 0; }
        //    int hight = 0;
        //    Queue<Node<TKey, TValue>> queue = new Queue<Node<TKey, TValue>>();
        //    queue.Enqueue(root);
        //    while (queue.Count > 0)
        //    {
        //        int countQue = queue.Count;
        //        for (int i = countQue; i != 0; i--)
        //        {
        //            var current = queue.Dequeue();
        //            if (current.Left != null)
        //            {
        //                queue.Enqueue(current.Left);
        //            }
        //            if (current.Right != null)
        //            {
        //                queue.Enqueue(current.Right);
        //            }
        //        }
        //        hight++;
        //    }
        //    return hight;
        //}
        public void Add(TKey key, TValue value)
        {
            var node = new Node<TKey, TValue>(key, value);
            if (_root == null)
            {
                _root = node;
                Count++;
                return;
            }
            var current = _root;
            var parent = _root;
            while (current != null)
            {
                parent = current;
                if (current.Key.CompareTo(node.Key) == 0)
                {
                    throw new ArgumentException("Such key is already added");
                }
                if (current.Key.CompareTo(node.Key) > 0)
                {
                    current = current.Left;
                }
                else if (current.Key.CompareTo(node.Key) < 0)
                {
                    current = current.Right;
                }
            }
            if (parent.Key.CompareTo(node.Key) > 0)
            {
                parent.Left = node;
            }
            if (parent.Key.CompareTo(node.Key) < 0)
            {
                parent.Right = node;
            }
            node.Parent = parent;
            Count++;
            Balancing(parent);
        }

        public bool Delete(TKey key)
        {
            var node = FindElem(key);
            //Удаление
            if (node != null)
            {
                Node<TKey,TValue> BalancingNode = node.Parent;
                Count--;
                var nodeLeft = node.Left; var nodeRight = node.Right; var nodeParent = node.Parent;
                // если нет детей - узел удаляется
                if (nodeLeft == null && nodeRight == null)
                {
                    if (nodeParent != null)//не корень
                    {
                        if (nodeParent.Left == node) nodeParent.Left = null;
                        else nodeParent.Right = null;
                    }
                    else if(nodeParent == null)
                    {
                        _root = null;
                    }

                }
                else if(nodeLeft != null && nodeRight == null)//Один ребенок слева
                {
                    if(nodeParent == null)//корень
                    {
                        nodeLeft.Parent = null;
                        _root = nodeLeft;
                    }
                    else//не корень
                    {
                        nodeLeft.Parent = node.Parent;
                        nodeLeft.Parent.Left = nodeLeft;
                    }
                }
                else if(nodeLeft == null && nodeRight != null)//Один ребенок справа
                {
                    if (nodeParent == null)//корень
                    {
                        nodeRight.Parent = null;
                        _root = nodeRight;
                    }
                    else//не корень
                    {
                        nodeRight.Parent = node.Parent;
                        nodeRight.Parent.Left = nodeRight;
                    }
                }
                else if (nodeLeft != null && nodeRight != null)//Два ребенка
                {
                    // ищем замену - самый левый из элементов правого поддерева
                    var current = nodeRight;
                    while (current.Left != null)
                    {
                        current = current.Left;
                    }
                    var minelement = current;
                    BalancingNode = minelement.Parent;
                    if (minelement.Right != null)//Работа с удалением minelement
                    {
                        minelement.Right.Parent = minelement.Parent;
                        if (minelement.Parent == node)//Если минимальный элемент сразу справа от нода и у него есть ребёнок справа
                        {
                            minelement.Parent.Right = minelement.Right;
                        }
                        else minelement.Parent.Left = minelement.Right;
                    }
                    else
                    {
                        if(minelement.Parent.Right == minelement)
                        {
                            minelement.Parent.Right = null;
                        }
                        else
                        {
                            minelement.Parent.Left = null;
                        }
                    }

                    if(minelement.Parent == node)
                    {

                        minelement.Parent = node.Parent;
                        if(node.Parent.Left == node)
                        {
                            node.Parent.Left = minelement;
                        }
                        else node.Parent.Right = minelement;
                        minelement.Left = node.Left;
                        minelement.Right = node.Right;
                        BalancingNode = minelement;
                    }
                    else
                    {
                        minelement.Left = nodeLeft; nodeLeft.Parent = minelement;
                        minelement.Right = nodeRight; nodeRight.Parent = minelement;
                        minelement.Parent = node.Parent;
                        if (nodeParent == null)//корень
                        {
                            _root = minelement;
                            _root.UpdateHeight();
                        }
                    }

                }
                Balancing(BalancingNode);
                return true;
            }
            else
            {
                return false;
                //throw new ArgumentException("No such element in tree");
            }
        }
        public bool Contains(TKey key, TValue value)
        {
            // Поиск узла осуществляется другим методом.
            return FindElem(key) != null;
        }
        private void Balancing(Node<TKey, TValue> node)
        {
            while (node != null)
            {
                node.UpdateHeight();
                //int HightLeft = node.Left.Height; int HightRight = node.Right.Height;
                int nodeBF = node.BalanceFactor();
                if (Math.Abs(nodeBF) == 2)//тогда балансим
                {
                    if(nodeBF < 0)//Левые повороты
                    {
                        if (node.Right.BalanceFactor() <= 0)//левый малый поворот
                        {
                            LeftSmallTurn(node);
                        }
                        else if (node.Right.BalanceFactor() > 0)//левый большой поворот
                        {
                            LeftBigTurn(node);
                        }
                    }
                    else if(nodeBF > 0)//Правые повороты
                    {
                        if (node.Left.BalanceFactor() >= 0)//правый малый поворот
                        {
                            RightSmallTurn(node);
                        }
                        else if (node.Left.BalanceFactor() < 0)//правый большой поворот
                        {
                            RightBigTurn(node);
                        }
                    }
                }
                node = node.Parent;
            }
        }
        private void LeftSmallTurn(Node<TKey, TValue> node)
        {
            /*
             *             A*                       B
             *           /   \                    /   \
             *          L      B        -->      A     R
             *               /   \             /   \
             *              C     R           L     C
             */
            var A = node;
            var B = node.Right;
            var C = B.Left;

            A.Right = C;
            if(C != null) C.Parent = A;
            B.Left = A;
            B.Parent = A.Parent;
            if (A.Parent != null)//Если не корень, то привязываем родителя к получившейся верхушке
            {
                if (A.Parent.Left == A)//Если А слева от своего родителя
                {
                    A.Parent.Left = B;
                }
                else //Если А справа от своего родителя
                {
                    A.Parent.Right = B;
                }
                A.Parent = B;
            }
            else _root = B;
            A.UpdateHeight();
            B.UpdateHeight();
        }
        private void RightSmallTurn(Node<TKey, TValue> node)
        {
            /*
             *            |                 |
            *             A*                B
            *           /   \             /   \
            *          B     R   -->     L     A
            *        /   \                   /   \
            *       L     C                 C     R
            */
            var A = node;
            var B = A.Left;
            var C = B.Right;
            var L = B.Left;
            var R = A.Right;

            B.Right = A;
            A.Left = C;
            if(C != null) C.Parent = A;
            B.Parent = A.Parent;
            if (A.Parent != null)//Если не корень, то привязываем родителя к получившейся верхушке
            {
                if (A.Parent.Left == A)//Если А слева от своего родителя
                {
                    A.Parent.Left = B;
                }
                else //Если А справа от своего родителя
                {
                    A.Parent.Right = B;
                }
                A.Parent = B;
            }
            else _root = B;
            A.UpdateHeight();
            B.UpdateHeight();
        }
        private void LeftBigTurn(Node<TKey, TValue> node)
        {
            /*
             *          A                      A                        C
             *        /   \                  /   \                   /     \
             *       L     B                L     С                 A       B
             *           /   \      -->         /   \       -->   /   \   /   \
             *          C     R                M     B           L    M  N     R
             *        /   \                        /   \
             *       M     N                      N     R
             */
            var A = node;
            var B = node.Right;
            var C = B.Left;
            //var L = A.Left;
            //var M = C.Left;
            var N = C.Right;
            //var R = B.Right;

            B.Left = N;
            if (N != null)
            {
                N.Parent = B;
            }
            C.Right = B;
            B.Parent = C;
            A.Right = C;
            C.Parent = A;
            A.UpdateHeight();
            B.UpdateHeight();
            C.UpdateHeight();
            LeftSmallTurn(A);
        }
        private void RightBigTurn(Node<TKey, TValue> node)
        {
            /*
            *          A                     A                   C
            *        /   \                 /   \              /     \
            *       B     R               C     R            B       A
            *     /   \         -->     /   \       -->    /   \   /   \
            *    L     C               B     N            L     M N     R
            *        /   \           /   \
            *       M     N         L     M
            */
            var A = node;
            var B = node.Left;
            var C = B.Right;
            //var L = B.Left;
            var M = C.Left;
            //var N = C.Right;
            //var R = A.Right;

            B.Right = M;
            if (M != null)
            {
                M.Parent = B;
            }
            C.Left = B;
            B.Parent = C;
            A.Left = C;
            C.Parent = A;
            A.UpdateHeight();
            B.UpdateHeight();
            C.UpdateHeight();
            RightSmallTurn(A);
        }
        private Node<TKey, TValue> FindElem(TKey findKey)
        {
            // Попробуем найти значение в дереве.
            var current = _root;

            // До тех пор, пока не нашли...
            while (current != null)
            {
                int result = current.Key.CompareTo(findKey);

                if (result > 0)
                {
                    // Если искомое значение меньше, идем налево.
                    current = current.Left;
                }
                else if (result < 0)
                {
                    // Если искомое значение больше, идем направо.
                    current = current.Right;
                }
                else
                {
                    // Если равны, то останавливаемся
                    break;
                }
            }

            return current;
        }
        private Node<TKey, TValue> FindMinElemOnTheRigthPath(Node<TKey, TValue> start)
        {
            while (start.Left != null)
            {
                start = start.Left;
            }
            return start;
        }
        IEnumerable<KeyValuePair<TKey, TValue>> Traverse(Node<TKey, TValue> node)
        {
            var nodes = new List<KeyValuePair<TKey,
            TValue>>();
            if (node != null)
            {
                nodes.AddRange(Traverse(node.Left));
                nodes.Add(new KeyValuePair<TKey, TValue>(node.Key, node.Value));
                nodes.AddRange(Traverse(node.Right));
            }
            return nodes;
        }
        public IEnumerable<KeyValuePair<TKey, TValue>> Traverse()
        {
            return Traverse(_root);
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return Traverse().GetEnumerator();
        }
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return Traverse().GetEnumerator();
        }

    }

}