08/21

바이너리 서치 트리 + 파일 읽기 복습
바이너리 서치 트리를 상속하는 class를 하나 만든다
이 class는 엑셀이나, 텍스트, XML 파일(택 1)을 읽어와 Key 값만 콘솔화면에 뿌려주고
콘솔에서 Key를 입력받아 해당하는 Key의 모든 값을 뿌려주는 코드 만들기

힙 트리 구현

힙 트리
힙 트리는 힙 정렬을 위해 쓰인다.
힙 트리는 완전 이진 트리의 형태를 가진다.
다만 힙 트리는 depth 가 낮은 것이 더 작은 값을 가지긴 하지만 left와 right 중 어느 쪽이 더 크고 작은지는 알 수 없다.
완전 이진트리의 형태를 가지므로 height와 node 개수, depth에 아래와 같은 식이 성립한다.
depth = height - 1
특정 depth의 node 개수 = 2^(h-1)

힙 트리 삽입
완전 이진 트리의 형태를 가지도록 왼쪽부터 빈 depth가 없도록 채워넣는다.
이후 up heap 을 통해 재정렬한다.

up heap
새로 추가된 키 값을 부모 키 값과 비교한다. 새로 추가된 키 값이 더 작으면 부모와 위치를 바꾼다.
이를 부모가 없어지거나(루트) 부모값이 더 작을 때까지 반복한다.

힙 트리 제거
삭제할 노드와 가장 최근 추가된 노드의 위치를 변경한다.
이제는 라스트 노드에 위치하게 된 삭제할 노드를 지운다.
삭제할 노드 자리에 들어가게된 노드에 대해서 down heap으로 정렬한다.

down heap
새 자리에 들어간 노드의 자식들 중 더 작은 키 값을 가진 자식 노드와 현재 노드를 비교한다.
현재 노드가 더 작으면 현재 노드와 자식 노드의 위치를 바꾼다
이를 현재 노드가 external 노드가 되거나 자식 노드의 값이 더 클 때까지 반복한다.

인덱스 찾는 법
숫자 n의 바로 위에 적힌 숫자: (n-1)/2
숫자 n의 왼쪽 아래의 숫자: 2n + 1
숫자 n의 오른쪽 아래의 숫자: 2n + 2

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

namespace LearnAlgorithm_DataStructure
{
    public struct hNode<K, V> where K : IComparable
    {
        public K Key;
        public V Value;

        public hNode(K key, V value)
        {
            Key = key;
            Value = value;
        }
    }

    class MyHeapTree<K, V> where K : IComparable
    {
        private List<hNode<K, V>> Nodes = new List<hNode<K, V>>();
        public int Count { get { return Nodes.Count; } }

        public void Add(K key, V val)
        {
            if (IsKeyExist(key))
            {
                Console.WriteLine($"Add : 이미 존재하는 키({key})입니다.");
                return;
            }

            Nodes.Add(new hNode<K, V>(key, val));
            UpHeap();
        }

        public hNode<K, V> Pop()
        {
            int index = 0;

            hNode<K, V> node = Nodes[index];

            ChangeNodeByIndex(index, Nodes.Count - 1);
            Nodes.RemoveAt(Nodes.Count - 1);
            DownHeap(index);

            return node;
        }

        public hNode<K, V> Pop(K key)
        {
            int index = FindIndex(key);

            if(index < 0)
            {
                Console.WriteLine($"Remove : 존재하지 않는 키({key})입니다.");
                return default;
            }

            hNode<K, V> node = Nodes[index];

            ChangeNodeByIndex(index, Nodes.Count - 1);
            Nodes.RemoveAt(Nodes.Count - 1);
            DownHeap(index);

            return node;
        }

