[멋쟁이사자처럼 부트캠프 TIL] 유니티 게임 개발 3기 : 트리

트리

일반 트리 General Tree

n개의 자식 노드를 가진 트리

잘 안씀 : 그래프로 대체 가능

이진 트리 Binary Tree

각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리

완전 이진 트리 Complete Binary Tree

마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리

포화 이진 트리 Perfect Binary Tree

모든 내부 노드가 2개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있는 트리

AVL 트리

자동으로 균형을 맞추는 이진 탐색 트리로, 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1임

레드-블랙 트리 (Red-Black Tree)

자가 균형 이진 탐색 트리의 일종으로, 색상 속성을 사용하여 균형을 유지

B-트리

데이터베이스와 파일 시스템에서 사용되는 균형 검색 트리로, 노드당 여러 개의 키를 저장 가능

 

트리의 순회 방법

트리 순회 : 트리의 모든 노드를 체계적으로 방문하는 프로세스

주요 순회 방법

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

전위, 중위, 후위 순회 코드

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

public class BinaryTree : MonoBehaviour
{
    public class Node
    {
        public int data;
        public Node left;
        public Node right;

        public Node(int item)
        {
            data = item;
            left = right = null;
        }
    }

    private Node root;
    
    // 전위 순회 Preorder
    public void Preorder(Node node)
    {
        if (node == null) return;
        
        Debug.Log(node.data + " "); // root
        Preorder(node.left);
        Preorder(node.right);
    }
    
    // 중위 순회 Inorder
    public void Inorder(Node node)
    {
        if (node == null) return;
        
        Inorder(node.left);
        Debug.Log(node.data + " ");
        Inorder(node.right);
    }
    
    // 후위 순회 Postorder
    public void Postorder(Node node)
    {
        if (node == null) return;
        
        Postorder(node.left);
        Postorder(node.right);
        Debug.Log(node.data + " ");
    }
    
    void Start()
    {
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        
        Debug.Log("전위");
        Preorder(root);
        
        Debug.Log("중위");
        Inorder(root);
        
        Debug.Log("후위");
        Postorder(root);
    }
}

 

그래프 Graph

그래프는 노드(정점)들과 그들을 연결하는 간선들의 집합으로 이루어진 자료구조

트리와 달리 순환 허용

더 유연한 관계 표현 가능

그래프의 주요 특징

방향성: 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 구분

가중치: 간선에 비용이나 거리 등의 가중치를 부여 가능

순환성: 순환(Cycle)이 허용되어 한 노드에서 시작하여 같은 노드로 돌아올 수 있음

연결성: 모든 노드가 연결되어 있지 않을 수 있음

 

그래프의 주요 알고리즘

깊이 우선 탐색 (DFS): 한 방향으로 깊이 탐색하다가 더 이상 갈 수 없으면 백트래킹

너비 우선 탐색 (BFS): 현재 노드와 가까운 노드부터 탐색

다익스트라 알고리즘: 가중 그래프에서 최단 경로를 찾음

크루스칼 알고리즘: 최소 신장 트리를 찾는 알고리즘

 

그래프 구현(DFS, BFS, 다익스트라 알고리즘)

using System.Collections.Generic;
using UnityEngine;

public class Graph : MonoBehaviour
{
    // 정점을 나타내는 클래스
    public class Vertex
    {
        public string Name; // 정점의 이름
        public Dictionary<Vertex, float> Neighbors; // 이웃 정점과 해당 간선의 가중치 저장

        public Vertex(string name)
        {
            Name = name;
            // Dictionary는 키-값 쌍으로 데이터를 저장하며, 이 경우 이웃 정점(Vertex)과 가중치(float)를 저장
            Neighbors = new Dictionary<Vertex, float>();
        }
    }

    private Dictionary<string, Vertex> vertices; // 정점 이름을 키로 사용하는 Dictionary

