WorkingButSlowAVL

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>
    {
        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(node);
        }
        private void DeleteIfNoChildrens(Node<TKey, TValue> node)
        {
            if (node.Parent.Left == node)
            {
                node.Parent.Left = null;
            }
            else
            {
                node.Parent.Right = null;
            }
        }
        public void Delete(TKey key)
        {
            var node = FindElem(key);
            var BalancingNode = node.Parent;
            //Удаление
            if (node != null)
            {
                Count--;

                // если нет детей - узел удаляется
                if (node.Left == null && node.Right == null)
                {
                    DeleteIfNoChildrens(node);
                }
                else if (node.Parent == null) //Когда корень
                {
                    if (node.Left != null && node.Right == null)//если один ребенок - слева
                    {
                        _root = node.Left;
                    }
                    else if (node.Left == null && node.Right != null)// если один ребенок - справа
                    {
                        _root = node.Right;
                    }
                    else if (node.Left != null && node.Right != null) // если два ребенка
                    {
                        // ищем замену - самый левый из элементов правого поддерева
                        var current = node.Right;
                        while (current.Left != null)
                        {
                            current = current.Left;
                        }
                        var minelement = current;

                        //Delete(minelement.Key, minelement.Value);
                        if (minelement.Right == null) // если у заместителя нет детей
                        {
                            DeleteIfNoChildrens(minelement);
                        }
                        else { minelement = minelement.Right; }
                        BalancingNode = minelement;
                        // значение узла заместителя переписыввется в удаляемый, а сам заместитель удаляется
                        var tempLeftTree = _root.Left; var tempRightTree = _root.Right;
                        _root = minelement;
                        _root.Parent = null;
                        _root.Left = tempLeftTree; _root.Right = tempRightTree;
                        _root.Left.Parent = _root;
                        _root.Right.Parent = _root;
                    }
                }
                else if (node.Parent != null)//Не корень
                {
                    // если один ребенок - ребенок занимает место удаленного узла
                    if ((node.Left != null && node.Right == null))
                    {
                        var tempparent = node.Parent;
                        node = node.Left;
                        tempparent.Right = node;
                        node.Parent = tempparent;
                    }
                    else if ((node.Left == null && node.Right != null))
                    {
                        var tempparent = node.Parent;
                        node = node.Right;
                        tempparent.Left = node;
                        node.Parent = tempparent;
                    }
                    // если два ребенка -
                    else if (node.Left != null && node.Right != null)
                    {
                        // ищем замену - самый левый из элементов правого поддерева
                        var current = node.Right;
                        while (current.Left != null)
                        {
                            current = current.Left;
                        }
                        var minelement = current;
                        // значение узла заместителя переписыввется в удаляемый, а сам заместитель удаляется
                        Node<TKey, TValue> tempLeftTree = new Node<TKey, TValue>(node.Left.Key, node.Left.Value);
                        tempLeftTree.Left = node.Left.Left; tempLeftTree.Right = node.Left.Right;// Привязка поддеревьев у детей
                        if (FindHightTheTree(node.Right) > 1)
                        {
                            Node<TKey, TValue> tempRightTree = new Node<TKey, TValue>(node.Right.Key, node.Right.Value);
                            tempRightTree.Left = node.Right.Left; tempRightTree.Right = node.Right.Right;
                            minelement.Right = tempRightTree;
                            tempRightTree.Parent = minelement;
                        }
                        //Delete(minelement.Key, minelement.Value);
                        if (minelement.Right == null)
                        {
                            DeleteIfNoChildrens(minelement);
                        }
                        else { minelement = minelement.Right; }
                        BalancingNode = minelement;

                        var tempParent = node.Parent;
                        node.Value = minelement.Value; node.Key = minelement.Key;
                        node.Left = tempLeftTree;
                        tempLeftTree.Parent = node;
                        node.Parent = tempParent;
                    }
                }
            }
            else
            {
                throw new ArgumentException("No such element in tree");
            }
            Balancing(BalancingNode);
            return;
        }
        public bool Contains(TKey key, TValue value)
        {
            // Поиск узла осуществляется другим методом.
            return FindElem(key) != null;
        }
        private void Balancing(Node<TKey, TValue> node)
        {
            while (node != null)
            {
                int HightLeft = FindHightTheTree(node.Left); int HightRight = FindHightTheTree(node.Right);
                if (Math.Abs(HightLeft - HightRight) > 1)//тогда балансим
                {
                    if (HightRight > HightLeft)//если к node мы пришли с правого поддерева node
                    {
                        if (FindHightTheTree(node.Right.Left) <= FindHightTheTree(node.Right.Right))//левый малый поворот
                        {
                            LeftSmallTurn(node);
                        }
                        else//левый большой поворот
                        {
                            LeftBigTurn(node);
                        }
                    }
                    else //if (FindHightTheTree(node.Right) < FindHightTheTree(node.Left))// если к node мы пришли с левого поддерева node
                    {
                        if (FindHightTheTree(node.Left.Right) <= FindHightTheTree(node.Left.Left))//правый малый поворот
                        {
                            RightSmallTurn(node);
                        }
                        else//правый большой поворот
                        {
                            RightBigTurn(node);
                        }
                    }
                }
                node = node.Parent;
            }
        }
        private void LeftSmallTurn(Node<TKey, TValue> node)
        {
            var A = node;
            var B = node.Right;
            var BLeft = B.Left;
            if(BLeft != null)
            {
                BLeft.Parent = null;//?
            }
            //var ParentA = A.Parent;
            if (A.Parent != null)
            {
                if (A.Parent.Left == A)//если балансим слева от родителя node, то вставляем тоже слева
                {
                    B.Parent = A.Parent;
                    A.Parent.Left = B;
                    A.Right = null;
                    B.Left = A;
                    A.Parent = B;
                }
                else if (A.Parent.Right == A)//если балансим справа от родителя node, то вставляем тоже справа
                {
                    B.Parent = A.Parent;
                    A.Parent.Right = B;
                    A.Right = null;
                    B.Left = A;
                    A.Parent = B;
                }
            }
            else//когда корень
            {
                B.Parent = A.Parent;
                A.Right = null;
                B.Left = A;
                _root = B;
                A.Parent = B;
            }
            if (BLeft != null)
            {
                Add(BLeft.Key, BLeft.Value); Count--;
            }
        }
        private void RightSmallTurn(Node<TKey, TValue> node)
        {
            var A = node;
            var B = node.Left;
            var BRight = B.Right;
            if(BRight != null)
            {
                BRight.Parent = null;//?
            }

            if (A.Parent != null)
            {
                if (A.Parent.Left == A)
                {
                    B.Parent = A.Parent;
                    A.Parent.Left = B;
                    A.Left = null;
                    B.Right = A;
                    A.Parent = B;
                }
                else if (A.Parent.Right == A)
                {
                    B.Parent = A.Parent;
                    A.Parent.Right = B;
                    A.Left = null;
                    B.Right = A;
                    A.Parent = B;
                }
            }
            else
            {
                B.Parent = A.Parent;
                A.Left = null;
                B.Right = A;
                _root = B;
                A.Parent = B;
            }
            if (BRight != null)
            {
                Add(BRight.Key, BRight.Value); Count--;
            }
        }
        private void LeftBigTurn(Node<TKey, TValue> node)
        {
            var A = node;
            var B = node.Right;
            var C = node.Right.Left;

            C.Parent = A;
            A.Right = C;
            B.Left = null;
            C.Right = B;
            B.Parent = C;
            LeftSmallTurn(A);
        }
        private void RightBigTurn(Node<TKey, TValue> node)
        {
            var A = node;
            var B = node.Left;
            var C = node.Left.Right;

            C.Parent = A;
            A.Left = C;
            B.Right = null;
            C.Left = B;
            B.Parent = C;
            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();
        }
    }
}