자료구조 — 트리(Tree)와 이진 탐색 트리(BST)

개요 — 왜 트리를 알아야 하는가

배열이나 연결 리스트 같은 선형(Linear) 자료구조는 데이터를 한 줄로 나열합니다. 그러나 현실의 많은 데이터는 계층(Hierarchy) 관계를 갖습니다. 파일 시스템의 폴더 구조, 조직도, XML/JSON 문서의 중첩 구조, 그리고 게임 엔진의 씬 그래프(Scene Graph)가 대표적입니다.

**트리(Tree)**는 이러한 계층 관계를 표현하는 비선형 자료구조입니다. 그리고 트리의 특수한 형태인 **이진 탐색 트리(Binary Search Tree, BST)**는 정렬된 데이터에 대해 평균 O(log n)의 탐색·삽입·삭제를 제공합니다.

Unreal Engine 내부에서도 BVH(Bounding Volume Hierarchy), Octree, Behavior Tree 등 핵심 시스템이 모두 트리 구조 위에 구현되어 있습니다. UE5 C++ 개발자라면 트리 자료구조를 깊이 이해하는 것이 엔진 구조를 꿰뚫는 지름길입니다.

---

1. 트리의 기본 개념

1.1 트리의 정의와 특성

트리는 **노드(Node)**와 **간선(Edge)**으로 구성된 계층적 자료구조입니다. 다음 특성을 가집니다.

• 하나의 루트(Root) 노드에서 시작합니다.
• 각 노드는 0개 이상의 자식(Child) 노드를 가집니다.
• 부모-자식 관계는 단방향이며, 사이클(Cycle)이 없습니다.
• 루트를 제외한 모든 노드는 정확히 하나의 부모(Parent) 노드를 가집니다.

                    [A]          ← 루트(Root)
                  /     \
               [B]       [C]    ← A의 자식, B와 C는 형제(Sibling)
              / | \       |
           [D] [E] [F]   [G]    ← 리프(Leaf): D, E, F, G는 자식 없음

1.2 핵심 용어 정리

용어	정의
루트(Root)	트리의 최상단 노드. 부모가 없음
노드(Node)	데이터를 담는 기본 단위
리프(Leaf)	자식이 없는 노드 (말단 노드)
내부 노드(Internal Node)	자식이 하나 이상 있는 노드
부모(Parent)	특정 노드의 바로 위 노드
자식(Child)	특정 노드의 바로 아래 노드
형제(Sibling)	같은 부모를 공유하는 노드들
서브트리(Subtree)	특정 노드와 그 모든 자손으로 구성된 부분 트리
깊이(Depth)	루트에서 해당 노드까지의 간선 수 (루트의 깊이 = 0)
높이(Height)	해당 노드에서 가장 깊은 리프까지의 간선 수 (리프의 높이 = 0)
레벨(Level)	같은 깊이에 있는 노드들의 집합
차수(Degree)	한 노드가 가진 자식의 수

트리 높이와 깊이 예시:

              [A]   ← 깊이 0, 높이 3
             /   \
          [B]     [C]   ← 깊이 1, 높이 2 / 1
         /   \       \
       [D]   [E]     [F]   ← 깊이 2, 높이 1 / 1 / 0
       /
     [G]   ← 깊이 3, 높이 0 (리프)

전체 트리의 높이 = 루트의 높이 = 3

1.3 트리의 종류

일반 트리:          이진 트리:         완전 이진 트리:
    [A]               [A]                  [A]
   / | \             /   \               /     \
 [B][C][D]         [B]   [C]           [B]     [C]
                  /   \     \         /   \   /   \
                [D]   [E]   [F]     [D]  [E][F]  [G]

이진 트리: 각 노드의 자식이 최대 2개
완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 꽉 차고,
              마지막 레벨은 왼쪽부터 채워짐
포화 이진 트리: 모든 레벨이 완전히 꽉 찬 이진 트리

---

2. 이진 트리 vs 이진 탐색 트리(BST)

2.1 이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 2개의 자식을 갖는 트리입니다. 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)으로 구분하지만, 데이터의 순서에 관한 규칙이 없습니다.

// 이진 트리 노드 구조 (C++)
struct FBinaryTreeNode
{
    int32              Value;
    FBinaryTreeNode*   Left;   // 왼쪽 자식
    FBinaryTreeNode*   Right;  // 오른쪽 자식

    explicit FBinaryTreeNode(int32 InValue)
        : Value(InValue), Left(nullptr), Right(nullptr)
    {}
};

