220419_자료구조_자가균형트리_AVL트리(AVL Tree) 구현

* 필요한 헤더: 링크드 리스트(Linked List)

https://hyrule.tistory.com/45

220407~220411_자료구조_링크드 리스트 구현 (Linked List)

 

 

//BinaryAVLTree.h

/*
[자가균형이진트리]
* 이진트리의 문제점: 편향트리가 될 가능성이 있다.
* 편향트리는 나오는 순간 최악.
* 일반 이진트리를 쓸 때 편향트리를 피할 수 있는 방법은 아예 없다.(넣는 데이터에 의존적)
* 그렇다고 사용자가 데이터를 직접 조율해가며 넣는 것은 너무 힘들다.
* 그래서 나온 것이 '자가균형이진트리'
	- AVL 이진트리, 레드블랙 이진트리
		-> AVL 이진트리는 매우 규칙이 빡빡해서 상대적으로 처리 속도가 느리다는 단점이 있다.
		-> 레드블랙 이진트리는 규칙이 느슨하게 적용되어 상대적으로 처리 속도가 빠르다고 한다.


[AVL TREE]
* Adelson-Velsky and Landis 라는 사람들이 만들어서 AVL 트리임
* 가장 중요한 것: 트리의 회전, 트리의 밸런스가 무너졌는지 판단
* 회전을 하는 이유: 완전 이진트리를 만들기 위해
* 회전을 할 때 -> 트리의 밸런스가 무너졌을 때
* 밸런스가 무너지는 경우: 추가 or 삭제 두 가지 경우
* 
*/


/* 
[트리의 회전]
* 높이 차이 구하기
	- 각 노드들로부터 부모님 노드와의 높이를 계산한다. 한 층당 1이라고 가정했을 때
	- 한 쪽만 자식을 가진 채로 높이차이가 2 이상 나면 밸런스가 무너졌다고 판단한다.
	ex)(균형붕괴)		(균형붕괴)		  (정상)
			1		1			1
			 \		 \			 \
			  2		  2			  2
			   \		 /			 / \
			    3		3			3   4

*/



//지난번에 구현한 이진트리 코드에 추가하여 구현할 것임.
#pragma once

#include <iostream>
#include "LinkedList.h"


//KEY값: 저장규칙 - 대소판별, VALUE값: 실제 들어갈 데이터
template <typename KEY, typename VALUE>
class CBinaryAVLTreeNode
{
	template <typename KEY, typename VALUE>
	friend class CBinaryAVLTree;

	template <typename KEY, typename VALUE>
	friend class CBinaryAVLTreeIterator;

public:
	CBinaryAVLTreeNode():
		m_Parent(nullptr),
		m_Left(nullptr),
		m_Right(nullptr),
		m_Next(nullptr),
		m_Prev(nullptr)
	{

	}
	~CBinaryAVLTreeNode()
	{

	}

public:
	//정보 저장
	VALUE m_Data;
	//현재 노드의 키값
	KEY m_Key;
private:
	//(트리노드)부모노드, 좌, 우 노드 저장
	CBinaryAVLTreeNode<KEY, VALUE>* m_Parent;
	CBinaryAVLTreeNode<KEY, VALUE>* m_Left;
	CBinaryAVLTreeNode<KEY, VALUE>* m_Right;

	//(링크드리스트)앞노드, 뒤노드 저장
	CBinaryAVLTreeNode<KEY, VALUE>* m_Next;
	CBinaryAVLTreeNode<KEY, VALUE>* m_Prev;
};