    void Start()
    {
        // Dictionary 초기화: 정점을 효율적으로 관리하기 위해 사용
        vertices = new Dictionary<string, Vertex>();

        // 정점 추가
        AddVertex("A");
        AddVertex("B");
        AddVertex("C");
        AddVertex("D");

        // 간선 추가 (가중치가 있는 방향 그래프)
        AddEdge("A", "B", 1);
        AddEdge("A", "C", 1);
        AddEdge("B", "C", 1);
        AddEdge("B", "D", 1);
        AddEdge("C", "D", 1);

        // 탐색 및 최단 경로 출력
        Debug.Log("너비 우선 탐색 (BFS)");
        BFS("A");

        Debug.Log("깊이 우선 탐색 (DFS)");
        DFS("A");

        Debug.Log("다익스트라 최단 경로");
        Dijkstra("A");
    }

    /// <summary>
    /// 새로운 정점을 그래프에 추가
    /// </summary>
    public void AddVertex(string name)
    {
        // Dictionary에 정점 이름이 없는 경우 추가
        if (!vertices.ContainsKey(name))
        {
            vertices[name] = new Vertex(name); // 새 정점 생성 후 추가
            Debug.Log($"정점 {name} 추가됨");
        }
        else
        {
            Debug.Log($"정점 {name}은 이미 존재함");
        }
    }

    /// <summary>
    /// 두 정점 간의 간선(가중치 포함)을 추가
    /// </summary>
    public void AddEdge(string fromName, string toName, float weight)
    {
        // 정점 이름으로 Vertex 객체를 찾고 없으면 무시
        if (vertices.TryGetValue(fromName, out Vertex from) && vertices.TryGetValue(toName, out Vertex to))
        {
            // 간선 중복을 방지하기 위해 이미 있는지 확인
            if (!from.Neighbors.ContainsKey(to))
            {
                from.Neighbors[to] = weight; // 간선 추가
                Debug.Log($"간선 {fromName} -> {toName} (가중치: {weight}) 추가됨");
            }
            else
            {
                Debug.Log($"간선 {fromName} -> {toName}는 이미 존재함");
            }
        }
        else
        {
            Debug.Log($"간선을 추가하려면 {fromName} 또는 {toName} 정점이 존재해야 함");
        }
    }

    /// <summary>
    /// 너비 우선 탐색 (Breadth-First Search)
    /// </summary>
    public void BFS(string startName)
    {
        if (!vertices.TryGetValue(startName, out Vertex start))
        {
            Debug.Log($"시작 정점 {startName}이 존재하지 않습니다.");
            return;
        }

        var visited = new HashSet<Vertex>(); // 방문 여부를 저장 (중복 방지)
        var queue = new Queue<Vertex>(); // 탐색할 정점을 순서대로 저장

        queue.Enqueue(start); // 시작 정점을 큐에 추가
        visited.Add(start); // 방문 처리

        while (queue.Count > 0) // 큐가 빌 때까지 반복
        {
            var current = queue.Dequeue(); // 큐에서 정점을 꺼냄
            Debug.Log($"방문: {current.Name}");

            foreach (var neighbor in current.Neighbors.Keys) // 이웃 정점 탐색
            {
                if (!visited.Contains(neighbor)) // 아직 방문하지 않았다면
                {
                    visited.Add(neighbor); // 방문 처리
                    queue.Enqueue(neighbor); // 큐에 추가
                }
            }
        }
    }

    /// <summary>
    /// 깊이 우선 탐색 (Depth-First Search)
    /// </summary>
    public void DFS(string startName)
    {
        if (!vertices.TryGetValue(startName, out Vertex start))
        {
            Debug.Log($"시작 정점 {startName}이 존재하지 않습니다.");
            return;
        }

        var visited = new HashSet<Vertex>(); // 방문 여부를 저장
        DFSRecursive(start, visited); // 재귀 함수 호출
    }

    private void DFSRecursive(Vertex vertex, HashSet<Vertex> visited)
    {
        visited.Add(vertex); // 현재 정점을 방문 처리
        Debug.Log($"방문: {vertex.Name}");

        foreach (var neighbor in vertex.Neighbors.Keys) // 이웃 정점 탐색
        {
            if (!visited.Contains(neighbor)) // 아직 방문하지 않았다면
            {
                DFSRecursive(neighbor, visited); // 재귀 호출
            }
        }
    }