아래 트리는 이진 트리이지만 BST가 아닙니다. 노드 배치에 순서 규칙이 없기 때문입니다.

      [5]
     /   \
  [9]    [2]     ← 오른쪽 자식(2)이 루트(5)보다 작음 → BST 위반
  /
[1]

2.2 이진 탐색 트리(BST)

BST는 이진 트리에 **정렬 속성(BST Property)**을 추가한 것입니다.

BST 속성: 임의의 노드 N에 대해,

• N의 왼쪽 서브트리의 모든 노드 값은 N의 값보다 작습니다.
• N의 오른쪽 서브트리의 모든 노드 값은 N의 값보다 큽니다.

올바른 BST:                잘못된 BST (BST 속성 위반):

      [8]                        [8]
     /   \                      /   \
   [3]   [10]                 [3]   [10]
  /   \     \                /   \     \
[1]   [6]  [14]            [1]   [9]  [14]
     /   \                           ← [9]가 [8]의 오른쪽에 있어야 하는데
   [4]   [7]                           [3]의 오른쪽에 있으므로 위반

중위 순회 결과: 1 3 4 6 7 8 10 14   중위 순회: 1 3 8 9 10 14 → 정렬 불일치

BST의 핵심 장점은 정렬 속성 덕분에 이진 탐색(Binary Search)과 동일한 원리로 O(log n) 탐색이 가능하다는 것입니다. 매 단계마다 탐색 범위가 절반으로 줄어듭니다.

2.3 이진 트리 vs BST 핵심 비교

특성	이진 트리	BST
자식 수 제한	최대 2개	최대 2개
데이터 정렬 규칙	없음	왼쪽 < 루트 < 오른쪽
탐색 효율	O(n) (전체 순회 필요)	평균 O(log n)
중위 순회 결과	임의 순서	오름차순 정렬된 순서
주요 활용	표현식 트리, 파스 트리	탐색, 정렬, 범위 쿼리

---

3. BST 삽입·탐색·삭제 연산

3.1 BST 노드 구조 및 클래스 설계

#include <cstdint>

struct FBSTNode
{
    int32      Value;
    FBSTNode*  Left;
    FBSTNode*  Right;

    explicit FBSTNode(int32 InValue)
        : Value(InValue), Left(nullptr), Right(nullptr)
    {}
};

class FBinarySearchTree
{
public:
    FBinarySearchTree() : Root(nullptr) {}
    ~FBinarySearchTree() { DestroyTree(Root); }

    void  Insert(int32 Value);
    bool  Search(int32 Value) const;
    void  Remove(int32 Value);

private:
    FBSTNode* Root;

    FBSTNode* InsertRecursive(FBSTNode* Node, int32 Value);
    bool      SearchRecursive(const FBSTNode* Node, int32 Value) const;
    FBSTNode* RemoveRecursive(FBSTNode* Node, int32 Value);
    FBSTNode* FindMin(FBSTNode* Node) const;
    void      DestroyTree(FBSTNode* Node);
};

3.2 탐색(Search) — 평균 O(log n), 최악 O(n)

BST 속성을 활용하여 매 단계마다 탐색 범위를 절반으로 줄입니다.

탐색 예시: 값 6을 찾아라 (BST 높이 = 3)

      [8]    → 6 < 8, 왼쪽으로 이동
     /   \
   [3]  [10]  → 6 > 3, 오른쪽으로 이동
  /   \
[1]   [6]    → 6 == 6, 탐색 성공! (3단계만에 완료)

bool FBinarySearchTree::SearchRecursive(const FBSTNode* Node, int32 Value) const
{
    if (Node == nullptr)
    {
        return false; // 탐색 실패: 값이 트리에 없음
    }

    if (Value == Node->Value)
    {
        return true;  // 탐색 성공
    }
    else if (Value < Node->Value)
    {
        return SearchRecursive(Node->Left, Value);  // 왼쪽 서브트리 탐색
    }
    else
    {
        return SearchRecursive(Node->Right, Value); // 오른쪽 서브트리 탐색
    }
}

bool FBinarySearchTree::Search(int32 Value) const
{
    return SearchRecursive(Root, Value);
}

시간복잡도

경우	복잡도	설명
평균 (균형 잡힌 트리)	O(log n)	매 단계 탐색 범위 절반 감소
최악 (편향 트리)	O(n)	한쪽으로만 치우쳐 선형 탐색과 동일

균형 BST (높이 ≈ log n):       편향 BST (높이 = n-1):
      [5]                         [1]
     /   \                           \
   [3]   [7]       →                 [2]
  / \   / \                             \
