Chapter 5-1. 트리 이론과 구현

Date: 2020.10.08 Updated: 2020.10.08

카테고리: Algorithm Lesson 2

태그: C Sharp Data Structure Graph Algorithm

인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click

Chapter 5. 트리

🚖 트리 이론

트리 👉 계층적 구조를 갖는 데이터를 위한 자료 구조 ex) 회사 조직도

노드(Node) : 데이터를 표현
- 루트 노드는 트리를 상징하며, 부모가 없다. 가장 조상이 되는 트리의 첫 노드.
- 잎(Leaf) 노드는 자식이 없는, 트리의 말단 노드들을 뜻한다.
간선(Edge) : 노드의 계층 구조를 표현하기 위해 사용
이름 그대로 나무와 같다. 뻗어 나가는 구조.

트리도 그래프의 일종이라고 볼 수 있다.

단, 제한적인 모양의 그래프.
- 트리는 사이클이 있어선 안된다. 👉 한 쪽 방향으로만 뻗어야 한다.
- 각 노드의 부모는 딱 하나만 있어야 한다.

트리는 재귀적인 속성을 가진다. 트리에서 일부분을 떼보면 그 부분도 트리다.(서브 트리)

🚖 트리 구현

트리는 재귀적 속성을 가진다.

트리이므로 사이클이 없고 각각 한 방향으로만 뻗어 내려갈 수 있다.
트리도 딱히 라이브러리에서 제공되지 않는다. 직접 구현해야 함.

트리 생성

using System;
using System.Collections.Generic;

namespace Excercise
{
    class TreeNode<T>
    {
        public T Data { get; set; }
        public List<TreeNode<T>> Children { get; set; } = new List<TreeNode<T>>();
    }

    class Program
    {
        static TreeNode<string> MakeTree()
        {
            TreeNode<string> root = new TreeNode<string>() { Data = "R1 개발실" };
            {
                {
                    TreeNode<string> node = new TreeNode<string>() { Data = "디자인팀" };
                    node.Children.Add(new TreeNode<string>() { Data = "전투" });
                    node.Children.Add(new TreeNode<string>() { Data = "경제" });
                    node.Children.Add(new TreeNode<string>() { Data = "스토리" });
                    root.Children.Add(node);
                }

                {
                    TreeNode<string> node = new TreeNode<string>() { Data = "프로그래밍팀" };
                    node.Children.Add(new TreeNode<string>() { Data = "서버" });
                    node.Children.Add(new TreeNode<string>() { Data = "클라" });
                    node.Children.Add(new TreeNode<string>() { Data = "엔진" });
                    root.Children.Add(node);
                }

                {
                    TreeNode<string> node = new TreeNode<string>() { Data = "아트팀" };
                    node.Children.Add(new TreeNode<string>() { Data = "배경" });
                    node.Children.Add(new TreeNode<string>() { Data = "캐릭터" });
                    root.Children.Add(node);
                }
            }

            return root;
        }


        static void Main(string[] args)
        {
            TreeNode<string> root = MakeTree();
        }
    }
}

TreeNode 하나의 노드
- 데이터 Data 를 가진다.
- 자식 노드들을 가진다.
  - Children 👉 해당 노드의 자식 노드들을 리스트에 저장
    - 오직 한 방향으로만 내려가므로 부모 노드를 굳이 저장하여 알아야 할 필요가 없다.
    - 자식 노드들이 누군지만 알면 됨.
트리 생성하기
- 루트 노드 root 부터 차례 차례 각각의 노드들의 Children 리스트에 자식 노드들을 추가해준다.
- root 루트 노드를 리턴한다.
  - 루트 노드만 알면 해당 트리 정보를 모두 얻은 것이나 마찬가지다. 오직 한 방향으로만 내려가므로.

트리 순회

        static void PrintTree(TreeNode<string> root)
        {
            // 현재 노드의 데이터 접근
            Console.WriteLine(root.Data);

            // 재귀적으로 자식들의 데이터 접근
            foreach (TreeNode<string> child in root.Children)
                PrintTree(child);
        }

        static void Main(string[] args)
        {
            TreeNode<string> root = MakeTree();

            PrintTree(root);

            Console.WriteLine(GetHeight(root));  // 2
        }

💎출력💎

R1 개발실
디자인팀
전투
경제
스토리
프로그래밍팀
서버
클라
엔진
아트팀
배경
캐릭터

트리는 재귀적 속성을 가진다는 것 기억하기!!

DFS 방식으로, 재귀적으로 자식 노드들에게 접근한다.

R1 개발실 ⭐
1. 디자인팀
2. 전투
3. 경제
4. 스토리
5. 프로그래밍팀
6. 서버
7. 클라
8. 엔진
9. 아트팀
10. 배경
11. 캐릭터

트리의 높이

이 트리의 높이는 2 이다. 디자인팀과 아트팀까지의 깊이는 1 이지만 트리의 높이는 가장 깊은 서브 트리를 기준으로 재기 때문에 프로그래밍팀 깊이인 2 에 맞춰, 이 트리의 높이는 2 이다.

        static int GetHeight(TreeNode<string> root)
        {
            int height = 0;

            foreach (TreeNode<string> child in root.Children)
            {
                int newHeight = GetHeight(child) + 1;
                if (height < newHeight)
                    height = newHeight;
                // 👉 height = Math.Max(height, newHeight); 와 같음
            }
            return height;
        }

        static void Main(string[] args)
        {
            TreeNode<string> root = MakeTree();

            PrintTree(root);

            Console.WriteLine(GetHeight(root));  // 2
        }

재귀적으로 트리의 높이는 (깊이가 가장 깊은 서브 트리의 깊이 + 1) 이어야 한다.
- 모든 자식들을 재귀적으로 순회 하여 깊이를 리턴한다.
  - 잎 노드들은 0 을 리턴한다.
- 더 큰 값의 깊이를 가진 서브 트리가 있다면 해당 깊이를 height로 업뎃한다.
  - 최대값 찾기 알고리즘

R1 개발실 ⭐
1. 디자인팀 - 0 리턴 👉 newHeight= 1
2. 프로그래밍팀 - 1 리턴 👉 newHeight= 2 ✔
3. 서버 - 0 리턴
4. 클라 - 0 리턴
5. 엔진 - 0 리턴
6. 아트팀 - 0 리턴 👉 newHeight= 1

따라서 리턴할 height는 2 가 된다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️