원래 다음 정렬인 힙 정렬을 배우려했지만 아직 힙에 대해 자세히모르니 힙과 관련된 비선형 자료구조를
공부해보려합니다.
트리(Tree)는 비선형 자료구조의 일종으로, 계층적인 관계를 표현하기 위해 사용됩니다. 트리는 노드(데이터 요소)와 엣지(노드 간의 연결)로 구성되며, 부모-자식 관계를 통해 서로 연결되어 있습니다.
트리의 기본 개념
노드 (Node):
트리의 기본 구성 요소로, 데이터를 저장하는 단위입니다.
루트 노드 (Root Node):
트리의 최상위 노드로, 부모가 없는 노드입니다. 모든 다른 노드는 루트 노드에서 파생됩니다.
자식 노드 (Child Node):
특정 노드의 하위 노드를 의미합니다. 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.
부모 노드 (Parent Node):
특정 노드를 포함하는 상위 노드입니다. 루트 노드를 제외한 모든 노드는 하나의 부모 노드를 가집니다.
리프 노드 (Leaf Node):
자식 노드가 없는 노드입니다. 트리의 끝에 위치하는 노드로, 데이터의 최종 저장 위치입니다.
깊이 (Depth):
특정 노드까지 도달하는 데 필요한 엣지의 수입니다. 루트 노드의 깊이는 0입니다.
높이 (Height):
트리의 가장 긴 경로(루트에서 리프까지)에서 엣지의 수로 정의됩니다. 리프 노드의 높이는 0입니다.
| A (루트 노드) / \ B C / \ \ D E F / \ G H |
트리의 구성 요소 설명
루트 노드 (Root Node):
- A: 트리의 최상위 노드로, 부모가 없는 노드입니다.
자식 노드 (Child Node):
- B와 C는 A의 자식 노드입니다.
- D와 E는 B의 자식 노드입니다.
- F는 C의 자식 노드입니다.
부모 노드 (Parent Node):
- A는 B와 C의 부모 노드입니다.
- B는 D와 E의 부모 노드입니다.
- C는 F의 부모 노드입니다.
리프 노드 (Leaf Node):
- G, H, E, F는 자식 노드가 없는 리프 노드입니다. 이들은 트리의 끝에 위치하여 데이터의 최종 저장 위치입니다.
깊이 (Depth):
- A의 깊이는 0입니다.
- B의 깊이는 1입니다.
- D의 깊이는 2입니다.
높이 (Height):
- 전체 트리의 높이는 3입니다 (루트 A에서 가장 깊은 리프 G 또는 H까지의 경로).
- 리프 노드 G와 H의 높이는 0입니다.
이걸 한번 공부한 후에 트리의 종류를 알아보면 이해가 수월했습니다.
트리의 종류
이진 트리 (Binary Tree):
- 각 노드가 최대 2개의 자식 노드를 가지는 트리입니다.
- 특징: 노드의 자식이 왼쪽과 오른쪽으로 구분됩니다.
이진 탐색 트리 (Binary Search Tree, BST):
- 이진 트리의 한 종류로, 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가집니다.
- 특징: 효율적인 탐색, 삽입, 삭제가 가능합니다.
AVL 트리:
- 자가 균형 이진 탐색 트리로, 모든 노드의 서브트리 높이 차이가 1 이하로 유지됩니다.
- 특징: 균형을 유지하여 탐색 효율성을 높입니다.
B-트리:
- 다중 자식 노드를 가지는 자가 균형 트리로, 데이터베이스와 파일 시스템에서 자주 사용됩니다.
- 특징: 높은 차원의 노드를 통해 디스크 접근을 줄입니다.
N-ary 트리:
- 각 노드가 최대 N개의 자식 노드를 가지는 트리입니다.
- 특징: 자식 노드의 수가 고정되지 않은 트리 구조입니다.
트리의 활용 사례
파일 시스템:
디렉토리 구조를 나타내는 데 사용됩니다. 루트 디렉토리에서 각 하위 디렉토리와 파일이 노드로 표현됩니다.
데이터베이스:
B-트리와 같은 형태로 인덱스를 구축하여 빠른 데이터 검색을 지원합니다.
이진 탐색:
이진 탐색 트리는 정렬된 데이터를 효율적으로 검색하는 데 사용됩니다.
등이 있지만 게임 개발에서는 어떻게 쓰이는지 알아보겠습니다.
게임에서 트리가 사용되는 몇 가지 주요 사례입니다.
1. AI 행동 트리 (Behavior Tree)
AI 의사결정: AI의 행동을 정의하는 데 사용됩니다. 행동 트리는 조건에 따라 여러 행동을 선택할 수 있도록 구성됩니다.
노드 기반 구조: 각 노드는 특정 행동이나 조건을 나타내며, 트리의 경로를 따라 AI의 행동이 결정됩니다. 이는 복잡한 AI 논리를 간단하게 구성하고 관리할 수 있게 해줍니다.
2. 씬 그래프 (Scene Graph)
장면 구성: 게임의 씬을 구성하는 오브젝트를 관리하는 데 사용됩니다. 씬 그래프는 각 오브젝트 간의 관계를 정의하며, 렌더링, 충돌 감지 등을 효율적으로 처리할 수 있습니다.
계층적 관리: 각 오브젝트의 위치, 회전, 크기 등을 계층적으로 관리하여 쉽게 조작할 수 있습니다.
3.UI 요소의 계층 구조
UI 트리: 게임의 사용자 인터페이스(UI) 구성 요소는 종종 트리 구조로 구성됩니다. 각 UI 요소는 부모 요소를 가질 수 있으며, 이로 인해 복잡한 UI를 쉽게 관리하고 업데이트할 수 있습니다.
상태 관리: UI의 상태와 동작을 트리 구조로 정의하여, 특정 이벤트에 따라 UI의 반응을 쉽게 설정할 수 있습니다.
AI 의사결정은 예로들면
이진탐색트리를 사용해서 비교값이 중요도라고 정해지면
주변을 감지하다가 발견했으면
1. 멀리 있으면 이동 (혹은 다른 공격 노드 탐색)
2. 가능하다면 공격 이라는 방식으로 행동을 결정 시킬 수 있을 것 같습니다.