[2][4][6][8]   O(log n)                 [3]
                                           \
                                           [4]  →  O(n)

편향 트리는 정렬된 순서로 데이터를 삽입할 때 발생합니다. 이를 해결하는 것이 AVL Tree, Red-Black Tree 등 균형 이진 트리입니다 (Section 5 참고).

3.3 삽입(Insert) — 평균 O(log n), 최악 O(n)

탐색과 동일한 방식으로 삽입 위치를 찾은 뒤, 해당 위치에 새 노드를 생성합니다.

삽입 예시: 값 5를 삽입 (BST: 8, 3, 10, 1, 6)

      [8]    → 5 < 8, 왼쪽
     /   \
   [3]  [10]  → 5 > 3, 오른쪽
  /   \
[1]   [6]    → 5 < 6, 왼쪽 → nullptr 발견, 여기에 삽입
     /
   [5]   ← 삽입 완료

FBSTNode* FBinarySearchTree::InsertRecursive(FBSTNode* Node, int32 Value)
{
    if (Node == nullptr)
    {
        // 삽입 위치 발견: 새 노드 생성
        return new FBSTNode(Value);
    }

    if (Value < Node->Value)
    {
        Node->Left = InsertRecursive(Node->Left, Value);
    }
    else if (Value > Node->Value)
    {
        Node->Right = InsertRecursive(Node->Right, Value);
    }
    // Value == Node->Value인 경우: 중복 값은 무시 (또는 카운터 증가 등 정책 적용)

    return Node;
}

void FBinarySearchTree::Insert(int32 Value)
{
    Root = InsertRecursive(Root, Value);
}

3.4 삭제(Remove) — 평균 O(log n), 최악 O(n)

삭제는 세 가지 케이스로 나뉩니다.

케이스 1 — 리프 노드 삭제 (자식 없음):
삭제: [1]

      [8]                [8]
     /   \              /   \
   [3]  [10]    →     [3]  [10]
  /   \               \
[1]   [6]             [6]
→ 그냥 제거

케이스 2 — 자식이 하나인 노드 삭제:
삭제: [10] (오른쪽 자식 [14]만 있음)

   [8]                [8]
  /   \              /   \
[3]  [10]    →     [3]  [14]
        \
       [14]
→ 자식 노드가 삭제된 노드 자리를 대체

케이스 3 — 자식이 둘인 노드 삭제:
삭제: [3] (왼쪽 [1], 오른쪽 [6] 모두 있음)

      [8]                [8]
     /   \              /   \
   [3]  [10]    →     [4]  [10]
  /   \              /   \
[1]   [6]          [1]   [6]
     /
   [4]
→ 오른쪽 서브트리의 최솟값(In-order Successor = [4])으로 대체 후,
  해당 최솟값 노드를 원래 위치에서 삭제

FBSTNode* FBinarySearchTree::FindMin(FBSTNode* Node) const
{
    // 왼쪽 끝 노드가 최솟값
    while (Node->Left != nullptr)
    {
        Node = Node->Left;
    }
    return Node;
}

FBSTNode* FBinarySearchTree::RemoveRecursive(FBSTNode* Node, int32 Value)
{
    if (Node == nullptr)
    {
        return nullptr; // 삭제 대상 없음
    }

    if (Value < Node->Value)
    {
        Node->Left = RemoveRecursive(Node->Left, Value);
    }
    else if (Value > Node->Value)
    {
        Node->Right = RemoveRecursive(Node->Right, Value);
    }
    else
    {
        // 삭제 대상 노드 발견

        // 케이스 1: 리프 노드 또는 케이스 2: 자식 하나
        if (Node->Left == nullptr)
        {
            FBSTNode* RightChild = Node->Right;
            delete Node;
            return RightChild; // 오른쪽 자식(또는 nullptr)으로 대체
        }
        else if (Node->Right == nullptr)
        {
            FBSTNode* LeftChild = Node->Left;
            delete Node;
            return LeftChild; // 왼쪽 자식으로 대체
        }

        // 케이스 3: 자식 둘 — In-order Successor로 대체
        FBSTNode* Successor = FindMin(Node->Right);
        Node->Value = Successor->Value;                              // 값 복사
        Node->Right = RemoveRecursive(Node->Right, Successor->Value); // Successor 삭제
    }

    return Node;
}

void FBinarySearchTree::Remove(int32 Value)
{
    Root = RemoveRecursive(Root, Value);
}