template <typename KEY, typename VALUE>
class CBinaryAVLTreeIterator
{
	template <typename KEY, typename VALUE>
	friend class CBinaryAVLTree;
//밖에서 실제로 활용해야 할 기능이기 때문에 public으로 선언
public:
	CBinaryAVLTreeIterator():
		m_Node(nullptr)
	{

	}
	~CBinaryAVLTreeIterator()
	{

	}

private:
	CBinaryAVLTreeNode<KEY, VALUE>* m_Node;

public:
	//연산자 추가
	bool operator == (const CBinaryAVLTreeIterator<KEY, VALUE>& iter) const
	{
		return (m_Node == iter.m_Node);
	}
	bool operator != (const CBinaryAVLTreeIterator<KEY, VALUE>& iter) const
	{
		return (m_Node != iter.m_Node);
	}
	void operator ++ ()
	{
		m_Node = m_Node->m_Next;
	}
	void operator -- ()
	{
		m_Node = m_Node->m_Prev;
	}
	void operator ++ (int)
	{
		m_Node = m_Node->m_Next;
	}
	void operator -- (int)
	{
		m_Node = m_Node->m_Prev;
	}
	void operator + (int addnum)
	{
		for (int i = 0; i < addnum; ++i)
		{
			if (nullptr == m_Node->m_Next)
				return;
			m_Node = m_Node->m_Next;
		}
	}
	void operator - (int addnum)
	{
		for (int i = 0; i < addnum; ++i)
		{
			if (nullptr == m_Node->m_Prev)
				return;
			m_Node = m_Node->m_Prev;
		}
	}

	VALUE& operator *()
	{
		return m_Node->m_Data;
	}
	
	//iterator.m_Node를 하지 않아도 바로 m_Node 주소를 반환해 주는 연산자 재정의
	CBinaryAVLTreeNode<KEY, VALUE>* operator -> () const
	{
		return m_Node;
	}

};


template <typename KEY, typename VALUE>
class CBinaryAVLTree
{
public:
	CBinaryAVLTree() :
		m_Root(nullptr)
	{
		m_Begin = new NODE;
		m_End = new NODE;

		m_Begin->m_Next = m_End;
		m_End->m_Prev = m_Begin;
	}
	~CBinaryAVLTree()
	{
		PNODE Del = m_Begin;
		while (Del)
		{
			PNODE Next = Del->m_Next;
			delete Del;
			Del = Next;
		}


	}

private:

	typedef CBinaryAVLTreeNode<KEY, VALUE>		NODE;
	typedef CBinaryAVLTreeNode<KEY, VALUE>* PNODE;
	typedef CBinaryAVLTreeIterator<KEY, VALUE> iterator;

	//루트 노드의 주소 관리
	PNODE m_Root;

	//링크드 리스트 주소 관리
	PNODE m_Begin;
	PNODE m_End;

