08/18

바이너리 서치 트리
Binary Tree에서 두 개의 추가적인 조건을 만족한 경우 이를 Binary Search Tree(이진 탐색 트리)라고 한다.

탐색 시
Root 부터 탐색한다
현재 방문한 Node의 key 값에 따라 다음 탐색 방향이 정해진다.
원하는 값을 찾지 못했다면 해당 Key값이 존재하지 않는 것

값 삽입
바이너리 트리와 동일

값 제거
삭제할 노드의 Left에 있는 노드 중 가장 큰 값(가장 오른쪽에 있는 값)을 찾는다. 그 값으로 삭제할 노드의 자리를 채운다.

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

namespace LearnAlgorithm_DataStructure
{
	public class bsNode<K, V> where K : IComparable
	{
		public K Key;
		public V Value;
		public bsNode<K, V> Parent, Left, Right;

		public bsNode()
		{
			Value = default(V);
			Parent = Left = Right = default(bsNode<K, V>);
		}

		public bsNode(K key, V value)
		{
			Key = key;
			Value = value;
			Parent = Left = Right = default(bsNode<K, V>);
		}

		public bsNode(K key, V value, bsNode<K, V> parent)
		{
			Key = key;
			Value = value;
			Parent = parent;
			Left = Right = default(bsNode<K, V>);
		}
	}

	class MyBinarySearchTree<K, V> where K : IComparable
	{
		private bsNode<K, V> Root;
		public int Count { get; private set; }

		public MyBinarySearchTree()
		{
			Root = null;
			Count = 0;
		}

		public bool Add(K key, V value)
		{
			if (Root == null)
			{
				Root = new bsNode<K, V>(key, value);
				Count++;
				return true;
			}

			return Add(key, value, Root);
		}

		// 재귀용
		private bool Add(K key, V value, bsNode<K, V> parentNode)
		{
			if (key.CompareTo(parentNode.Key) == 0)
			{
				Console.WriteLine($"Add : 동일한 키 값({key})이 입력되었습니다.");
				return false;
			}

			if (key.CompareTo(parentNode.Key) < 0)
			{
				if (parentNode.Left == default(bsNode<K, V>))
				{
					parentNode.Left = new bsNode<K, V>(key, value, parentNode);
					Count++;
					return true;
				}

				return Add(key, value, parentNode.Left);
			}
			else if (key.CompareTo(parentNode.Key) > 0)
			{
				if (parentNode.Right == default(bsNode<K, V>))
				{
					parentNode.Right = new bsNode<K, V>(key, value, parentNode);
					Count++;
					return true;
				}

				return Add(key, value, parentNode.Right);
			}

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

		public bool Remove(K key)
		{
			bsNode<K, V> removeNode = Find(key, Root);

            if (IsEmptyNode(removeNode) == true)
            {
                Console.WriteLine("Remove : 삭제할 노드가 존재하지 않습니다.");
				return false;
			}

			return Remove(ref removeNode);
		}

		private bool Remove(ref bsNode<K, V> node)
		{
			if (IsEmptyNode(node) == false)
			{
				bsNode<K, V> parent = node.Parent; //지워질 노드의 parent 값을 저장해둠
				bsNode<K, V> left = node.Left; //지워질 노드의 left 값을 저장해둠
				bsNode<K, V> right = node.Right; //지워질 노드의 Right 값을 저장해둠

				if (IsEmptyNode(left) == false)
				{
					if (IsEmptyNode(left.Right) == false)
					{
						bsNode<K, V> LastRightOfLeft = left.Right; // 지워진 노드의 right를 연결할 left중 가장 오른쪽의 노드를 찾기

						while (IsEmptyNode(LastRightOfLeft.Right) == false)
						{
							LastRightOfLeft = LastRightOfLeft.Right;
						}

						node.Key = LastRightOfLeft.Key;
						node.Value = LastRightOfLeft.Value;
						LastRightOfLeft.Parent.Right = default;

						Count--;
						return true;
					}

					// IsEmptyNode(left.Right) == true
					node.Key = left.Key;
					node.Value = left.Value;
					node.Left = left.Left;

					Count--;
					return true;
				}

				// Right만 있는 경우에만 Right 쪽을 끌어올림
				if (IsEmptyNode(right) == false)
				{
					node.Key = right.Key;
					node.Value = right.Value;
					node.Left = right.Left;
					node.Right = right.Right;

					Count--;
					return true;
				}

				//Left도 Right도 없는 External Node인 경우, 부모와 자신의 연결만 끊음
				if (parent.Left.Equals(node))
				{
					node.Parent.Left = null;
					node.Parent = null;
					return true;
				}

				if (node.Parent.Right.Equals(node))
				{
					node.Parent.Right = null;
					node.Parent = null;
					return true;
				}
			}

			Console.WriteLine("Remove : 알 수 없는 오류가 발생했습니다.");
			return false;
		}

		public bsNode<K, V> Find(K key, bsNode<K, V> node)
		{
			if (key.CompareTo(node.Key) == 0)
			{
				return node;
			}

			if(key.CompareTo(node.Key) > 0 && IsEmptyNode(node.Right) == false)
			{
				return Find(key, node.Right);
			}

			if (key.CompareTo(node.Key) < 0 && IsEmptyNode(node.Left) == false)
			{
				return Find(key, node.Left);
			}

            Console.WriteLine("Find : 값이 존재하지 않습니다.");
			return null;
		}

		protected static bool IsEmptyNode(bsNode<K, V> node)
		{
			return node == default(bsNode<K, V>);
		}

		public void Print(bsNode<K, V> node = default, string locate = default)
		{
			if (node == default)
			{
				node = Root;
			}

			if (locate == default)
			{
				locate = "Root";
			}

			Console.Write($"({node.Key}, {node.Value})");
			Console.WriteLine(" : " + locate);

			if (IsEmptyNode(node.Left) == false)
			{
				Print(node.Left, locate + " L");
			}

			if (IsEmptyNode(node.Right) == false)
			{
				Print(node.Right, locate + " R");
			}
		}

		public bool IsEmpty()
		{
			return Count == 0;
		}
	}
}

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

namespace LearnAlgorithm_DataStructure
{
	internal class Program
	{
		static void Main()
		{
			//ArrayListTest();
			//LinkedListTest();
			//QueueTest();
			//StackTest();
			//QueueArrayTest();
			//StackArrayTest();
			//BinaryTreeTest();
			//BinarySearchTreeTest();
			BinarySearchTreeFileTest();


			Console.ReadKey();
		}

