AVL/27.02/22:40

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

namespace AVLTree
{
    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)
        {
            Stack<Node<TKey, TValue>> stack = new Stack<Node<TKey, TValue>>();
            Queue<Node<TKey, TValue>> queue_abc = new Queue<Node<TKey, TValue>>();
            var node = new Node<TKey, TValue>(key, value);
            if (_root == null)
            {
                _root = node;
                Count++;
                return;
            }
            var current = _root;
            var parent = _root;
            while (current != null)
            {
                stack.Push(current);
                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;
            queue_abc.Enqueue(node);
            Count++;
            while (stack.Count != 0)
            {
                var currentNode = stack.Pop();
                queue_abc.Enqueue(currentNode);
                if (queue_abc.Count > 3)
                {
                    queue_abc.Dequeue();
                }
                var LeftInt = FindHightTheTree(currentNode.Left);
                var RightInt = FindHightTheTree(currentNode.Right);
                if (Math.Abs(LeftInt - RightInt) > 1)
                {
                    Balancing(queue_abc);
                }
            }
        }

        public void Delete(TKey key, TValue value)
        {
            Stack<Node<TKey,TValue>> stack = new Stack<Node<TKey,TValue>>();
            Queue<Node<TKey, TValue>> queue_abc = new Queue<Node<TKey, TValue>>();
            var node = FindElem(key);

            //Удаление
            if (node != null)
            {
                Count--;

                // если нет детей - узел удаляется
                if (node.Left == null && node.Right == null)
                {
                    Node<TKey, TValue> newnode;
                    if (node.Parent.Left == node)
                    {
                        node.Parent.Left = null;
                    }
                    else
                    {
                        node.Parent.Right = null;
                    }
                }

                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)
                        {
                            stack.Push(current);
                            current = current.Left;
                        }
                        var minelement = current;
                        Delete(minelement.Key, minelement.Value); Count++;
                        // значение узла заместителя переписыввется в удаляемый, а сам заместитель удаляется
                        var tempLeftTree = _root.Left; var tempRightTree = _root.Right;
                        _root = minelement;
                        _root.Parent = null;
                        _root.Left = tempLeftTree; _root.Right = tempRightTree;
                    }
                }
                else //Не корень
                {
                    // если один ребенок - ребенок занимает место удаленного узла
                    if ((node.Left != null && node.Right == null))
                    {
                        var tempparent = node.Parent;
                        node = node.Left;
                        tempparent.Left = node;
                        node.Parent = tempparent;
                    }
                    else if ((node.Left == null && node.Right != null))
                    {
                        var tempparent = node.Parent;
                        node = node.Right;
                        tempparent.Right = node;
                        node.Parent = tempparent;
                    }
                    // если два ребенка -
                    else if (node.Left != null && node.Right != null)
                    {
                        // ищем замену - самый левый из элементов правого поддерева
                        var current = node.Right;
                        while (current.Left != null)
                        {
                            stack.Push(current);
                            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); Count++;

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

            queue_abc.Enqueue(node);
            while (stack.Count != 0)
            {
                var currentNode = stack.Pop();
                queue_abc.Enqueue(currentNode);
                if (queue_abc.Count > 3)
                {
                    queue_abc.Dequeue();
                }
                var LeftInt = FindHightTheTree(currentNode.Left);
                var RightInt = FindHightTheTree(currentNode.Right);
                if (Math.Abs(LeftInt - RightInt) > 1)
                {
                    Balancing(queue_abc);
                }
            }
            return;
        }
        public bool Contains(TKey key, TValue value)
        {
            // Поиск узла осуществляется другим методом.
            return FindElem(key) != null;
        }
        private void Balancing(Queue<Node<TKey, TValue>> abc)
        {
            var C = abc.Dequeue();
            var B = abc.Dequeue();
            var A = abc.Dequeue();
            var addingEl = A;

            if (A.Right == B) //Справа
            {
                if (B.Right == C) // Если добавляем справа
                {
                    if (B.Left != null)
                    {
                        var BLeft = new Node<TKey, TValue>(B.Left.Key, B.Left.Value);//Запоминаем левый от B
                        BLeft.Right = B.Left.Right; BLeft.Left = B.Left.Left;

                        Delete(B.Left.Key, B.Left.Value); //Удаляем левый от B

                        var tempA = new Node<TKey, TValue>(A.Key, A.Value);
                        tempA.Left = A.Left;

                        B.Parent = A.Parent; //Поворот поддерева без удалённого элемента
                        if (A.Parent != null)
                        {
                            A.Parent.Right = B;
                        }
                        else _root = B;
                        B.Left = tempA;
                        tempA.Parent = B;

                        Add(BLeft.Key, BLeft.Value); //Добавляем удалённый элемент
                    }
                    else
                    {
                        var BLeft = new Node<TKey, TValue>(A.Key,A.Value);
                        BLeft.Left = A.Left;

                        B.Parent = A.Parent;
                        if (A.Parent != null)
                        {
                            A.Parent.Right = B;
                        }
                        else _root = B;

                        B.Left = BLeft;
                        BLeft.Parent = B;
                    }
                }
                else if (B.Left == C)// Если добавляем слева
                {
                    var tempB = new Node<TKey, TValue>(B.Key, B.Value);
                    tempB.Right = B.Right;
                    A.Right = C;
                    C.Parent = A;
                    C.Right = tempB;
                    abc.Enqueue(tempB);
                    abc.Enqueue(C);
                    abc.Enqueue(A);
                    Balancing(abc);
                }
            }
            else //Слева
            {
                if (B.Left == C) // Если добавляем слева
                {
                    if (B.Right != null)
                    {
                        var BRight = new Node<TKey, TValue>(B.Right.Key, B.Right.Value);//Запоминаем левый от B
                        BRight.Left = B.Right.Left; BRight.Right = B.Right.Right;

                        Delete(B.Right.Key, B.Right.Value); //Удаляем левый от B

                        var tempA = new Node<TKey, TValue>(A.Key, A.Value);
                        tempA.Right = A.Right;

                        B.Parent = A.Parent; //Поворот поддерева без удалённого элемента
                        if (A.Parent != null)
                        {
                            A.Parent.Left = B;
                        }
                        else _root = B;
                        B.Right = tempA;
                        tempA.Parent = B;

                        Add(BRight.Key, BRight.Value); //Добавляем удалённый элемент
                    }
                    else
                    {
                        var BRight = new Node<TKey, TValue>(A.Key, A.Value);
                        BRight.Right = A.Right;

                        B.Parent = A.Parent;
                        if (A.Parent != null)
                        {
                            A.Parent.Left = B;
                        }
                        else _root = B;

                        B.Right = BRight;
                        BRight.Parent = B;
                    }
                }
                else if (B.Right == C)// Если добавляем слева
                {
                    var tempB = new Node<TKey, TValue>(B.Key, B.Value);
                    tempB.Left = B.Left;
                    A.Left = C;
                    C.Parent = A;
                    C.Left = tempB;
                    abc.Enqueue(tempB);
                    abc.Enqueue(C);
                    abc.Enqueue(A);
                    Balancing(abc);
                }
            }
        }
        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();
        }
    }
}