08/23

AVL 트리 완성

using System;
using System.Collections.Generic;

namespace LearnAlgorithm_DataStructure
{
	public class AVL_Node
	{
		public object Key;
		public object Value;
		public AVL_Node Left;
		public AVL_Node Right;
		public int Height = 1;
		public int Balance { get { return AVL_Tree.GetHeight(Left) - AVL_Tree.GetHeight(Right); } }

		public AVL_Node(object key, object value)
		{
			Key = key;
			Value = value;
			Left = null;
			Right = null;
		}

		public AVL_Node(object key, object value, AVL_Node left, AVL_Node right)
		{
			Key = key;
			Value = value;
			Left = left;
			Right = right;
		}
	}

	class AVL_Tree
	{
		private AVL_Node Root = null;

		public void Add(object newKey, object newValue)
		{
			if (Root == null)
			{
				Root = new AVL_Node(newKey, newValue);
				return;
			}

			Add(newKey, newValue, ref Root);
		}

		private void Add(object newKey, object newValue, ref AVL_Node parentNode)
		{
			int compare = Comparer<object>.Default.Compare(parentNode.Key, newKey);

			if (compare == 0)
			{
				Console.WriteLine($"Add : 동일한 Key({newKey})가 이미 존재합니다.");
				return;
			}

			if (compare > 0)
			{
				if (parentNode.Left == null)
				{
					parentNode.Left = new AVL_Node(newKey, newValue);
					UpdateNode(ref parentNode);
					return;
				}

				Add(newKey, newValue, ref parentNode.Left);
				UpdateNode(ref parentNode);
				return;
			}

			if (compare < 0)
			{
				if (parentNode.Right == null)
				{
					parentNode.Right = new AVL_Node(newKey, newValue);
					UpdateNode(ref parentNode);
					return;
				}

				Add(newKey, newValue, ref parentNode.Right);
				UpdateNode(ref parentNode);
				return;
			}

			Console.WriteLine("Add : 알 수 없는 오류입니다.");
			return;
		}

		public void Remove(object removeKey)
		{
			if (Root == null)
			{
				Console.WriteLine($"Remove : 삭제 할 키({removeKey})를 찾을 수 없습니다. 빈 트리입니다.");
				return;
			}

			Remove(removeKey, ref Root);
		}

		private void Remove(object removeKey, ref AVL_Node node)
		{
			int compare = Comparer<object>.Default.Compare(node.Key, removeKey);

			if (compare > 0)
			{
				if (node.Left == null)
				{
					Console.WriteLine($"Remove : 삭제 할 키({removeKey})를 찾을 수 없습니다.");
					return;
				}

				if(Comparer<object>.Default.Compare(node.Left.Key, removeKey) == 0)
				{
					RemoveNodeFromParent(ref node, true);
					UpdateNode(ref node);
					return;
				}

				Remove(removeKey, ref node.Left);
				UpdateNode(ref node);
				return;
			}

			if (compare < 0)
			{
				if (node.Right == null)
				{
					Console.WriteLine($"Remove : 삭제 할 키({removeKey})를 찾을 수 없습니다.");
					return;
				}

				if (Comparer<object>.Default.Compare(node.Right.Key, removeKey) == 0)
				{
					RemoveNodeFromParent(ref node, false);
					UpdateNode(ref node);
					return;
				}

				Remove(removeKey, ref node.Right);
				UpdateNode(ref node);
				return;
			}

			if(compare == 0)
			{
				// 부모가 없는 경우 ( Root 노드인 경우)
                RemoveNodeFromParent(ref Root, null);
				UpdateNode(ref Root);
				return;
            }

			Console.WriteLine("Remove : 알 수 없는 오류입니다.");
			return;
		}