    /// <summary>
    /// 다익스트라 최단 경로 알고리즘
    /// </summary>
    public void Dijkstra(string startName)
    {
        if (!vertices.TryGetValue(startName, out Vertex start))
        {
            Debug.Log($"시작 정점 {startName}이 존재하지 않습니다.");
            return;
        }

        var distances = new Dictionary<Vertex, float>(); // 각 정점까지의 최단 거리
        var unvisited = new HashSet<Vertex>(vertices.Values); // 방문하지 않은 정점들

        foreach (var vertex in vertices.Values)
        {
            distances[vertex] = float.MaxValue; // 초기 거리를 무한대로 설정
        }
        distances[start] = 0; // 시작 정점의 거리는 0

        while (unvisited.Count > 0)
        {
            // 미방문 정점 중 가장 가까운 정점 찾기
            Vertex current = null;
            float minDistance = float.MaxValue;

            foreach (var vertex in unvisited)
            {
                if (distances[vertex] < minDistance)
                {
                    current = vertex;
                    minDistance = distances[vertex];
                }
            }

            if (current == null) break; // 더 이상 접근할 수 있는 정점이 없을 경우 종료
            unvisited.Remove(current); // 현재 정점을 방문 처리

            foreach (var neighbor in current.Neighbors)
            {
                // 현재 정점을 통해 이웃으로 가는 새로운 거리 계산
                float newDistance = distances[current] + neighbor.Value;
                if (newDistance < distances[neighbor.Key]) // 더 짧은 경로라면 업데이트
                {
                    distances[neighbor.Key] = newDistance;
                }
            }
        }

        // 최단 거리 결과 출력
        foreach (var vertex in vertices.Values)
        {
            Debug.Log($"{startName}에서 {vertex.Name}까지의 최단 거리: {distances[vertex]}");
        }
    }
}

 

Unity에서의 트리 구조 예제

주로 게임 오브젝트의 계층 구조나 AI 결정 트리 등에 사용

 

트리의 구조와 용어

• 노드 (Node): 트리를 구성하는 기본 요소로, 데이터를 저장
• 간선 (Edge): 노드와 노드를 연결하는 선
• 루트 노드 (Root Node): 트리의 최상위에 있는 노드
• 부모 노드 (Parent Node): 직접적인 상위 노드를 의미
• 자식 노드 (Child Node): 직접적인 하위 노드를 의미
• 리프 노드 (Leaf Node): 자식이 없는 노드로, 트리의 끝단에 위치
• 깊이 (Depth): 루트에서 특정 노드까지의 경로 길이
• 높이 (Height): 노드에서 가장 먼 리프까지의 경로 길이

 

트리의 종류

• 이진 트리 (Binary Tree): 각 노드가 최대 두 개의 자식을 가질 수 있는 트리
• 이진 탐색 트리 (Binary Search Tree): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리
• AVL 트리: 자가 균형 이진 탐색 트리로, 높이 차이가 1 이하로 유지됨
• 레드-블랙 트리: 자가 균형 이진 탐색 트리의 일종으로, 복잡한 균형 조건을 가짐
• B-트리: 이진 트리를 일반화한 균형 트리로, 데이터베이스와 파일 시스템에서 주로 사용

 

트리의 응용

• 파일 시스템: 디렉토리와 파일의 계층 구조를 표현
• HTML DOM: 웹 페이지의 구조를 트리 형태로 표현
• 컴파일러: 구문 분석 트리를 생성하여 코드를 해석
• 게임 AI: 결정 트리를 사용하여 AI의 행동을 결정
• 데이터베이스 인덱싱: B-트리나 B+트리를 사용하여 빠른 검색을 지원

 

AVL 트리 구현

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

/// <summary>
/// AVL 트리를 시각화하고 관리하는 클래스
/// AVL 트리는 균형 이진 검색 트리로, 삽입 또는 삭제 시마다 균형을 유지합니다.
/// </summary>
public class AVLTreeVisualizer : MonoBehaviour
{
    // AVL 트리의 노드 클래스
    private class Node
    {
        public int data; // 노드가 저장하는 데이터 값
        public Node left; // 왼쪽 자식 노드
        public Node right; // 오른쪽 자식 노드
        public int height; // 현재 노드의 높이
        public Vector2 position; // 시각화에서 노드의 2D 위치 좌표