        /// <summary>
        /// key 값으로 Nodes 에서의 index 값 찾기, 없으면 -1
        /// </summary>
        /// <param name="key">키 값</param>
        /// <returns>해당 키 값의 노드를 가지고 있는 Nodes의 인덱스 번호. 없으면 -1</returns>
        private int FindIndex(K key)
        {
            for (int i = 0; i < Nodes.Count; i++)
            {
                hNode<K, V> node = Nodes[i];
                if (key.Equals(node.Key))
                {
                    return i;
                }
            }

            return -1;
        }

        private bool IsKeyExist(K key)
        {
            return FindIndex(key) != -1;
        }

        private void UpHeap(int index = -1)
        {
            if(index < 0)
            {
                index = Nodes.Count - 1;
            }

            int upIndex = GetparentIndex(index);
            while (upIndex >= 0 && index != upIndex)
            {
                if (Nodes[upIndex].Key.CompareTo(Nodes[index].Key) < 0)
                {
                    break;
                }

                ChangeNodeByIndex(index, upIndex);

                index = upIndex;
                upIndex = GetparentIndex(index);
                if(upIndex < 0)
                {
                    break;
                }
            }
        }

        private void DownHeap(int index)
        {
            int leftIndex = GetLeftIndex(index);
            int rightIndex = GetRightIndex(index);
            int downIndex;

            if(rightIndex >= Count)
            {
                downIndex = leftIndex;
            }
            else
            {
                if(Nodes[leftIndex].Key.CompareTo(Nodes[rightIndex].Key) < 0)
                {
                    downIndex = leftIndex;
                }
                else
                {
                    downIndex = rightIndex;
                }
            }

            if (downIndex < Nodes.Count)
            {
                if (Nodes[index].Key.CompareTo(Nodes[downIndex].Key) > 0)
                {
                    ChangeNodeByIndex(index, downIndex);
                    DownHeap(downIndex);
                }
            }
        }

        private static int GetparentIndex(int index)
        {
            return (index - 1) / 2;
        }

        private static int GetLeftIndex(int index)
        {
            return index * 2 + 1;
        }

        private static int GetRightIndex(int index)
        {
            return index * 2 + 2;
        }

        private void ChangeNodeByIndex(int index1, int index2)
        {
            hNode<K, V> tmp = Nodes[index1];
            Nodes[index1] = Nodes[index2];
            Nodes[index2] = tmp;
        }

        public void Print(int index = 0, string locate = "ROOT")
        {
            Console.WriteLine($"({Nodes[index].Key}, {Nodes[index].Value}) : {locate}");

            int leftIndex = GetLeftIndex(index);
            if (leftIndex <= Nodes.Count - 1)
            {
                Print(leftIndex, locate + " L");
            }
            else
            {
                return;
            }

            int rightIndex = GetRightIndex(index);
            if (rightIndex <= Nodes.Count - 1)
            {
                Print(rightIndex, locate + " R");
            }
            else
            {
                return;
            }
        }
    }
}

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();
			//BinarySearchTreeExcel();
			HeapTest();


            Console.ReadKey();
		}

		static void HeapTest()
		{
			var tree = new MyHeapTree<int, string>();
			Console.WriteLine("=== Add : 100, 50, 51, 49, 150, 151, 149, 149 ===");
			tree.Add(100, "나보기가");
			tree.Add(50, "역겨워");
			tree.Add(51, "가실");
			tree.Add(49, "때에는");
			tree.Add(150, "죽어도");
			tree.Add(151, "눈물아니");
			tree.Add(149, "흘리오리다");

			tree.Add(149, "흘리오리다"); // 동일 키 입력 시 메시지 확인
			Console.WriteLine();

			tree.Print();
			Console.WriteLine();


			Console.WriteLine("=== Pop ===");
			tree.Pop();
			tree.Print();
			Console.WriteLine();


			Console.WriteLine("=== Pop : 49 ===");
			tree.Pop(49); // 존재하지 않는 키 입력 시 메시지 확인
			Console.WriteLine();


			Console.WriteLine("=== Pop : 150 ===");
			tree.Pop(150);
			tree.Print();
			Console.WriteLine();


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

		}
	}
}