	int m_Size;




public:
	//기본 기능들 구현.
	iterator begin() const
	{
		iterator iter;
		iter.m_Node = m_Begin->m_Next;
		return iter;
	}
	iterator end() const
	{
		iterator iter;
		iter.m_Node = m_End;
		return iter;
	}
	int getsize() const
	{
		return m_Size;
	}
	void clear()
	{
		if (m_Size == 0)
			return;

		PNODE del = m_Begin->m_Next;
		PNODE end = m_End;

		while (del != end)
		{
			PNODE next = del->m_Next;
			delete del;
			del = next;
		}

		m_Begin->m_Next = m_End;
		m_End->m_Prev = m_Begin;

		m_Root = nullptr;
		m_Size = 0;
	}
//////////////////////////////////////////



public:
	//삽입 기능 구현
	void insert(const KEY& Key, const VALUE& Value)
	{
		//루트 노드가 생성되어 있지 않다면 생성
		if (!m_Root)
		{
			//트리 부분
			m_Root = new NODE;
			m_Root->m_Key = Key;
			m_Root->m_Data = Value;

			//리스트 부분
			m_Root->m_Next = m_End;
			m_Root->m_Prev = m_Begin;

			m_Begin->m_Next = m_Root;
			m_End->m_Prev = m_Root;

			++m_Size;

		}
		else
		{
			//이외의 경우 재귀호출 시작
			PNODE NewNode = insert(Key, Value, m_Root);
		}

	}

private:
	//재귀호출용 오버라이드 함수
	PNODE insert(const KEY& Key, const VALUE& Value, PNODE Node)
	{
		if (!Node)
			return nullptr;

		//인자로 들어온 노드의 키 값이 Key보다 작을 경우
		if (Node->m_Key > Key)
		{
			//m_Left값이 존재하지 않으면 바로 추가.
			if (!Node->m_Left)
			{
				//트리 부분
				PNODE NewNode = new NODE;
				NewNode->m_Data = Value;
				NewNode->m_Key = Key;

				//부모-자식 관계로 연결.
				Node->m_Left = NewNode;
				NewNode->m_Parent = Node;
				////////////////////////////

				//리스트 부분
				//m_Left에 들어가는 상황이므로 부모 노드의 키 값은 무조건 나보다 크다.

				//연결을 위해 임시로 주소를 받아놓고
				PNODE Prev = Node->m_Prev;

				NewNode->m_Prev = Prev;
				NewNode->m_Next = Node;

				Prev->m_Next = NewNode;
				Node->m_Prev = NewNode;


				++m_Size;

				//새로 추가한 곳으로부터 위로 올라가면서 밸런스 작업을 수행
				Rebalance(NewNode);

				//새로 만들어진 노드 주소를 반환
				return NewNode;
			}

			//m_Left값이 존재하면 한번 더 타고들어가는 재귀함수 호출.
			return insert(Key, Value, Node->m_Left);
		}

		//인자로 들어온 노드의 키 값이 Key보다 클 경우
		if (Node->m_Key < Key)
		{
			//m_Left값이 존재하지 않으면 바로 추가.
			if (!Node->m_Right)
			{
				//트리 부분
				PNODE NewNode = new NODE;
				NewNode->m_Data = Value;
				NewNode->m_Key = Key;

				//부모-자식 관계로 연결.
				Node->m_Right = NewNode;
				NewNode->m_Parent = Node;
				////////////////////////////

				//리스트 부분
				//m_Right에 들어가는 상황이므로 부모 노드의 키 값은 무조건 나보다 크다.

				//연결을 위해 임시로 주소를 받아놓고
				PNODE Next = Node->m_Next;

				NewNode->m_Next = Next;
				NewNode->m_Prev = Node;

				Next->m_Prev = NewNode;
				Node->m_Next = NewNode;
				//////////////////////////


				//새로 추가한 곳으로부터 위로 올라가면서 밸런스 작업을 수행
				Rebalance(NewNode);

				++m_Size;
				return NewNode;
			}

			//m_Right값이 존재하면 한번 더 타고들어가는 재귀함수 호출.
			return insert(Key, Value, Node->m_Right);
		}

	}
////////////////////////////////////////////////////////////////////






public:
	//키값을 입력하면 삭제해주는 기능
	iterator erase(const KEY& key)
	{
		iterator iter = Find(key);
		if (iter == end())
			return end();

		//본체에 찾은 iterator을 넣어 검색
		return erase(iter);

	}