        public Node(int data)
        {
            this.data = data; // 생성자에서 데이터 초기화
            this.height = 1; // 새로 생성된 노드의 초기 높이는 1
        }
    }

    private Node root; // 트리의 루트 노드

    /// <summary>
    /// Unity의 Start 메서드: 초기화 코드
    /// </summary>
    void Start()
    {
        // 트리에 1부터 9까지의 숫자를 삽입
        for (int i = 1; i <= 9; i++)
        {
            Insert(i);
        }

        // 각 노드의 화면 상 위치를 업데이트
        UpdatePositions(root, 0, 0, 2);
    }

    /// <summary>
    /// AVL 트리에 데이터를 삽입
    /// </summary>
    public void Insert(int data)
    {
        root = InsertRec(root, data); // 재귀적으로 삽입 작업 수행
    }

    /// <summary>
    /// 데이터를 AVL 트리에 재귀적으로 삽입하는 내부 메서드
    /// </summary>
    private Node InsertRec(Node node, int data)
    {
        // 빈 위치에 새 노드를 생성
        if (node == null) return new Node(data);

        // 데이터 비교를 통해 삽입 위치 결정
        if (data < node.data)
            node.left = InsertRec(node.left, data); // 왼쪽 하위 트리에 삽입
        else if (data > node.data)
            node.right = InsertRec(node.right, data); // 오른쪽 하위 트리에 삽입
        else
            return node; // 중복된 데이터는 삽입하지 않음

        // 삽입 후 높이를 업데이트하고 트리를 균형 상태로 만듦
        UpdateHeight(node);
        return Balance(node, data); // 균형을 유지하도록 조정
    }

    /// <summary>
    /// 노드의 높이를 반환
    /// </summary>
    private int Height(Node node)
    {
        // 노드가 null인 경우 높이는 0
        return node == null ? 0 : node.height;
    }

    /// <summary>
    /// 노드의 균형 인수를 계산
    /// </summary>
    private int GetBalance(Node node)
    {
        // 균형 인수는 왼쪽 높이 - 오른쪽 높이
        return node == null ? 0 : Height(node.left) - Height(node.right);
    }

    /// <summary>
    /// 노드의 높이를 업데이트
    /// </summary>
    private void UpdateHeight(Node node)
    {
        if (node != null)
        {
            // 현재 노드의 높이는 자식 노드들 중 더 큰 높이에 1을 더한 값
            node.height = Mathf.Max(Height(node.left), Height(node.right)) + 1;
        }
    }

    /// <summary>
    /// 트리의 특정 노드를 기준으로 오른쪽 회전
    /// </summary>
    private Node RightRotate(Node y)
    {
        // 회전 과정: 새로운 루트와 서브트리 재배치
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        // 높이를 다시 계산
        UpdateHeight(y);
        UpdateHeight(x);

        return x; // 새로운 루트 반환
    }

    /// <summary>
    /// 트리의 특정 노드를 기준으로 왼쪽 회전
    /// </summary>
    private Node LeftRotate(Node x)
    {
        // 회전 과정: 새로운 루트와 서브트리 재배치
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        // 높이를 다시 계산
        UpdateHeight(x);
        UpdateHeight(y);

        return y; // 새로운 루트 반환
    }

    /// <summary>
    /// 노드를 균형 상태로 유지
    /// </summary>
    private Node Balance(Node node, int data)
    {
        int balance = GetBalance(node); // 현재 노드의 균형 인수 계산

        // LL 케이스: 왼쪽 서브트리에서 삽입된 경우
        if (balance > 1 && data < node.left.data)
            return RightRotate(node);

        // RR 케이스: 오른쪽 서브트리에서 삽입된 경우
        if (balance < -1 && data > node.right.data)
            return LeftRotate(node);

        // LR 케이스: 왼쪽-오른쪽 형태 삽입
        if (balance > 1 && data > node.left.data)
        {
            node.left = LeftRotate(node.left); // 왼쪽 자식을 왼쪽 회전
            return RightRotate(node); // 그 후 오른쪽 회전
        }

        // RL 케이스: 오른쪽-왼쪽 형태 삽입
        if (balance < -1 && data < node.right.data)
        {
            node.right = RightRotate(node.right); // 오른쪽 자식을 오른쪽 회전
            return LeftRotate(node); // 그 후 왼쪽 회전
        }

        return node; // 균형 상태면 그대로 반환
    }