void FBinarySearchTree::DestroyTree(FBSTNode* Node)
{
    if (Node == nullptr) return;
    DestroyTree(Node->Left);
    DestroyTree(Node->Right);
    delete Node;
}

3.5 BST 연산 시간복잡도 요약

연산	평균	최악	비고
탐색(Search)	O(log n)	O(n)	편향 트리 시 최악
삽입(Insert)	O(log n)	O(n)	편향 트리 시 최악
삭제(Remove)	O(log n)	O(n)	편향 트리 시 최악
최솟값/최댓값	O(log n)	O(n)	가장 왼쪽/오른쪽 노드
중위 순회 (전체)	O(n)	O(n)	정렬된 순서 출력

---

4. 트리 순회(Tree Traversal)

트리 순회는 트리의 모든 노드를 특정 순서로 방문하는 방법입니다. 이진 트리에서는 4가지 주요 순회 방식이 있습니다.

예제 트리:
        [1]
       /   \
     [2]   [3]
    /   \
  [4]   [5]

4.1 전위 순회(Pre-order) — 루트 → 왼쪽 → 오른쪽

현재 노드를 먼저 방문한 뒤, 왼쪽 서브트리, 오른쪽 서브트리 순으로 순회합니다.

방문 순서: 1 → 2 → 4 → 5 → 3

활용: 트리 복사, 직렬화(Serialization), 표현식 트리의 전위 표기법

void PreorderTraversal(const FBSTNode* Node)
{
    if (Node == nullptr) return;

    // 1. 현재 노드 방문 (Root)
    UE_LOG(LogTemp, Log, TEXT("%d"), Node->Value);

    // 2. 왼쪽 서브트리 순회
    PreorderTraversal(Node->Left);

    // 3. 오른쪽 서브트리 순회
    PreorderTraversal(Node->Right);
}

4.2 중위 순회(In-order) — 왼쪽 → 루트 → 오른쪽

BST에서 중위 순회를 하면 오름차순 정렬된 결과를 얻습니다.

방문 순서: 4 → 2 → 5 → 1 → 3

활용: BST에서 정렬된 출력, 오름차순 탐색

void InorderTraversal(const FBSTNode* Node)
{
    if (Node == nullptr) return;

    // 1. 왼쪽 서브트리 순회
    InorderTraversal(Node->Left);

    // 2. 현재 노드 방문 (Root)
    UE_LOG(LogTemp, Log, TEXT("%d"), Node->Value);

    // 3. 오른쪽 서브트리 순회
    InorderTraversal(Node->Right);
}

4.3 후위 순회(Post-order) — 왼쪽 → 오른쪽 → 루트

자식 노드를 모두 처리한 뒤 현재 노드를 방문합니다.

방문 순서: 4 → 5 → 2 → 3 → 1

활용: 트리 메모리 해제, 파일 시스템 삭제(자식 폴더 먼저 삭제), 표현식 트리의 후위 표기법

void PostorderTraversal(const FBSTNode* Node)
{
    if (Node == nullptr) return;

    // 1. 왼쪽 서브트리 순회
    PostorderTraversal(Node->Left);

    // 2. 오른쪽 서브트리 순회
    PostorderTraversal(Node->Right);

    // 3. 현재 노드 방문 (Root) — 자식들을 모두 처리한 후
    UE_LOG(LogTemp, Log, TEXT("%d"), Node->Value);
}

4.4 레벨 순회(Level-order / BFS) — 위에서 아래, 왼쪽에서 오른쪽

같은 레벨(깊이)의 노드를 왼쪽부터 오른쪽으로 방문한 뒤 다음 레벨로 이동합니다. **큐(Queue)**를 사용하여 구현합니다.

방문 순서: 1 → 2 → 3 → 4 → 5

활용: 최단 경로 탐색(BFS), 트리 직렬화, 완전 이진 트리 검증

#include <queue>

void LevelOrderTraversal(const FBSTNode* Root)
{
    if (Root == nullptr) return;

    std::queue<const FBSTNode*> NodeQueue;
    NodeQueue.push(Root);

    while (!NodeQueue.empty())
    {
        const FBSTNode* Current = NodeQueue.front();
        NodeQueue.pop();

        // 현재 노드 방문
        UE_LOG(LogTemp, Log, TEXT("%d"), Current->Value);

        // 자식 노드를 큐에 추가 (왼쪽 → 오른쪽 순)
        if (Current->Left  != nullptr) NodeQueue.push(Current->Left);
        if (Current->Right != nullptr) NodeQueue.push(Current->Right);
    }
}

4.5 순회 방식 비교 요약

