[자료구조] 비선형 자료구조 Tree

1. Tree가 무엇인지 알고 있나요? Tree의 종류에는 어떤 것들이 있나요?

• 트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조로, 루트 노드에서 시작하여 자식 노드들이 연결되어 있는 형태를 가진다.

• 편향 트리 (Skewed Tree):
  • 모든 노드가 한쪽 방향으로만 치우친 트리.
• 이진 트리 (Binary Tree):
  • 각 노드가 최대 두 개의 자식 노드를 가지는 트리.
• 이진 탐색 트리 (Binary Search Tree, BST):
  • 왼쪽 서브트리에는 작은 값, 오른쪽 서브트리에는 큰 값을 가지는 이진 트리.
• 완전 이진 트리 (Complete Binary Tree):
  • 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있는 이진 트리.
• 포화 이진 트리 (Full Binary Tree):
  • 모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리.
• 균형 이진 트리 (Balanced Binary Tree):
  • 모든 서브트리의 높이 차이가 1 이하인 이진 트리.
• B 트리 (B-Tree):
  • 노드에 여러 키를 저장하고, 자식 노드의 수가 정해진 다진 트리.
  • 데이터베이스와 파일 시스템에서 사용.
• B+ 트리 (B+ Tree):
  • B 트리의 변형으로, 모든 키를 리프 노드에 저장하고, 리프 노드들이 연결 리스트로 연결됨.
• B 트리 (B Tree)
  • B+ 트리의 변형으로, 노드의 공간 활용도를 높이고 삽입, 삭제 시 재배열을 줄임.
• TRIE (Prefix Tree):
  • 문자열을 저장하고 검색하기 위한 트리 자료구조.
• 힙 트리 (Heap Tree)
  • 배열의 원소를 정렬하기 위한 트리 자료 구조로, 우선순위 큐를 구현할 때, 사용
  • 최소 힙, 최대 힙으로 나누어짐

---

2. 다음의 트리를 DFS로 방문할 때와 BFS로 방문할 때의 순서가 어떻게 될까요?

• DFS : 1 5 4 8 3 7 6 9 2
• BFS : 1 2 3 4 5 6 7 8 9

---

3. 아래와 같은 형식의 미니맵이 있습니다. 나의 현재 위치로부터 보스방까지 어떻게 가야 가장 빠르게 갈 수 있는지 체크하려고 합니다. DFS와 BFS 중 어느 방법이 더 적절할까요?

 

최단 경로를 알기 위해서는 가중치를 계산해야하기 때문에 BFS가 적절하다.

---

4. Tree의 순회(Traversal) 방법에 대해 설명해주세요.

• pre : VLR (루트 → 왼쪽 노드 → 오른쪽 노드)
• in : LVR (왼쪽 노드 → 루트 → 오른쪽 노드)
• post : LRV (왼쪽 노드 → 오른쪽 노드 → 루트)

---

5. DFS와 BFS에 대해 설명해주세요.

• DFS
  • 깊이 우선 탐색으로, 한 경로를 끝까지 탐색한 후에 다른 경로를 탐색한다.
  • 주로 모든 경로를 탐색하거나, 특정한 깊이까지의 경로를 탐색할 때 유용하다.
  • 단점 : 최단 경로를 보장하지 않는다.
• BFS
  • 너비 우선 탐색으로 현재 위치에서 가까운 노드부터 탐색하여 점차 멀리 있는 노드를 탐색한다.
  • 가까운 노드 부터 탐색을 하여 가중치를 구할 수 있기 때문에 최단 경로를 보장한다.

1. DFS와 BFS를 본인의 프로젝트에 활용한 경험이 있다면 설명해주세요.
   • 최단 거리를 구하기 위해서 BFS를 사용했다.

---

6. 행동 트리 (Behaviour Tree) 에 대해 설명해주세요.

https://husk321.tistory.com/412

• 행동을 Tree 구조로 만들어 AI의 행동을 제어하는 것이다.
• 행동을 트리 구조로 시각화할 수 있어, AI의 행동 흐름을 이해하기 쉽다.
• 각 행동 노드를 독립적으로 작성할 수 있어, 다른 행동 트리에서도 쉽게 재사용할 수 있다.
• 트리 구조를 쉽게 수정하고 확장할 수 있어, AI 행동의 복잡성을 유연하게 관리할 수 있다.

[Unity] Behaviour Tree에 관한 간단한 이야기

---

최소 힙 예제.cs

class Program
{
    static void Main(string[] args)
    {
        // 카드 풀 생성
        List<Card> cardPool = new List<Card>
            {
                new Card("Fireball", 5),
                new Card("Ice Bolt", 3),
                new Card("Healing Potion", 2),
                new Card("Shield", 4)
            };

        // 랜덤 객체 생성
        Random rand = new Random(1);

        // MinHeap 생성
        MinHeap<Card> cardHeap = new MinHeap<Card>();


        // 카드 풀에서 랜덤하게 5장의 카드를 뽑아 힙에 삽입
        for (int i = 0; i < 5; i++)
        {
            int randomIndex = rand.Next(cardPool.Count);
            cardHeap.Insert(cardPool[randomIndex]);
        }

        // TODO: cardHeap이 빌 때까지 가장 적은 비용의 카드만 내기
        while (cardHeap.Count > 0)
        {
            cardHeap.DisplayHeap();
            Card cardToPlay = cardHeap.ExtractMin();
            PlayCard(cardToPlay);
        }
    }

    static void PlayCard(Card card)
    {
        Console.WriteLine($"Playing card: {card}");
    }
}

public class Card : IComparable<Card>
{
    public string Name { get; set; }
    public int Cost { get; set; }

    public Card(string name, int cost)
    {
        Name = name;
        Cost = cost;
    }

    public int CompareTo(Card other)
    {
        if (other == null) return 1;
        return Cost.CompareTo(other.Cost);
    }

    public override string ToString()
    {
        return $"{Name} (Cost: {Cost})";
    }
}

public class MinHeap<T> where T : IComparable<T>
{
    private List<T> heap;

    public MinHeap()
    {
        heap = new List<T>();
    }

    public int Count => heap.Count;

    public void Insert(T item)
    {
        heap.Add(item);
        HeapifyUp(heap.Count - 1);
    }

    public T ExtractMin()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty.");

        T min = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);

        if (heap.Count > 0)
            HeapifyDown(0);

        return min;
    }

    public T Peek()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty.");

        return heap[0];
    }

    public void DisplayHeap()
    {
        Console.WriteLine("Current cards in heap:");
        foreach (T item in heap)
        {
            Console.WriteLine(item);
        }
        Console.WriteLine();
    }

    private void HeapifyUp(int index)
    {
        int parentIndex = (index - 1) / 2;

        if (index > 0 && heap[index].CompareTo(heap[parentIndex]) < 0)
        {
            Swap(index, parentIndex);
            HeapifyUp(parentIndex);
        }
    }

    private void HeapifyDown(int index)
    {
        int smallest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < heap.Count && heap[leftChild].CompareTo(heap[smallest]) < 0)
        {
            smallest = leftChild;
        }

        if (rightChild < heap.Count && heap[rightChild].CompareTo(heap[smallest]) < 0)
        {
            smallest = rightChild;
        }

        if (smallest != index)
        {
            Swap(index, smallest);
            HeapifyDown(smallest);
        }
    }

    private void Swap(int index1, int index2)
    {
        T temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}