		private void RemoveNodeFromParent(ref AVL_Node parentNode, bool? removeLeft = true)
		{
			// 삭제할 노드 참조
			AVL_Node removeNode;
            if (removeLeft == true)
			{
				removeNode = parentNode.Left;
			}
			else if(removeLeft == false)
			{
				removeNode = parentNode.Right;
			}
			else
			{
                //null 이면 Root 삭제할 때
                removeNode = Root;
			}

            if (removeNode.Left != null)
			{
				if (removeNode.Right != null)
				{
					// 삭제할 노드가 Left, Right 모두 있는 경우
					// 지워진 노드의 left중 가장 오른쪽의 노드와 그 부모 찾기
					AVL_Node Rightmost = removeNode.Left;
					AVL_Node Rightmost_Parent = removeNode;

					// 위치 바꾼 후 삭제할 때 쓸 값
					bool tmpFlag;
                    if (Rightmost.Right == null)
					{
                        tmpFlag = true; 
                    }
					else
					{
                        tmpFlag = false;
                    }


                    while (Rightmost.Right != null)
					{
						Rightmost_Parent = Rightmost;
						Rightmost = Rightmost.Right;
					}

					// 삭제 할 위치의 값을 왼쪽의 가장 오른쪽 노드의 값으로 변경
					removeNode.Key = Rightmost.Key;
					removeNode.Value = Rightmost.Value;

					// 왼쪽의 가장 오른쪽 노드 위치의 노드는 삭제
					if (tmpFlag)
					{
						Rightmost_Parent.Left = null;
                    }
					else
					{
                        Rightmost_Parent.Right = null;
                    }

                    return;
				}

				// 삭제할 노드가 right는 없고 left만 있는 경우
				removeNode.Key = removeNode.Left.Key;
				removeNode.Value = removeNode.Left.Value;
				removeNode.Left = removeNode.Left.Left;

				return;
			}

			// Right만 있는 경우, Right 쪽을 끌어올림
			if (removeNode.Right != null)
			{
				removeNode.Key = removeNode.Right.Key;
				removeNode.Value = removeNode.Right.Value;
				removeNode.Left = removeNode.Right.Left;
                removeNode.Right = removeNode.Right.Right;

                return;
			}

			// Root 노드를 지우는데, Root가 External Node인 경우
            if(removeLeft == null)
			{
                Root = null;
				return;
            }

            //Left도 Right도 없는 External Node를 지우는 경우
            if(removeLeft == true)
			{
                parentNode.Left = null;
				return;
            }

            parentNode.Right = null;
            return;
		}

		private void UpdateNode(ref AVL_Node node)
		{
			UpdateHeight(ref node);
			Restructure(ref node);
			UpdateHeight(ref node);
		}

		private void UpdateHeight(ref AVL_Node node)
		{
			node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
		}

		public static int GetHeight(AVL_Node node)
		{
			if (node == null)
			{
				return 0;
			}

			return node.Height;
		}

		private void Restructure(ref AVL_Node node)
		{
			if (Math.Abs(node.Balance) <= 1)
			{
				return;
			}

			// 재정리 실행
			if (node.Balance > 0)
			{
				// 좌편향
				if(node.Left != null && node.Left.Balance > 0)
				{
					RotateLL(ref node);
				}
				else
				{
					RotateLR(ref node);
				}
			}
			else
			{
				// 우편향
				if (node.Right != null && node.Right.Balance > 0)
				{
					RotateRL(ref node);
				}
				else
				{
					RotateRR(ref node);
				}
			}
		}

		// 왼쪽으로 연속 2개 편향 시 사용
		private void RotateLL(ref AVL_Node node)
		{
			var newRight = new AVL_Node(node.Key, node.Value, node.Left, node.Right);
			var newCenter = new AVL_Node(node.Left.Key, node.Left.Value, node.Left.Left, node.Left.Right);
			newRight.Left = node.Left.Right;
			newCenter.Right = newRight;
			node = newCenter;

			UpdateHeight(ref node.Right);
		}

		// 오른쪽으로 연속 2개 편향 시 사용
		private void RotateRR(ref AVL_Node node)
		{
			var newLeft = new AVL_Node(node.Key, node.Value, node.Left, node.Right);
			var newCenter = new AVL_Node(node.Right.Key, node.Right.Value, node.Right.Left, node.Right.Right);
			newLeft.Right = node.Right.Left;
			newCenter.Left = newLeft;
			node = newCenter;

            UpdateHeight(ref node.Left);
        }

		private void RotateLR(ref AVL_Node node)
		{
            // first Rotate (for R) make node tree LL
            var L = new AVL_Node(node.Left.Key, node.Left.Value);
            var LR = new AVL_Node(node.Left.Right.Key, node.Left.Right.Value);
			L.Left = node.Left.Left;
			L.Right = node.Left.Right.Left;
            LR.Left = L;
            LR.Right = node.Left.Right.Right;
			node.Left = LR;

            UpdateHeight(ref node.Left.Left);
            UpdateHeight(ref node.Left);

            // Second Rotate (for LL)
            RotateLL(ref node);
        }

		private void RotateRL(ref AVL_Node node)
		{
			// first Rotate (for L) make node tree RR
			var R = new AVL_Node(node.Right.Key, node.Right.Value);
            var RL = new AVL_Node(node.Right.Left.Key, node.Right.Left.Value);
			R.Left = node.Right.Left.Right;
			R.Right = node.Right.Right;
            RL.Left = node.Right.Left.Left;
            RL.Right = R;
			node.Right = RL;

            UpdateHeight(ref node.Right.Right);
            UpdateHeight(ref node.Right);

			// Second Rotate (for RR)
			RotateRR(ref node);
        }

		public void Print()
		{
			Print(Root);
		}

		private void Print(AVL_Node node, string locate = "ROOT")
		{
			if(node == null)
			{
				return;
			}

			Console.WriteLine($"({node.Key}, {node.Value}) {node.Height} {locate}");

			Print(node.Left, locate + " L");
			Print(node.Right, locate + " R");
		}
	}
}