	//erase 본체는 이거
	//삭제 후에도 규칙을 유지할 수 있어야 하므로 추가나 탐색보다 훨씬 복잡하다.
	iterator erase(const iterator& iter)
	{

		if (iter == end())
			return end();
		

		//1-1. 리프노드인지 확인한다.(리프노드면 바로 삭제하면 되므로)
		if (!iter.m_Node->m_Left && !iter.m_Node->m_Right)
		{
			//(예외처리)혹시나 지울 대상이 마지막 남은 루트노드라면
			//(자식이 없는 루트노드 -> 노드가 딱 하나라는 뜻)
			//해당 루트노드를 삭제하고 end()를 반환
			if (iter.m_Node == m_Root)
			{
				m_Begin->m_Next = m_End;
				m_End->m_Prev = m_Begin;

				delete iter.m_Node;

				m_Root = nullptr;

				--m_Size;
				return end();
			}


			//1-2. 지울 노드가 오른쪽 노드인지 왼쪽 노드인지 확인한다.
			if (iter.m_Node->m_Parent->m_Left == iter.m_Node)
			{
				//이진트리 부모자식관계 정리
				iter.m_Node->m_Parent->m_Left = nullptr;
			}
			else
			{
				iter.m_Node->m_Parent->m_Right = nullptr;
			}

			//1-3. 링크드리스트 제거
			PNODE Next = iter.m_Node->m_Next;
			PNODE Prev = iter.m_Node->m_Prev;
			Next->m_Prev = Prev;
			Prev->m_Next = Next;


			//(AVL)노드가 제거되면 부모노드부터 높이를 검사해서 불균형이 일어났는지 확인한다.
			//미리 주소를 받아놓고
			PNODE Parent = iter.m_Node->m_Parent;

			//1-4. 노드 제거
			delete iter.m_Node;

			Rebalance(Parent);


			//1-5. 사이즈 하나 감소
			--m_Size;


			//1-6. 삭제된 노드의 다음 노드를 반복자에 담아 반환.
			iterator result;

			//Next가 end()로 반환될 경우 에러가 났는지 헷갈릴수도 있으므로
			//end 바로 전인 Prev를 반환.
			if (Next == end().m_Node)
			{
				result.m_Node = Prev;
				return result;
			}
			result.m_Node = Next;
			return result;
		}

		//2-1. 리프 노드가 아니라면,

		//2.2. 그리고, 왼쪽 노드가 존재한다면 왼쪽 노드의 '최댓값'을
		// 지울 노드의 위치로 가져온다.
		//참고)왼쪽 노드의 최댓값은 절대로 오른쪽 노드를 가지지 않는다.
		// 왼쪽 노드의 최댓값의 오른쪽 자식 노드 = 최댓값보다 더 큰 값이여야 함 
		// -> 말이 안됨.
		//하지만, 왼쪽 자식 노드는 가질 수도 있다.
		//이 경우, 왼쪽 자식 노드를 부모 노드 위치로 가져온다.
		PNODE FindNode = nullptr;
		PNODE ChildNode = nullptr;
		if (iter.m_Node->m_Left)
		{
			//왼쪽 노드의 최댓값 탐색
			FindNode = FindMax(iter.m_Node->m_Left);

			//자식 노드 주소를 받아옴. 없다면 nullptr을 받아올 것임.
			ChildNode = FindNode->m_Left;
		}

		//만약 왼쪽 노드가 존재하지 않을 경우, 오른쪽 노드의 값을 가져온다.
		else
		{
			FindNode = FindMin(iter.m_Node->m_Right);
			ChildNode = FindNode->m_Right;
		}


		//가져온 값을, 지울 키값의 노드에 복사.
		iter.m_Node->m_Key = FindNode->m_Key;
		iter.m_Node->m_Data = FindNode->m_Data;


		//찾은 왼쪽 노드 중 최댓값 / 오른쪽 노드 중 최솟값은
		//이진트리의 규칙 상 절대로 자식 노드를 두개 가질 수 없다.
		//잘 생각해보자.
		//왼쪽 노드 중 최댓값이 오른쪽 노드가 있다면, 
		//그 값이 최댓값이여야 한다.
		//마찬가지로 오른쪽 노드 중 최솟값이 왼쪽 노드가 있다면,
		//그 값이 최솟값이여야 한다.
		if(FindNode == FindNode->m_Parent->m_Left)
		{
			FindNode->m_Parent->m_Left = ChildNode;
		} 
		else if (FindNode == FindNode->m_Parent->m_Right)
		{
			FindNode->m_Parent->m_Right = ChildNode;
		}

		//그리고 만약 자식노드가 있었다면
		//해당 노드를 find노드의 부모 노드와 연결한다.
		if (ChildNode)
		{
			ChildNode->m_Parent = FindNode->m_Parent;
		}
		


		//링크드 리스트 정리
		//연결시켜주어야 하는 노드는 
		//FindNode 노드의 prev와 next이다.(왼쪽, 오른쪽 동일)
		FindNode->m_Prev->m_Next = FindNode->m_Next;
		FindNode->m_Next->m_Prev = FindNode->m_Prev;

		PNODE Parent = FindNode->m_Parent;

		//최종적으로 FindNode를 제거한다.
		delete FindNode;

		Rebalance(Parent);

		//그리고 지운 값이 있던 노드를 반환한다
		//(해당 노드는 새 값으로 변경되었음)
		iterator result;
		result.m_Node = iter.m_Node;

		--m_Size;
		return result;
	}
//////////////////////////////////////////////////////////////////////




private:
	//기준 노드의 오른쪽으로 쭉 타고 가면 최댓값이 나온다.
	PNODE FindMax(PNODE Node)
	{
		if (!Node->m_Right)
			return Node;

		return FindMax(Node->m_Right);
	}
	//반대로 똑같이
	PNODE FindMin(PNODE Node)
	{
		if (!Node->m_Left)
			return Node;

		return FindMax(Node->m_Left);
	}








//탐색 함수
public:
	iterator Find(const int& Key) const
	{
		return Find(Key, m_Root);
	}

private:
	iterator Find(const int& Key, PNODE Node) const
	{
		if (!Node)
			return end();

		
		//일치하는 키를 찾으면 이터레이터에 해당 노드를 담아서 리턴
		if(Node->m_Key == Key)
		{
			iterator iter;
			iter.m_Node = Node;
			return iter;
		}
		//만약 키 값이 노드의 키보다 작으면 왼쪽으로 탐색
		else if (Node->m_Key > Key)
		{
			return Find(Key, Node->m_Left);
		}
		
		//if문을 전부 통과해도 못 찾았을 경우 오른쪽으로 탐색 시작
		return Find(Key, Node->m_Right);
	}




//전위순회: 루트->왼쪽->오른쪽 순
//중위순회: 왼쪽->루트->오른쪽 순
//후위순회: 왼쪽->오른쪽->루트 순(리프노드부터)
//함수의 재귀구조는 동일하고, 출력 순서만 바꿔주면 됨.
public:
	void PreOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&))
	{
		PreOrder(Func, m_Root);
	}