    /// <summary>
    /// 각 노드의 화면 상 위치를 계산
    /// </summary>
    private void UpdatePositions(Node node, float x, float y, float horizontalSpacing)
    {
        if (node == null) return;

        // 현재 노드의 위치 저장
        node.position = new Vector2(x, y);

        // 재귀적으로 왼쪽과 오른쪽 자식 위치 계산
        UpdatePositions(node.left, x - horizontalSpacing, y - 1.5f, horizontalSpacing / 2);
        UpdatePositions(node.right, x + horizontalSpacing, y - 1.5f, horizontalSpacing / 2);
    }

    /// <summary>
    /// Unity에서 노드와 간선을 그리기 위한 메서드
    /// </summary>
    private void OnDrawGizmos()
    {
        if (root != null)
        {
            DrawNode(root); // 루트 노드부터 그리기 시작
        }
    }

    /// <summary>
    /// 재귀적으로 각 노드를 그리고 연결선 추가
    /// </summary>
    private void DrawNode(Node node)
    {
        if (node == null) return;

        // 왼쪽 자식 노드와 연결선 그림
        if (node.left != null)
        {
            Gizmos.color = Color.white;
            Gizmos.DrawLine(new Vector3(node.position.x, node.position.y, 0),
                            new Vector3(node.left.position.x, node.left.position.y, 0));
        }

        // 오른쪽 자식 노드와 연결선 그림
        if (node.right != null)
        {
            Gizmos.color = Color.white;
            Gizmos.DrawLine(new Vector3(node.position.x, node.position.y, 0),
                            new Vector3(node.right.position.x, node.right.position.y, 0));
        }

        // 노드 자체를 원으로 표현
        Gizmos.color = Color.cyan;
        Gizmos.DrawSphere(new Vector3(node.position.x, node.position.y, 0), 0.2f);

        // 노드의 데이터와 높이를 표시
        UnityEditor.Handles.Label(new Vector3(node.position.x, node.position.y + 0.3f, 0),
            $"{node.data} (h: {node.height})");

        // 왼쪽과 오른쪽 자식도 그리기
        DrawNode(node.left);
        DrawNode(node.right);
    }
}

 

실행 결과

 

 

레드블랙트리 구현

개념은 아래 글 참고하면 좋을 것 같다

https://code-lab1.com/red-black-tree/

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

public class RedBlackTree : MonoBehaviour
{
    // 노드의 색상을 나타내는 열거형
    // RedBlackTree에서 노드는 Red(빨간색) 또는 Black(검은색) 중 하나의 색을 가집니다.
    private enum NodeColor
    {
        Red,   // 빨간색
        Black  // 검은색
    }

    // 레드-블랙 트리에서 사용하는 노드 클래스
    private class Node
    {
        public int data;          // 노드에 저장된 값
        public Node left, right;  // 왼쪽 자식 노드, 오른쪽 자식 노드
        public Node parent;       // 부모 노드
        public NodeColor color;   // 노드의 색상

        // 생성자: 새로운 노드를 만들 때 호출
        // 기본적으로 새 노드는 Red(빨간색)으로 생성됩니다. (레드-블랙 트리 규칙)
        public Node(int data)
        {
            this.data = data;         // 데이터 값 설정
            left = right = parent = null;  // 초기에는 자식이나 부모가 없음
            color = NodeColor.Red;    // 새 노드는 기본적으로 Red
        }
    }

    private Node root;  // 트리의 루트 노드 (트리의 시작점)
    private Node TNULL; // 특별한 NIL 노드, 레드-블랙 트리에서 빈 노드를 표현