순회 방식	방문 순서	예제 결과	주요 활용
전위(Pre-order)	루트 → 좌 → 우	1 2 4 5 3	트리 복사, 직렬화
중위(In-order)	좌 → 루트 → 우	4 2 5 1 3	BST 정렬 출력
후위(Post-order)	좌 → 우 → 루트	4 5 2 3 1	트리 해제, 파일 삭제
레벨(Level-order)	레벨별 좌→우	1 2 3 4 5	BFS, 최단 경로

---

5. 균형 이진 트리 — AVL Tree와 Red-Black Tree

일반 BST는 삽입 순서에 따라 편향 트리가 될 수 있어 O(n) 최악 케이스가 발생합니다. **균형 이진 트리(Balanced BST)**는 트리의 높이를 항상 O(log n)으로 유지하여 이 문제를 해결합니다.

5.1 AVL Tree

AVL Tree(Adelson-Velsky and Landis Tree)는 **균형 인수(Balance Factor)**를 사용하여 트리 균형을 유지합니다.

균형 인수(Balance Factor) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이

모든 노드의 균형 인수는 반드시 -1, 0, +1 중 하나여야 합니다.

균형이 깨지면 회전(Rotation) 연산으로 복구합니다.

Left-Left 케이스 (우회전):         Left-Right 케이스 (좌-우 회전):

      [5] BF=+2                         [5] BF=+2
     /                                 /
   [3] BF=+1        →               [3] BF=-1      →  [4]
  /                               우회전 전 좌회전    /   \
[1]                                     \           [3]   [5]
                                        [4]
↓ 우회전(Right Rotation)
   [3]
  /   \
[1]   [5]

Right-Right 케이스 (좌회전):       Right-Left 케이스 (우-좌 회전):

[1] BF=-2                         [1] BF=-2
    \                                 \
    [3] BF=-1      →                  [5] BF=+1     →  [3]
        \                좌회전 전 우회전              /   \
        [5]                          /              [1]   [5]
↓ 좌회전(Left Rotation)            [3]
  [3]
 /   \
[1]   [5]

AVL Tree 특징

• 모든 연산의 시간복잡도: O(log n) 보장
• 삽입·삭제마다 균형 인수를 갱신하고 최대 O(log n) 번의 회전 수행
• 엄격한 균형 유지로 탐색 성능이 Red-Black Tree보다 우수
• 삽입·삭제 시 회전 횟수가 많아 쓰기 작업이 빈번한 경우 Red-Black Tree보다 느릴 수 있음

5.2 Red-Black Tree

Red-Black Tree는 각 노드에 색상(빨강/검정) 속성을 추가하여 5가지 규칙으로 균형을 유지합니다.

Red-Black Tree 5가지 규칙

1. 모든 노드는 빨강 또는 검정이다.
2. 루트 노드는 항상 검정이다.
3. 모든 리프(NIL 노드)는 검정이다.
4. 빨강 노드의 자식은 반드시 검정이다 (빨강이 연속으로 올 수 없다).
5. 루트에서 임의의 리프까지 경로에 있는 검정 노드의 수는 모두 동일하다.

Red-Black Tree 예시:
(B=검정, R=빨강)

          [8:B]
         /     \
      [3:R]   [10:B]
      /   \       \
  [1:B] [6:B]  [14:R]
        /   \
     [4:R] [7:R]

Red-Black Tree 특징

• 모든 연산의 시간복잡도: O(log n) 보장
• AVL Tree보다 덜 엄격한 균형 — 탐색은 다소 느리지만 삽입·삭제 시 회전 횟수 적음
• C++ STL의 std::map, std::set, std::multimap, std::multiset이 내부적으로 Red-Black Tree를 사용
• Linux 커널의 프로세스 스케줄러(CFS)에서도 활용

5.3 AVL Tree vs Red-Black Tree 비교

특성	AVL Tree	Red-Black Tree
균형 기준	균형 인수 (-1, 0, +1)	색상 규칙 5가지
균형 엄격도	더 엄격	덜 엄격
탐색 성능	상대적으로 빠름	상대적으로 느림
삽입·삭제 성능	상대적으로 느림 (더 많은 회전)	상대적으로 빠름 (적은 회전)
시간복잡도	O(log n) 보장	O(log n) 보장
주요 사용처	탐색 중심 DB, 파일시스템	std::map/set, Linux 스케줄러

5.4 C++ STL에서의 Red-Black Tree 활용

#include <map>
#include <set>

