AVLTree

namespace AVL
{
    public class AVLTree
    {
        public class Node
        {
            private string name;
            private string phone;
            private string tariff;
            private Node Left;
            private Node Right;
            private int height;

            public Node(string name_, string phone_, string tariff_)
            {
                name = name_;
                phone = phone_;
                tariff = tariff_;
                Left = null;
                Right = null;
                height = 1;
            }

            private static int Height(Node AVL)
            {
                return (AVL != null) ? AVL.height : 0;
            }

            private static int Bfactor (Node AVL)
            {
                return (Height(AVL.Right) - Height(AVL.Left));
            }

            private static void Fixheight(Node AVL)
            {
                int hl = Height(AVL.Left);
                int hr = Height(AVL.Right);
                AVL.height = (hl > hr ? hl : hr) + 1;
            }

            private static void RotateRight(ref Node AVL)
            {
                Node tmp = AVL.Left;
                AVL.Left = tmp.Right;
                tmp.Right = AVL;
                Fixheight(AVL);
                Fixheight(tmp);
                AVL = tmp;
            }

            private static void RotateLeft(ref Node AVL)
            {
                Node tmp = AVL.Right;
                tmp.Right = tmp.Left;
                tmp.Left = AVL;
                Fixheight(AVL);
                Fixheight(tmp);
                AVL =  tmp;
            }

            private static void Balance(ref Node AVL)
            {
                Fixheight(AVL);
                if (Bfactor(AVL) == 2)
                {
                    if (Bfactor(AVL.Right) < 0)
                        RotateRight(ref AVL.Right);
                    RotateLeft(ref AVL);
                }
                if (Bfactor(AVL) == -2)
                {
                    if (Bfactor(AVL.Left) > 0)
                        RotateLeft(ref AVL.Left);
                    RotateRight(ref AVL);
                }
            }

            public static void Add(ref Node AVL, string _name, string _phone, string _tariff)
            {
                if (AVL == null)  AVL = new Node(_name, _phone, _tariff);
                else if (((IComparable)(AVL.phone)).CompareTo(_phone) < 0)
                    Add(ref AVL.Left, _name, _phone, _tariff);
                else
                    Add(ref AVL.Right, _name, _phone, _tariff);
                Balance(ref AVL);
            }

            private Node FindMin(Node AVL)
            {
                return (AVL.Left != null) ? FindMin(AVL.Left) : AVL;
            }

            public static void RemoveMin(Node AVL, ref Node AVLT)
            {
                if (AVLT.Right != null)
                    RemoveMin(AVL, ref AVLT.Right);
                else
                {
                    AVL.name = AVLT.name;
                    AVLT = AVLT.Left;
                }
            }

            public static void RemoveByTelephone(ref Node AVL, string number)
            {
                if(AVL == null) throw new Exception ("This phone number doesn't belongs tree!");
                if (((IComparable)(AVL.phone)).CompareTo(number) < 0)
                    RemoveByTelephone(ref AVL.Left, number);
                else if (((IComparable)(AVL.phone)).CompareTo(number) > 0)
                    RemoveByTelephone(ref AVL.Right, number);
                else
                {
                    if(AVL.Left == null) AVL = AVL.Right;
                    if(AVL.Right == null) AVL = AVL.Left;
                    else RemoveMin(AVL, ref AVL.Left);
                }
                Balance(ref AVL);
            }

            public static void FindByPhone (Node AVL, string number, out Node result)
            {
                if (AVL == null)    result = null;
                else
                {
                    if (((IComparable)(AVL.phone)).CompareTo(number) == 0)
                    {
                        result = AVL;
                        Console.WriteLine("{0} - {1} - {2}", AVL.name, AVL.phone, AVL.tariff);
                        Console.WriteLine();
                    }
                    else if (((IComparable)(AVL.phone)).CompareTo(number) < 0)
                        FindByPhone(AVL.Left, number, out result);
                    else FindByPhone(AVL.Right, number, out result);
                }
            }

