C#AVL 트리

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading;

using System.Threading.Tasks;

using System.Collections.Concurrent;

namespace Console1

{

    public class AvlNode

    {

        public int m_iData;

        public AvlNode m_Left_Child;

        public AvlNode m_Right_Child;

        public AvlNode(int iData)

        {

            m_iData = iData;

        }

    }

    public class AvlTree

    {

        private AvlNode m_Root;

        //삽입

        public void Avl_Insert(int iKey)

        {

            if(m_Root == null)

            {

                m_Root = new AvlNode(iKey);

                return;

            }

            //왼쪽

            if (m_Root.m_iData > iKey)

            {

                m_Root = NodeInsert(ref m_Root, iKey);

                

            }

            //오른쪽

            else if(m_Root.m_iData < iKey)

            {

            }

            else

            {

                Console.WriteLine("중복키");

            }

        }

        private AvlNode NodeInsert(ref AvlNode node, int iKey)

        {

            if(node == null)

            {

                node = new AvlNode(iKey);

                return node;

            }

            if (node.m_iData > iKey)

            {

                node.m_Left_Child = NodeInsert(ref node.m_Left_Child, iKey);

                BlanceTree(ref node);

                return node;

            }

            else if(node.m_iData < iKey)

            {

                node.m_Right_Child = NodeInsert(ref node.m_Right_Child, iKey);

                BlanceTree(ref node);

                return node;

            }

            return null;

        }

        private void BlanceTree(ref AvlNode node)

        {

            int iDepthTree = GetHeightTree(node);

            //왼쪽 서브트리 균형

            if(iDepthTree > 1)

            {

                if(GetHeightTree(node.m_Left_Child) > 0)

                {

                    //LL 회전

                    AvlNode Root = RotateLL(node);

                    node = Root;

                }

                else

                {

                }

            }

            //오른쪽 서브트리 균형

            else if(iDepthTree < -1)

            {

                if (GetHeightTree(node.m_Right_Child) < 0)

                {

                }

                else

                {

                }

            }

        }

        //평균인수를 구하는 함수

        private int GetHeightTree(AvlNode node)

        {

            if (node == null)

                return 0;

            return GetHeight(node.m_Left_Child) - GetHeight(node.m_Right_Child);

        }

        //트리의 높이를 계산

        private int GetHeight(AvlNode node)

        {

            int iHeight = 0;

            if(node != null)

            {

                iHeight = 1 + Math.Max(GetHeight(node.m_Left_Child), GetHeight(node.m_Right_Child));

            }

            return iHeight;

        }

        private AvlNode RotateLL(AvlNode node)

        {

            AvlNode TempNode = null;

            TempNode = node.m_Left_Child;   //7

            node.m_Left_Child = TempNode.m_Right_Child;         //null

            TempNode.m_Right_Child = node;  //

            return TempNode;

        }

    }

    class Program

    {

        static void Main(string[] args)

        {

            AvlTree pRoot = new AvlTree();

            pRoot.Avl_Insert(10);

            pRoot.Avl_Insert(7);

            pRoot.Avl_Insert(5);

        }

    }

}

** 매개변수의 Ref를 잘써야 한다..이건 C++에서의 이중 포인터와 같다.

** 부모 즉, 루트를 바꿔줘야하는게 까다로웠음..뭐 이중포인터를 썼다면 금방 끝날 문제이긴 한데.....