// std::map — Red-Black Tree 기반 Key-Value 탐색 (O(log n) 보장)
void STLMapExample()
{
    // 내부적으로 Red-Black Tree
    std::map<int32, std::string> ScoreMap;

    // O(log n) 삽입
    ScoreMap[100] = "Diamond";
    ScoreMap[75]  = "Platinum";
    ScoreMap[50]  = "Gold";
    ScoreMap[25]  = "Silver";

    // O(log n) 탐색
    auto It = ScoreMap.find(75);
    if (It != ScoreMap.end())
    {
        // "Platinum"
        UE_LOG(LogTemp, Log, TEXT("Rank: %s"), It->second.c_str());
    }

    // 중위 순회 → 오름차순 자동 출력 (25, 50, 75, 100)
    for (const auto& [Score, Rank] : ScoreMap)
    {
        UE_LOG(LogTemp, Log, TEXT("%d: %s"), Score, Rank.c_str());
    }
}

// std::set — Red-Black Tree 기반 정렬된 유일값 집합
void STLSetExample()
{
    std::set<int32> UniqueIDs;

    UniqueIDs.insert(42);
    UniqueIDs.insert(17);
    UniqueIDs.insert(88);
    UniqueIDs.insert(42); // 중복 무시

    // 정렬된 순서: 17, 42, 88
    for (int32 ID : UniqueIDs)
    {
        UE_LOG(LogTemp, Log, TEXT("ID: %d"), ID);
    }
}

---

6. Unreal Engine에서의 트리 활용

트리 자료구조는 Unreal Engine의 핵심 시스템 곳곳에서 사용됩니다. 원리를 이해하면 엔진 내부 동작과 성능 특성을 훨씬 명확하게 파악할 수 있습니다.

6.1 BVH (Bounding Volume Hierarchy) — 충돌 감지

BVH는 물리 시뮬레이션과 레이캐스트(Raycast)에서 사용하는 가속 구조입니다. 씬의 모든 오브젝트를 경계 볼륨(AABB 또는 OBB)으로 감싸고, 이를 계층적 트리 구조로 구성합니다.

BVH 구조 예시 (씬에 오브젝트 A, B, C, D가 있는 경우):

         [전체 씬 AABB]
        /              \
 [그룹1 AABB]      [그룹2 AABB]
  /       \          /       \
[A]       [B]      [C]       [D]

레이캐스트 과정:

1. 레이가 루트 AABB와 교차하는지 검사
2. 교차하면 자식 AABB와 검사 재귀 진행
3. 교차하지 않는 서브트리 전체를 즉시 제외 (가지치기, Pruning)

// UE5에서 BVH 기반 물리 시스템 활용
// Engine/Source/Runtime/Engine/Public/Physics/PhysicsInterfacePhysX.h 참조

// 레이캐스트 (BVH를 내부적으로 사용)
FHitResult HitResult;
FVector Start  = GetActorLocation();
FVector End    = Start + GetActorForwardVector() * 5000.0f;

bool bHit = GetWorld()->LineTraceSingleByChannel(
    HitResult,
    Start,
    End,
    ECC_Visibility
);
// 내부적으로 PhysX/Chaos의 BVH 트리를 순회하여 후보 오브젝트만 정밀 검사
// 전체 오브젝트 순회(O(n))가 아닌 O(log n) 수준으로 성능 개선

if (bHit)
{
    UE_LOG(LogTemp, Log, TEXT("Hit: %s"), *HitResult.GetActor()->GetName());
}

6.2 Octree — 공간 분할

Octree는 3D 공간을 재귀적으로 8개의 자식 셀로 분할하는 트리 구조입니다. Unreal Engine은 Octree를 다양한 용도로 활용합니다.

Octree 공간 분할 (2D 예시로는 Quadtree):

루트: 전체 공간
├── 셀 0 (왼쪽 위 앞)
│   ├── 서브셀 0-0
│   └── 서브셀 0-1 (오브젝트 A, B 포함)
│       ├── ...
├── 셀 1 (오른쪽 위 앞)
├── 셀 2 (왼쪽 아래 앞)
...
└── 셀 7 (오른쪽 아래 뒤)
    └── 서브셀 7-X (오브젝트 C, D 포함)

// UE5의 FPrimitiveSceneInfo는 Octree에 등록되어 렌더링 가시성 쿼리에 사용됨
// Engine/Source/Runtime/Engine/Public/SceneManagement.h 참조

// 예시: Overlap 쿼리 (내부적으로 Octree 활용)
TArray<FOverlapResult> OverlapResults;
FCollisionShape SphereShape = FCollisionShape::MakeSphere(500.0f);