            public static void Print(Node AVL)
                {
                    if (AVL != null)
                    {
                        Console.WriteLine("{0} - {1} - {2}", AVL.name, AVL.phone, AVL.tariff);
                        Print(AVL.Left);
                        Print(AVL.Right);
                    }
                }

            public static void GetMostPopularTariff(Node AVL)
            {
                if (AVL != null)
                {
                    Dictionary<string, int> allTariffes = new Dictionary<string, int>();
                    CounterOfTariffes(AVL, ref allTariffes);

                    int max = 0;
                    foreach(var i in allTariffes)
                        if(i.Value > max)   max = i.Value;

                    Console.Write("The most popular tariff is: ");

                    foreach(var i in allTariffes)
                        if(i.Value == max)  Console.Write("{0} ", i.Key);

                    Console.WriteLine();
                }
            }

            private static void CounterOfTariffes(Node AVL, ref Dictionary <string, int> allTariffes)
            {
                if(AVL != null)
                {
                    if (allTariffes.ContainsKey(AVL.tariff))
                        allTariffes[AVL.tariff] += 1;
                    else allTariffes.Add(AVL.tariff, 0);

                    CounterOfTariffes(AVL.Left, ref allTariffes);
                    CounterOfTariffes(AVL.Right, ref allTariffes);
                }
            }

        }

        Node tree;

        public AVLTree()
        {
            tree = null;
        }

        private AVLTree(Node tmp)
        {
            tree = tmp;
        }

        public void Add(string name, string phone, string tariff)
        {
            Node.Add(ref tree, name, phone, tariff);
        }

        public void RemoveByTelephone(string number)
        {
            Node.RemoveByTelephone(ref tree, number);
        }

        public void Print()
        {
            Node.Print(tree);
            Console.WriteLine();
        }

        public void GetMostPopularTariff()
        {
            Node.GetMostPopularTariff(tree);
        }

        public AVLTree FindByPhone(string number)
        {
            Node res;
            Node.FindByPhone(tree, number, out res);
            if (res == null) throw new Exception("Object with this phone number is not found!");
            return new AVLTree(res);
        }

        public void FormAVLTree(StreamReader fin)
        {
            string name, tariff;
            string[] tmp;
            while (!fin.EndOfStream)
            {
                tmp = fin.ReadLine().Split(' ');
                if (tmp.Length == 5)
                {
                    name = tmp[0] + ' ' + tmp[1] + ' ' + tmp[2];
                    Node.Add(ref tree, name, tmp[3], tmp[4]);
                }
                else
                {
                    name = tmp[0] + ' ' + tmp[1] + ' ' + tmp[2];
                    tariff = tmp[4] + ' ' + tmp[5];
                    Node.Add(ref tree, name, tmp[3], tariff);
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            AVLTree tree = new AVLTree();
            AVLTree tmp = new AVLTree();

            StreamReader fin = new StreamReader("input.txt");
            tree.FormAVLTree(fin);
            fin.Close();
            tree.Print();


            tree.Add("Иванов Сергей Иванович", "9213456532", "Все включено");
            tree.Add("Гордеев Андрей Владимирович", "9653214333", "Домашний");
            tree.Add("Грачева Антонина Николаевна", "9653214334", "Все включено");
            tree.Add("Андреянова Светлана Георгиевна", "9653214335", "Домашний");
            tree.Add("Соколов Виктор Сергеевич", "9653214336", "Домашний");
            tree.Add("Петров Геннадий Вадимович", "9653214337", "Все включено");
            Console.WriteLine("Tree after adding new elements: ");
            tree.Print();

            tree.RemoveByTelephone("9653214336");
            Console.WriteLine("Remove of 9653214336:");
            tree.Print();

            Console.WriteLine("Find by number:");
            tmp = tree.FindByPhone("9653214334");

            tree.GetMostPopularTariff();
        }
    }
}

//input
Иванов Антон Иванович 9213456538 Все включено
Кузьмин Андрей Владимирович 9653214339 Семейный
Лососева Антонина Николаевна 9653214340 Все включено
Кулякина Светлана Георгиевна 9653214341 Домашний