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

namespace ATSD2
{
    class Program
    {
        static void Main(string[] args)
        {
            BalancedBST b = new BalancedBST();
            b.AddItem(25);
            b.AddItem(17);
            b.AddItem(35);
            b.AddItem(10);
            b.AddItem(20);
            b.Delete(35);
            b.inorder();
        }
    }
    class Node
    {
        public int Key { get; set; }
        public Node Left;
        public Node Right;
        public Node Parent;
        public int Height;
        public int Balance;
        public Node(int k, Node p=null, int b=0)
        {
            Key = k;
            Left = null;
            Right = null;
            Parent = p;
            Balance = b;
            if (Parent != null)
                Height = Parent.Height - 1;
            else
                Height = 1;
        }

    }

    class BalancedBST
    {
        public Node Root;
        public BalancedBST()
        {
            Root = null;
        }
        public BalancedBST(int key)
        {
            Root = new Node(key);
        }
        private Node RotateLeft(Node node)
        {
            Node right = node.Right;
            Node rightLeft = right.Left;
            Node parent = node.Parent;

            right.Parent = parent;
            right.Left = node;
            node.Right = rightLeft;
            node.Parent = right;

            if (rightLeft != null)
            {
                rightLeft.Parent = node;
            }

            if (node == Root)
            {
                Root = right;
            }
            else if (parent.Right == node)
            {
                parent.Right = right;
            }
            else
            {
                parent.Left = right;
            }

            return right;
        }

        private Node RotateRight(Node node)
        {
            Node left = node.Left!=null?node.Left:null;
            Node leftRight = left.Right!=null?left.Right:null;
            Node parent = node.Parent;

            left.Parent = parent;
            left.Right = node;
            node.Left = leftRight;
            node.Parent = left;

            if (leftRight != null)
            {
                leftRight.Parent = node;
            }

            if (node == Root)
            {
                Root = left;
            }
            else if (parent.Left == node)
            {
                parent.Left = left;
            }
            else
            {
                parent.Right = left;
            }

            return left;
        }
        public void FixHeight(Node p)
        {
            int hl = 0;
            int hr = 0;
            if (p.Left != null)
                FixHeight(p.Left);
            if (p.Right != null)
                FixHeight(p.Right);
            if (p.Left != null)
                hl = p.Left.Height;
            if (p.Right != null)
                hr = p.Right.Height;
            p.Height = (hl > hr ? hl : hr) + 1;
        }
        public void RecountBalance(Node p)
        {
            int hl = 0;
            int hr = 0;
            if (p.Left != null)
            {
                RecountBalance(p.Left);
                hl = p.Left.Height;
            }
            if (p.Right != null)
            {
                RecountBalance(p.Right);
                hr = p.Right.Height;
            }
            p.Balance = hl - hr;
        }
        public void AddBalanceTree(Node p)
        {
            if (p.Left != null)
                AddBalanceTree(p.Left);
            if (p.Right != null)
                AddBalanceTree(p.Right);
            if (p.Balance == 2)
            {
                if (p.Left.Balance == 1)
                    RotateRight(p);
                else
                {
                    RotateLeft(p.Left);
                    RotateRight(p);
                }
            }
            if (p.Balance == -2)
            {
                if (p.Right.Balance == -1)
                    RotateLeft(p);
                else
                {
                    RotateRight(p.Right);
                    RotateLeft(p.Left);
                }
            }
        }
        public void AddItem(int k)
        {
            Insert(Root, k);
        }
        public void Insert(Node p, int k)
        {
            if (Root == null)
                Root = new Node(k);
            else if (p.Left == null && k < p.Key)
                p.Left = new Node(k, p);
            else if (p.Right == null && k >= p.Key)
                p.Right = new Node(k, p);
            else if (k < p.Key)
                Insert(p.Left, k);
            else if (k >= p.Key)
                Insert(p.Right, k);
            FixHeight(Root);
            RecountBalance(Root);
            AddBalanceTree(Root);
        }
        public void DelBalanceTree(Node p)
        {
            if (p.Balance == 2)
                RotateRight(p);
            if (p.Balance == -2)
                RotateLeft(p);
            if (p.Left != null)
                DelBalanceTree(p.Left);
            if (p.Right != null)
                DelBalanceTree(p.Right);
        }
        public void Delete(int key)
        {
            DeleteKey(ref Root, key);
            FixHeight(Root);
            RecountBalance(Root);
            DelBalanceTree(Root);
            FixHeight(Root);
        }
        public void DeleteKey(ref Node p, int key)
        {
            if (p.Key == key && p.Left == null && p.Right == null)
            {
                if(p == Root)
                    Root = null;
                else if (p.Parent.Left == p)
                    p.Parent.Left = null;
                else if (p.Parent.Right == p)
                    p.Parent.Right = null;

            }
            else if (p.Key == key && p.Left != null && p.Right == null)
            {
                if (p == Root)
                    Root = p.Left;
                else
                {
                    if (p.Parent.Right == p)
                        p.Parent.Right = p.Left;
                    else if (p.Parent.Left == p)
                        p.Parent.Left = p.Left;
                }
            }
            else if (p.Key == key && p.Right != null)
            {
                Node min = findmin(p.Right);
                p.Key = min.Key;
                if (min.Parent.Left == min)
                {
                    if (min.Right == null)
                        min.Parent.Left = null;
                    else
                        min.Parent.Left = min.Right;
                }
                else if (min.Parent.Right == min)
                {
                    if (min.Right == null)
                        min.Parent.Right = null;
                    else
                        min.Parent.Right = min.Right;
                }
            }
            else if (p.Left != null && key < p.Key)
                DeleteKey(ref p.Left, key);
            else if (p.Right != null && key >= p.Key)
                DeleteKey(ref p.Right, key);
        }

        public Node findmin(Node p)
        {
            return p.Left!=null ? findmin(p.Left) : p;
        }

        public void inorder()
        {
            Console.WriteLine("inorder sequence of nodes:");
            Console.WriteLine(Root.Key);
            inorder_rec(Root);
            Console.WriteLine(";");
        }
        protected void inorder_rec(Node p)
        {
            if (p != null)
            {
                inorder_rec(p.Left);
                Console.Write(p.Key + ", " + p.Height + ", ");
                inorder_rec(p.Right);
            }
        }


    }
}