    void Start()
    {
        // TNULL 노드는 항상 Black(검은색)이며, 빈 노드를 나타냅니다.
        // 이는 레드-블랙 트리의 규칙에서 사용하는 특수 노드입니다.
        TNULL = new Node(0);         // 데이터 값은 0 (사용되지 않음)
        TNULL.color = NodeColor.Black; // 항상 검은색
        root = TNULL;                 // 트리의 시작은 NIL 노드로 초기화
    }

    // 트리 재구성을 위한 "좌회전" 함수
    // 특정 노드를 기준으로 좌회전하여 트리의 균형을 맞춥니다.
    private void LeftRotate(Node x)
    {
        Node y = x.right;  // x의 오른쪽 자식 y를 가져옵니다.
        x.right = y.left;  // y의 왼쪽 자식을 x의 오른쪽 자식으로 설정

        if (y.left != TNULL)
            y.left.parent = x;  // y의 왼쪽 자식이 존재하면, 그 부모를 x로 설정

        y.parent = x.parent;  // y의 부모를 x의 부모로 변경

        if (x.parent == null)
            root = y;  // x가 루트라면 y가 새로운 루트가 됩니다.
        else if (x == x.parent.left)
            x.parent.left = y;  // x가 부모의 왼쪽 자식이라면, y가 왼쪽 자식이 됨
        else
            x.parent.right = y; // x가 부모의 오른쪽 자식이라면, y가 오른쪽 자식이 됨

        y.left = x;    // x를 y의 왼쪽 자식으로 설정
        x.parent = y;  // x의 부모를 y로 설정
    }

    // 트리 재구성을 위한 "우회전" 함수
    // 특정 노드를 기준으로 우회전하여 트리의 균형을 맞춥니다.
    private void RightRotate(Node x)
    {
        Node y = x.left;  // x의 왼쪽 자식 y를 가져옵니다.
        x.left = y.right; // y의 오른쪽 자식을 x의 왼쪽 자식으로 설정

        if (y.right != TNULL)
            y.right.parent = x;  // y의 오른쪽 자식이 존재하면, 그 부모를 x로 설정

        y.parent = x.parent;  // y의 부모를 x의 부모로 변경

        if (x.parent == null)
            root = y;  // x가 루트라면 y가 새로운 루트가 됩니다.
        else if (x == x.parent.right)
            x.parent.right = y;  // x가 부모의 오른쪽 자식이라면, y가 오른쪽 자식이 됨
        else
            x.parent.left = y;   // x가 부모의 왼쪽 자식이라면, y가 왼쪽 자식이 됨

        y.right = x;   // x를 y의 오른쪽 자식으로 설정
        x.parent = y;  // x의 부모를 y로 설정
    }

    // 새로운 값을 트리에 삽입하는 함수
    public void Insert(int key)
    {
        Node node = new Node(key); // 삽입할 새 노드를 생성
        node.left = TNULL;         // 새 노드의 왼쪽 자식은 NIL
        node.right = TNULL;        // 새 노드의 오른쪽 자식은 NIL

        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;  // 삼촌 노드를 추적하기 위한 변수

        // 부모 노드가 Red(빨간색)일 때만 작업이 필요합니다.
        while (k.parent != null && k.parent.color == NodeColor.Red)
        {
            if (k.parent == k.parent.parent.right)  // 부모가 할아버지의 오른쪽 자식일 때
            {
                u = k.parent.parent.left; // 삼촌 노드를 왼쪽 자식으로 설정

                if (u.color == NodeColor.Red) // Case 1: 삼촌이 빨간색
                {
                    // 부모와 삼촌을 Black으로 바꾸고 할아버지를 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.left) // Case 2: k가 부모의 왼쪽 자식
                    {
                        k = k.parent;
                        RightRotate(k); // 부모를 기준으로 우회전
                    }
                    // Case 3: 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) // Case 1
                {
                    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) // Case 2
                    {
                        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; // 루트는 항상 Black으로 설정
    }
}

 

---

트리는 이미 알던 거지만 C#으로 보니까 새로워보였다