[자료구조] 5. 트리(Tree)

---

트리(Tree)

트리(Tree)

---

트리(Tree)

특징, 장단점

특징
   1. 정렬, 검색이 쉽다. db관리에 많이 사용
   2. 루트 노드, 부모/자식 노드
   3. 깊이와 높이

장점
   1. 계층적 구조 : 파일 시스템
   2. 효율적인 검색 및 정렬 : 이진 탐색 트리
   3. 동적인 구조 : 노드 추가/ 제거가 쉬움
   4. 효율적인 데이터 관리 : 데이터 베이스 시스템에 적합

단점
   1. 구현이 복잡합
   2. 비효율적인 메모리 사용 : 각 노드는 참조포인터를 가지고 있어서 추가적 메모리 소모
   3. 불균형 구조 가능성 - 트리가 한쪽으로 치우쳐지면 성능 저하 -> 해결(AVL, 레드-블랙트리)

게임 개발 활용

이진 탐색 트리(BST)

   1. 왼쪽노드는 작은 값, 오른쪽 노드는 큰 값, 최대 두개의 자식 노드
   2. 데이터 정렬된 상태로 저장, 빠른 검색, 삽입, 삭제가 필요할 때
   3. 현업에서 별로 잘 안쓴다. 불균형하게 될 가능성이 높다. AVL, 레드블랙트리 많이 사용

AVL

   1. AVL트리가 더 엄격해서 삽입, 삭제 시 더 많은 회전을 하고 느린 경향이 있다.
   2. 데이터 균형을 유지하며 효율적 탐색이 필요할 때 많이 사용된다.
   3. 플레이어 랭킹 정보 검색 기능에 사용

레드 블랙트리

   1. 삽입 삭제가 빈번할 때 유리한 성능을 보인다.
   2. 데이터 균형을 유지하며 효율적 탐색이 필요할 때 많이 사용된다.
   3. 대규모 멀티 플레이어 게임 플레이어 상태 정보가 빠른 업데이트가 필요한 경우

힙

   1. 최대값, 최소값이 루트에 위치
   2. 완전 이진 트리
   3. 데이터 중 최대, 최소값에 빠르게 접근해야하는 경우 사용

기타 트리 구조

서버 개발자
   1. B–, B++ 트리
   2. 대량의 데이터를 관리하는데 적합한 구조

클라이언트 개발자    1. 옥트리, 쿼드트리
   2. 2D,3D 공간을 분할하고, 렌더링, 물리 시뮬레이션 등의 최적화에 사용됨.

---

TOP

---