private:
	void PreOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&), PNODE Node)
	{
		if (!Node)
			return;

		int ParentKey = 0, RightKey = 0, LeftKey = 0;

		if (Node->m_Parent)
			ParentKey = Node->m_Parent->m_Key;
		if (Node->m_Right)
			RightKey = Node->m_Right->m_Key;
		if (Node->m_Left)
			LeftKey = Node->m_Left->m_Key;

		Func(Node->m_Key, Node->m_Data, ParentKey, LeftKey, RightKey);

		PreOrder(Func, Node->m_Left);
		PreOrder(Func, Node->m_Right);
	}

public:
	void InOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&))
	{
		InOrder(Func, m_Root);
	}
private:
	void InOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&), PNODE Node)
	{
		if (!Node)
			return;

		int ParentKey = 0, RightKey = 0, LeftKey = 0;

		if (Node->m_Parent)
			ParentKey = Node->m_Parent->m_Key;
		if (Node->m_Right)
			RightKey = Node->m_Right->m_Key;
		if (Node->m_Left)
			LeftKey = Node->m_Left->m_Key;


		InOrder(Func, Node->m_Left);
		Func(Node->m_Key, Node->m_Data, ParentKey,LeftKey, RightKey);
		InOrder(Func, Node->m_Right);

	}

public:
	void PostOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&))
	{
		PostOrder(Func, m_Root);
	}