        static void BinarySearchTreeFileTest()
		{

		}

        static void BinarySearchTreeTest()
		{
			var bsTree = new MyBinarySearchTree<int, int>();
			Console.WriteLine("=== Add : 100, 50, 51, 49, 150, 151, 149 ===");
			bsTree.Add(100, 1);
			bsTree.Add(50, 2);
			bsTree.Add(51, 3);
			bsTree.Add(49, 4);
			bsTree.Add(150, 5);
			bsTree.Add(151, 6);
			bsTree.Add(149, 7);

			bsTree.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove : 100 ===");
			bsTree.Remove(100);
			bsTree.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove : 50 ===");
			bsTree.Remove(50);
			bsTree.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove : 150 ===");
			bsTree.Remove(150);
			bsTree.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove : 51 ===");
			bsTree.Remove(51);
			bsTree.Print();
		}

		static void BinaryTreeTest()
		{
			var binaryTree = new MyBinaryTree<int>();
			Console.WriteLine("=== Add : 100, 50, 200, 150, 99, 10, 250 ===");
			binaryTree.Add(100);
			binaryTree.Add(50);
			binaryTree.Add(200);
			binaryTree.Add(150);
			binaryTree.Add(10);
			binaryTree.Add(99);
			binaryTree.Add(250);

			binaryTree.Print();


			Console.WriteLine("=== Remove : 100 ===");
			binaryTree.Remove(100);
			binaryTree.Print();

			Console.WriteLine("=== Remove : 10 ===");
			binaryTree.Remove(10);
			binaryTree.Print();

			Console.WriteLine("=== Remove : 200 ===");
			binaryTree.Remove(200);
			binaryTree.Print();
		}