GetWorld()->OverlapMultiByChannel(
    OverlapResults,
    GetActorLocation(),
    FQuat::Identity,
    ECC_Pawn,
    SphereShape
);
// Octree로 해당 구체와 겹치는 셀만 탐색 → 후보 Actor만 정밀 검사
// 씬 전체 순회 없이 근처 Actor만 효율적으로 탐색

for (const FOverlapResult& Result : OverlapResults)
{
    if (ACharacter* Nearby = Cast<ACharacter>(Result.GetActor()))
    {
        UE_LOG(LogTemp, Log, TEXT("Nearby: %s"), *Nearby->GetName());
    }
}

6.3 Scene Graph — 씬 계층 구조

Unreal Engine의 씬은 Actor → Component 계층 구조로 구성됩니다. 특히 USceneComponent는 AttachToComponent를 통해 트리 구조를 형성하며, 부모-자식 Transform이 계층적으로 전파됩니다.

씬 그래프 예시:

ACharacter (Actor)
└── UCapsuleComponent (RootComponent)
    ├── USkeletalMeshComponent (캐릭터 메시)
    │   └── UParticleSystemComponent (이펙트, 소켓 부착)
    ├── UCameraComponent (카메라)
    └── USpringArmComponent (카메라 붐)
        └── UCameraComponent (3인칭 카메라)

// AttachToComponent: 씬 그래프 트리에 노드 추가
// Engine/Source/Runtime/Engine/Classes/Components/SceneComponent.h 참조

UCLASS()
class AMyWeapon : public AActor
{
    GENERATED_BODY()

    UPROPERTY(VisibleAnywhere)
    TObjectPtr<UStaticMeshComponent> WeaponMesh;

public:
    void AttachToCharacterSocket(USkeletalMeshComponent* CharacterMesh, FName SocketName)
    {
        // 씬 그래프 트리에 자식으로 추가
        WeaponMesh->AttachToComponent(
            CharacterMesh,
            FAttachmentTransformRules::SnapToTargetIncludingScale,
            SocketName
        );
        // 이후 CharacterMesh의 Transform이 변경되면
        // WeaponMesh에도 자동으로 전파됨 (트리 구조 덕분)
    }
};

// 씬 그래프 순회 — PostorderTraversal과 동일한 원리
void TraverseComponentTree(USceneComponent* Component, int32 Depth = 0)
{
    if (!IsValid(Component)) return;

    FString Indent = FString::ChrN(Depth * 2, ' ');
    UE_LOG(LogTemp, Log, TEXT("%s%s"), *Indent, *Component->GetName());

    // 자식 컴포넌트 순회 (전위 순회 방식)
    for (USceneComponent* Child : Component->GetAttachChildren())
    {
        TraverseComponentTree(Child, Depth + 1);
    }
}

6.4 Behavior Tree — AI 의사결정

Unreal Engine의 Behavior Tree는 AI 캐릭터의 행동을 트리 구조로 정의하는 시스템입니다. 루트에서 자식 노드를 순회하며 조건에 따라 행동을 결정합니다.

Behavior Tree 구조:

Root
└── Selector (자식 중 하나가 성공하면 OK)
    ├── Sequence (모든 자식이 성공해야 OK)
    │   ├── BTTask_FindEnemy       ← 적 탐지
    │   ├── BTTask_MoveToEnemy     ← 적에게 이동
    │   └── BTTask_Attack          ← 공격
    └── Sequence
        ├── BTTask_FindPatrolPoint ← 순찰 포인트 탐색
        └── BTTask_MoveToPoint     ← 순찰

노드 유형:
- Composite: Selector(OR), Sequence(AND), Simple Parallel
- Decorator: 조건 검사 (Is Blackboard Value Set, Cooldown 등)
- Task: 실제 행동 (Move To, Play Animation, Custom Task 등)

// 커스텀 Behavior Tree Task 구현
// Engine/Source/Runtime/AIModule/Classes/BehaviorTree/BTTaskNode.h 참조

#include "BehaviorTree/BTTaskNode.h"
#include "BehaviorTree/BlackboardComponent.h"
#include "AIController.h"

UCLASS()
class UBTTask_FindAndSetTarget : public UBTTaskNode
{
    GENERATED_BODY()

    // Blackboard에서 읽어올 Target 키
    UPROPERTY(EditAnywhere, Category = "Blackboard")
    FBlackboardKeySelector TargetKey;

public:
    UBTTask_FindAndSetTarget()
    {
        NodeName = TEXT("Find And Set Target");
    }

