[멋쟁이사자처럼 부트캠프 TIL 회고] 유니티 게임개발 3기 15일차 자료구조(Tree)

Tree

• 트리는 계층적 구조를 표현하는 비선형 자료구조로, 노드들과 노드들을 연결하는 간선들로 구성되어 있다.

트리의 주요 특징

• 하나의 루트 노드를 가진다.
• 각 노드는 0개 이상의 자식 노드를 가질 수 있다.
• 사이클이 존재하지 않는다.

트리의 종류

• 일반 트리 (General Tree): 노드가 임의의 수의 자식을 가질 수 있는 트리
• 이진 트리 (Binary Tree): 각 노드가 최대 2개의 자식을 가질 수 있는 트리
• 완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리
• 포화 이진 트리 (Perfect Binary Tree): 모든 내부 노드가 2개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있는 트리
• 이진 탐색 트리 (Binary Search Tree): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리
• AVL 트리: 자동으로 균형을 맞추는 이진 탐색 트리로, 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1
• 레드-블랙 트리 (Red-Black Tree): 자가 균형 이진 탐색 트리의 일종으로, 색상 속성을 사용하여 균형을 유지한다.

트리의 순회 방법

• 전위 순회 (Preorder): 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
• 중위 순회 (Inorder): 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
• 후위 순회 (Postorder): 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
• 레벨 순회 (Level-order): 루트부터 레벨별로 왼쪽에서 오른쪽으로 순회

레드블랙 트리

• 모든 새로운 노드는 Red로 삽입된다다 (조건 1)
• 루트 노드는 항상 Black으로 유지된다 (조건 2)
• NIL 노드는 Black으로 처리된다 (조건 3)
• Red 노드의 자식들은 Black이 되도록 보장된다 (조건 4)
• 모든 경로의 Black 높이가 같도록 유지된다 (조건 5)

레드블랙 트리 구현

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class RedBlackTree : MonoBehaviour
{
    //노드 색상 정의하는 열거형
    private enum NodeColor
    {
        Red, Black
    }
    // 노드 class
    private class Node
    {
        public int data;
        public Node left, right, parent;
        public NodeColor color;
        
        // 새로운 노드는 항상 Red
        public Node(int data)
        {
            this.data = data;
            left = right = parent = null;
            color = NodeColor.Red;
        }

        private Node root;
        private Node TNULL; // NIL node

        void Start()
        {
            // NIL 노드는 항상 Black
            TNULL = new Node(0);
            TNULL.color = NodeColor.Black;
            root = TNULL;
        }
        
        // 삽입 시 트리 재조정을 위한 좌회전
        private void LeftRotate(Node x)
        {
            Node y = x.right;
            x.right = y.left;

            if (y.left != TNULL)
                y.left.parent = x;
            
            y.parent = x.parent;

            if (x.parent == null)
                root = y;
            else if(x == x.parent.left)
                x.parent.left = y;
            else
                x.parent.right = y;
        }
        
        // 삽입 시 트리 재조정을 위한 우회전
        private void RightRotate(Node x)
        {
            Node y = x.left;
            x.left = y.right;
            
            if(y.right != TNULL)
                y.right.parent = x;
            
            y.parent = x.parent;
            
            if(x.parent == null)
                root = y;
            else if (x == x.parent.right)
                x.parent.right = y;
            else
                x.parent.left = y;

            y.right = x;
            x.parent = y;
        }
        
        // 노드 삽입
        public void Insert(int key)
        {
            Node node = new Node(key);
            node.left = TNULL;
            node.right = TNULL;

            Node y = null;
            Node x = root;
            
            // 삽입 위치 찾기
            while (x != TNULL)
            {
                y = x;
                if(node.data < x.data)
                    x = x.left;
                else
                    x = x.right;
            }
            
            node.parent = y;

            if (y == null)
                root = node;
            else if (node.data < y.data)
                y.left = node;
            else
                y.right = node;

            InsertFixup(node);
        }
        // 삽입 후 레드-블랙 트리 속성 복구
        private void InsertFixup(Node k)
        {
            Node u;
            while (k.parent != null && k.parent.color == NodeColor.Red)
            {
                if (k.parent == k.parent.left)
                {
                    u = k.parent.left;
                    // case 1 : 삽촌 노드가 red
                    if (u.color == NodeColor.Red)
                    {
                        // 색상 변경으로 해결
                        u.color = NodeColor.Black;
                        k.parent.color = NodeColor.Black;
                        k.parent.parent.color = NodeColor.Red;
                        k = k.parent.parent;
                    }
                    else
                    {
                        // case 2 & 3 : 삼촌 노드가 black
                        if (k == k.parent.left)
                        {
                            k = k.parent;
                            RightRotate(k);
                        }
                        // 색상 변경 및 회전으로 해결
                        k.parent.color = NodeColor.Black;
                        k.parent.parent.color = NodeColor.Red;
                        LeftRotate(k.parent.parent);
                    }
                }
                else
                {
                    // 위의 경우의 대칭
                    u = k.parent.parent.right;
                    if (u.color == NodeColor.Red)
                    {
                        u.color = NodeColor.Black;
                        k.parent.color = NodeColor.Black;
                        k.parent.parent.color = NodeColor.Red;
                        k = k.parent.parent;
                    }
                    else
                    {
                        if (k == k.parent.right)
                        {
                            k = k.parent;
                            LeftRotate(k);
                        }

                        k.parent.color = NodeColor.Black;
                        k.parent.parent.color = NodeColor.Red;
                        RightRotate(k.parent.parent);
                    }
                }

                if (k == root)
                    break;
            }
            root.color = NodeColor.Black;
        }
    }
}