		static void StackTest()
		{
			var myStack = new MyStack<string>();
			string first, second;
			Console.WriteLine("=== 값 3개 Push ===");
			myStack.Push("하나").Push("둘").Push("셋").Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 1개 Pop ===");
			first = myStack.Pop();
			Console.WriteLine($"Pop 결과 : {first}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 1개 Pop ===");
			myStack.Pop(out second);
			Console.WriteLine($"Pop 결과 : {second}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 3개 Push ===");
			myStack.Push("하나").Push("둘").Push("셋").Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 1개 Top ===");
			first = myStack.Top();
			Console.WriteLine($"Top 결과 : {first}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 1개 Top ===");
			myStack.Top(out second);
			Console.WriteLine($"Top 결과 : {second}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 1개 Pop ===");
			myStack.Pop(out second);
			Console.WriteLine($"Pop 결과 : {second}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();
		}

		static void StackArrayTest()
		{
			var myStack = new MyStackArray<string>();
			string first, second;
			Console.WriteLine("=== 값 3개 Push ===");
			myStack.Push("하나").Push("둘").Push("셋").Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== Pop ===");
			first = myStack.Pop();
			Console.WriteLine($"Pop 결과 : {first}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== Pop ===");
			myStack.Pop(out second);
			Console.WriteLine($"Pop 결과 : {second}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 3개 Push ===");
			myStack.Push("하나").Push("둘").Push("셋").Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("===  Top ===");
			first = myStack.Top();
			Console.WriteLine($"Top 결과 : {first}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== Top ===");
			myStack.Top(out second);
			Console.WriteLine($"Top 결과 : {second}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== Pop ===");
			myStack.Pop(out second);
			Console.WriteLine($"Pop 결과 : {second}");
			myStack.Print();
			Console.WriteLine($"Size : {myStack.Size()}");
			Console.WriteLine();
		}

		static void QueueTest()
		{
			var myQueue = new MyQueue<int>();
			int first, second;
			Console.WriteLine("=== 값 3개 EnQueue ===");
			myQueue.EnQueue(1).EnQueue(2).EnQueue(3).Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== DeQueue ===");
			first = myQueue.DeQueue();
			Console.WriteLine($"DeQueue 결과 : {first}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== DeQueue ===");
			myQueue.DeQueue(out second);
			Console.WriteLine($"DeQueue 결과 : {second}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 3개 EnQueue ===");
			myQueue.EnQueue(1).EnQueue(2).EnQueue(3).Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== Front ===");
			first = myQueue.Front();
			Console.WriteLine($"Front 결과 : {first}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== Front ===");
			myQueue.Front(out second);
			Console.WriteLine($"Front 결과 : {second}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== DeQueue ===");
			myQueue.DeQueue(out second);
			Console.WriteLine($"DeQueue 결과 : {second}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();
		}

		static void QueueArrayTest()
		{
			var myQueue = new MyQueue<int>();
			int first, second;
			Console.WriteLine("=== 값 3개 EnQueue ===");
			myQueue.EnQueue(1).EnQueue(2).EnQueue(3).Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== DeQueue ===");
			first = myQueue.DeQueue();
			Console.WriteLine($"DeQueue 결과 : {first}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== DeQueue ===");
			myQueue.DeQueue(out second);
			Console.WriteLine($"DeQueue 결과 : {second}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== 값 3개 EnQueue ===");
			myQueue.EnQueue(1).EnQueue(2).EnQueue(3).Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== Front ===");
			first = myQueue.Front();
			Console.WriteLine($"Front 결과 : {first}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== Front ===");
			myQueue.Front(out second);
			Console.WriteLine($"Front 결과 : {second}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();

			Console.WriteLine("=== DeQueue ===");
			myQueue.DeQueue(out second);
			Console.WriteLine($"DeQueue 결과 : {second}");
			myQueue.Print();
			Console.WriteLine($"Size : {myQueue.Size()}");
			Console.WriteLine();
		}

		static void LinkedListTest()
		{
			var myLinkedList = new MyLinkedList<object>();
			Console.WriteLine("=== 값 3개 Add ===");
			myLinkedList.Add(1);
			myLinkedList.Add(2);
			myLinkedList.Add(3);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Get, Set ===");
			Console.Write("GET : myLinkedList[1] = ");
			Console.WriteLine(myLinkedList[1]);
			Console.WriteLine("SET : myLinkedList[1] = 4;");
			myLinkedList[1] = 4;
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Insert(0, 5) ===");
			myLinkedList.Insert(0, 5);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Insert(2, 5) ===");
			myLinkedList.Insert(2, 5);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Insert(4, 5) ===");
			myLinkedList.Insert(4, 5);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove(5) ===");
			myLinkedList.Remove(5);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove(0) ===");
			myLinkedList.Remove(0);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove(3) ===");
			myLinkedList.Remove(3);
			myLinkedList.Print();
			Console.WriteLine();

			Console.WriteLine("=== Remove(1) ===");
			myLinkedList.Remove(1);
			myLinkedList.Print();
			Console.WriteLine();
		}

		static void ArrayListTest()
		{
			try
			{
				{
					var myArrayList = new MyArrayList<string>();

					Console.WriteLine("===== Count =====");
					myArrayList.test();
					Console.WriteLine($"IsEmpty : {myArrayList.IsEmpty}");
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== 1개 값 Add =====");
					myArrayList.Add("하나");
					myArrayList.test();
					Console.WriteLine($"IsEmpty : {myArrayList.IsEmpty}");
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== 7개 값 Add =====");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.Add("둘");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					// 8개 이후
					Console.WriteLine("===== 4개 값 Add =====");
					myArrayList.Add("셋");
					myArrayList.Add("셋");
					myArrayList.Add("셋");
					myArrayList.Add("셋");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Insert(0, \"넷\"); =====");
					myArrayList.Insert(0, "넷");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Insert(3, \"넷\"); =====");
					myArrayList.Insert(3, "넷");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Insert(-1, \"넷\"); =====");
					myArrayList.Insert(-1, "넷");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Insert(100, \"넷\"); =====");
					myArrayList.Insert(100, "넷");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Remove(0); =====");
					myArrayList.Remove(0);
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Remove(11); =====");
					myArrayList.Remove(11);
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== Remove(20); =====");
					myArrayList.Remove(20);
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== GET myArrayList[0] =====");
					Console.WriteLine(myArrayList[0]);
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();

					Console.WriteLine("===== SET myArrayList[0] = \"하나둘셋\" =====");
					Console.WriteLine(myArrayList[0] = "하나둘셋");
					myArrayList.test();
					Console.WriteLine();
					Console.WriteLine();
				}
			}
			catch (Exception ex)
			{
				Console.WriteLine(ex.ToString());
			}
		}
	}
}