    virtual EBTNodeResult::Type ExecuteTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory) override
    {
        AAIController* AIController = OwnerComp.GetAIOwner();
        if (!IsValid(AIController))
        {
            return EBTNodeResult::Failed;
        }

        APawn* ControlledPawn = AIController->GetPawn();
        if (!IsValid(ControlledPawn))
        {
            return EBTNodeResult::Failed;
        }

        // 반경 내 적 탐색 (내부적으로 Octree/BVH 활용)
        TArray<FOverlapResult> OverlapResults;
        FCollisionShape SearchSphere = FCollisionShape::MakeSphere(2000.0f);

        bool bFound = ControlledPawn->GetWorld()->OverlapMultiByChannel(
            OverlapResults,
            ControlledPawn->GetActorLocation(),
            FQuat::Identity,
            ECC_Pawn,
            SearchSphere
        );

        if (bFound)
        {
            // Blackboard에 Target 설정
            UBlackboardComponent* Blackboard = OwnerComp.GetBlackboardComponent();
            Blackboard->SetValueAsObject(TargetKey.SelectedKeyName, OverlapResults[0].GetActor());
            return EBTNodeResult::Succeeded;
        }

        return EBTNodeResult::Failed;
    }
};

6.5 UE5 트리 시스템 활용 요약

트리 시스템	트리 종류	활용 목적	관련 클래스/파일
BVH	이진 트리 계열	충돌 감지, 레이캐스트 가속	FPhysScene, Chaos Physics
Octree	8진 트리	공간 분할, Overlap 쿼리	FPrimitiveSceneInfo, UWorld
Scene Graph	일반 트리	오브젝트 계층, Transform 전파	USceneComponent
Behavior Tree	일반 트리	AI 의사결정	UBehaviorTreeComponent, UBTTaskNode
Widget Tree	일반 트리	UMG UI 계층	UWidgetTree, UUserWidget
Animation Tree	DAG(방향 비순환 그래프)	애니메이션 블렌딩	UAnimGraph, FAnimNode_Base

---

7. 정리 및 체크리스트

핵심 개념 요약

트리 (Tree)
├── 기본 개념: 루트, 노드, 리프, 깊이(Depth), 높이(Height)
├── 이진 트리: 각 노드 자식 최대 2개, 순서 규칙 없음
└── BST (Binary Search Tree)
    ├── BST 속성: 왼쪽 < 현재 < 오른쪽
    ├── 탐색/삽입/삭제: 평균 O(log n), 최악 O(n)
    └── 균형 BST
        ├── AVL Tree: 균형 인수(-1,0,+1), 엄격한 균형, 탐색 우수
        └── Red-Black Tree: 색상 규칙 5개, 삽입·삭제 우수
                           → std::map, std::set 내부 구조

순회 방식
├── 전위(Pre-order): 루트→좌→우, 트리 복사/직렬화
├── 중위(In-order): 좌→루트→우, BST 정렬 출력
├── 후위(Post-order): 좌→우→루트, 트리 해제
└── 레벨(Level-order): BFS, 최단 경로

UE5 트리 활용
├── BVH: 충돌 감지 O(log n) 가속
├── Octree: 공간 분할, Overlap 쿼리 최적화
├── Scene Graph: 컴포넌트 계층, Transform 전파
└── Behavior Tree: AI 의사결정 구조

개발자 체크리스트

• BST 속성(왼쪽 < 현재 < 오른쪽)을 손으로 트리를 그리며 검증할 수 있는가?
• 삭제 3가지 케이스(리프, 자식 하나, 자식 둘)를 설명하고 코드로 구현할 수 있는가?
• 정렬된 데이터를 BST에 순서대로 삽입하면 왜 편향 트리가 되는지 설명할 수 있는가?
• 중위 순회가 BST에서 정렬된 결과를 내는 이유를 이해하고 있는가?
• AVL Tree와 Red-Black Tree의 트레이드오프를 상황에 맞게 설명할 수 있는가?
• std::map/std::set이 Red-Black Tree 기반임을 알고, O(log n) 특성을 감안하여 사용하는가?
• UE5의 LineTraceSingleByChannel이 내부적으로 BVH를 활용함을 이해하는가?
• USceneComponent::AttachToComponent가 씬 그래프 트리에 자식 노드를 추가하는 것임을 이해하는가?
• Behavior Tree의 Composite 노드(Selector/Sequence)가 트리 순회 방식으로 실행됨을 이해하는가?