private:
	void PostOrder(void (*Func)(const int&, const int&, const int&, const int&, const int&), PNODE Node)
	{
		if (!Node)
			return;

		int ParentKey = 0, RightKey = 0, LeftKey = 0;

		if (Node->m_Parent)
			ParentKey = Node->m_Parent->m_Key;
		if (Node->m_Right)
			RightKey = Node->m_Right->m_Key;
		if (Node->m_Left)
			LeftKey = Node->m_Left->m_Key;


		PostOrder(Func, Node->m_Left);
		PostOrder(Func, Node->m_Right);

		Func(Node->m_Key, Node->m_Data, ParentKey, LeftKey, RightKey);

	}

	//회전 함수
	//회전을 하게 되면 노드들의 위치가 바뀌고, 인자로 들어온 기준 노드도 바뀌게 되므로
	//다시 기준노드가 되어야 할 노드를 반환해주는 타입의 함수를 만든다.
	//이해가 안되면, 그림을 그려서 회전하는 상황을 그린 후, 코드를 작성해보자.
	PNODE RotationRight(PNODE Node)
	{
		//기준노드의 부모노드를 얻어온다.(마지막에 정리하고 다시 연결해줄 예정)
		PNODE Parent = Node->m_Parent;

		//기준노드의 왼쪽 자식노드가 기준노드로 되어야 하므로 
		//왼쪽 자식노드를 얻어온다.
		PNODE LeftChild = Node->m_Left;

		//왼쪽 자식노드의 오른쪽 자식의 노드 주소를 얻어온다.
		//nullptr이 들어와도 괜찮다.
		PNODE LeftChildRight = LeftChild->m_Right;


		//만약 LeftChildRight가 존재하면 연결될 것이고
		//LeftChildRight이 nullptr이면 연결이 해제될 것이다.
		Node->m_Left = LeftChildRight;


		//가족관계 정리
		if (LeftChildRight)
			LeftChildRight->m_Parent = Node;


		//기준노드는 왼쪽 자식노드의 오른쪽 자식이 된다.
		LeftChild->m_Right = Node;
		Node->m_Parent = LeftChild;



		//기준 노드의 부모노드가 없었다면 Parent는 nullptr일 것이다.
		//(부모노드가 없었다면 그대로 nullptr이 들어가므로 
		//직접 nullptr을 넣어줄 필요가 없음.)
		LeftChild->m_Parent = Parent;
		
		//부모노드가 있으면 다시 부모노드를 추가해주고
		if (Parent)
		{
			//부모노드의 왼쪽에 붙어있었는지 오른쪽에 붙어있었는지 생각해야 됨.
			if(Node == Parent->m_Left)
			{
				Parent->m_Left = LeftChild;
			}
			else
			{
				Parent->m_Right = LeftChild;
			}
			
			
		}
		else
			m_Root = LeftChild;
		

		


		//이제 기준 노드는 Child가 되었다.
		return LeftChild;
		
	}

	PNODE RotationLeft(PNODE Node)
	{//기준노드의 부모노드를 얻어온다.(마지막에 정리하고 다시 연결해줄 예정)
		PNODE Parent = Node->m_Parent;

		//기준노드의 왼쪽 자식노드가 기준노드로 되어야 하므로 
		//왼쪽 자식노드를 얻어온다.
		PNODE RightChild = Node->m_Right;

		//왼쪽 자식노드의 오른쪽 자식의 노드 주소를 얻어온다.
		//nullptr이 들어와도 괜찮다.
		PNODE RightChildLeft = RightChild->m_Left;


		//만약 RightChildLeft가 존재하면 연결될 것이고
		//RightChildLeft이 nullptr이면 연결이 해제될 것이다.
		Node->m_Right = RightChildLeft;


		//가족관계 정리
		if (RightChildLeft)
			RightChildLeft->m_Parent = Node;


		//기준노드는 왼쪽 자식노드의 오른쪽 자식이 된다.
		RightChild->m_Left = Node;
		Node->m_Parent = RightChild;



		//기준 노드의 부모노드가 없었다면 Parent는 nullptr일 것이다.
		//(부모노드가 없었다면 그대로 nullptr이 들어가므로 
		//직접 nullptr을 넣어줄 필요가 없음.)
		RightChild->m_Parent = Parent;

		//부모노드가 있으면 다시 부모노드를 추가해주고
		if (Parent)
		{
			//부모노드의 왼쪽에 붙어있었는지 오른쪽에 붙어있었는지 생각해야 됨.
			if (Node == Parent->m_Left)
			{
				Parent->m_Left = RightChild;
			}
			else
			{
				Parent->m_Right = RightChild;
			}


		}
		else
			m_Root = RightChild;



		//이제 기준 노드는 Child가 되었다.
		return RightChild;
	}



	int GetHeight(PNODE Node)
	{
		//없으면 0
		if (!Node)
			return 0;

		//있으면 없을때까지 계속 내려간다.
		int Left = GetHeight(Node->m_Left);
		int Right = GetHeight(Node->m_Right);

		//둘 다 기준 노드에서 리프 노드까지 끝까지 내려가면서 높이를 구해올 것이다

		//둘 중 높이 값이 더 큰 곳의 값을 반환.
		int Height = Left > Right ? Left : Right;

		//1을 더해주는 이유: 함수 호출을 기준 노드의 자식 노드들부터 시작하므로
		//기준 노드와의 높이 차이가 반영되지 않음 -> 1을 더해주어 반영시킴.
		return Height + 1;
	}



	//들어온 노드를 기준으로 왼쪽 child와 오른쪽 child의 높이 차이를 구할 것임.
	int BalanceFactor(PNODE Node)
	{
		//기준 노드의 왼쪽과 오른쪽의 높이를 각각 구해온다.
		//각각 함수는 개별적으로 동작하여 재귀함수를 통해 
		//가장 큰 높이차이를 구해올 것이다.
		//두 값을 빼 주면, 양쪽의 높이차이를 구해줄 수 있게 된다.
		return GetHeight(Node->m_Left) - GetHeight(Node->m_Right);
	}

	
	//기준노드를 하나 받아서 기준으로 추가
	//기준노드가 들어오면 부모노드를 하나하나 타고 올라가면서
	//루트 노드까지 높이 차이를 체크하기 시작한다.
	void Rebalance(PNODE Node)
	{
		//루트까지 모두 완료되었을 경우 작업을 종료한다.
		//루트의 Parent 노드는 nullptr
		if (!Node)
			return;

		int Factor = BalanceFactor(Node);


		//균형이 무너졌으면 회전을 통해 균형을 복구해 준다.
		//오른쪽으로 트리의 균형이 무너졌을 경우
		if (Factor <= -2)
		{
			/*오른쪽으로 트리의 균형이 무너진 경우는 두 가지 경우의 수가 있다.
			* RR
				1
				 \
				  2
				   \
				    3
				또는

			* RL
				1
				 \
				  3
				 /
				2

				이것을 판별하기 위해서는, 기준 노드의 오른쪽 자식 노드를 기준으로
				BalanceFactor()함수를 돌려 준다.
				왼쪽의 높이 - 오른쪽의 높이 이므로 전자는 -1이 나올 것이고(RR)
				후자는 +1이 나올 것이다.
			
			*/
			int RightFactor = BalanceFactor(Node->m_Right);

			if (RightFactor <= 0)
			{
				//회전하면 기준노드가 새로 바뀌므로 새 노드를 기준 노드로 바꿔준다.
				Node = RotationLeft(Node);
			}
			else
			{
				/*
				* RL
				1
				 \
				  3
				 /
				2
				* 3(기준 노드의 오른쪽 자식)를 중심으로 우회전을 하면 
				1
				 \
				  2
				   \
				    3
				-> 이 상태에서 기준 노드를 왼쪽으로 회전을 하면 수정 완료.
				*/

				RotationRight(Node->m_Right);
				Node = RotationLeft(Node);
			}

		}
		
		//왼쪽으로 트리의 균형이 무너졌을 경우
		else if (Factor >= 2)
		{
			/*
			* LL
			    1
			   /
			  2
			 /
			3
			또는
			* LR
				1
			   /
			  3
			   \
			    2
			*/
			int LeftFactor = BalanceFactor(Node->m_Left);

			if (LeftFactor >= 0)
			{
				//회전하면 기준노드가 새로 바뀌므로 새 노드를 기준 노드로 바꿔준다.
				Node = RotationRight(Node);
			}
			else
			{
				/*
					* RL
					1
				   /
				  3
				   \
					2
				* 3(기준 노드의 왼쪽 자식)을 기준으로 우회전을  하면
					1
				   /
				  2
				 /
				3
				이 될 것임. 이 상태에서 1 기준으로 좌회전을 하면 
				*/
				RotationLeft(Node->m_Left);
				Node = RotationRight(Node);
			}
			


		}

		//재귀를 통해 루트노드까지 타고 가며 작업을 반복한다.
		Rebalance(Node->m_Parent);

	}

};