트리(Tree) 란?
계층적 구조를 나타내는 자료구조로, 루트(Root) 노드에서 시작하여 자식(Children) 노드로 확장되는 방식으로 구성.
트리는 다양한 컴퓨터 과학 및 알고리즘 문제에서 중요한 역할을 함.
트리의 기본 개념
- 노드(Node) : 트리의 기본 구성 요소로, 데이터와 자식 노드에 대한 참조를 포함
- 루트 노드(Root Node) : 트리의 최상위 노드. 트리는 하나의 루트 노드로 시작
- 부모 노드(Parent Node) : 자식 노드를 갖는 노드
- 자식 노드(Child Node) : 다른 노드의 하위에 있는 노드
- 리프 노드(Leaf Node) : 자식 노드가 없는 최하위 노드
- 간선(Edge) : 노드 간의 연결을 나타냄 (다리역할)
- 서브트리(SUbtree) : 트리의 하위 트리로, 루트 노드와 그 자식들로 구성됨
- 레벨(Level) : 트리에서 노드의 깊이를 나타내는 개념. 루트 노드의 레벨은 0 이며, 루트의 자식 노드는 레벨 1, 그 자식 노드는 레벨2
- 깊이(Depth) : 루트 노드에서 특정 노드에 도달하기까지 거쳐야 하는 간선의 수
- 높이(Heigth) : 트리의 최대 깊이를 의미하며, 루트 노드에서 가장 멀리있는 리프 노드까지의 간선 수
- 차수(Degree) : 특정 노드가 가진 자식 노드의 수. 트리 전체의 차수는 노드들 중 최대 차수를 갖는 노드의 차수로 정의
트리의 종류
-
이진 트리(Binary Tree) : 각 노드가 최대 두개의 자식 노드를 갖는 트리
-완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 트리
-포화 이진 트리 (Full Binary Tree) : 모든 노드가 두 개의 자식 노드를 가지거나 리프 노드인 트리
-균형 이진 트리 (Balanced Binary Tree) : 모든 리프 노드가 같은 높이에 있는 트리
-이진 탐색 트리 (Binary Search Tree, BST) : 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 이진 트리 -
AVL 트리(AVL Tree) : 모든 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 1 이하인 자가 균형 이진 탐색 트리
-
레드-블랙 트리(Red-Black Tree) : 각 노드가 레드 또는 블랙으로 색칠된 이진 탐색 트리로, 트리의 균형을 유지하기 위해 특정 규칙을 따름
-
N-진 트리(N-ary Tree) : 각 노드가 최대 N개의 자식을 갖는 트리
트리의 용도
- 검색(Search) : 이진 탐색 트리(BST) 등을 이용한 빠른 검색
- 정렬(Sorting) : 트리 정렬 알고리즘을 사용한 정렬
- 계층적 데이터 모델링(Hierarchical Data Modeling) : 파일 시스템, 데이터베이스 인덱스 등에서의 계층적 데이터 표현
- 트라이(Trie) : 문자열 검색 및 자동 완성 등에 사용
- 그래프 알고리즘 : 최소 신장 트리(MST) 와 같은 그래프 문제 해결
트리 관련 알고리즘
-
트리 순회(Tree Traversal) : 트리의 노드를 방문하는 방법
-전위 순회(Preorder Traversal) : 루트 -> 왼쪽 -> 오른쪽 순서대로 방문
-중위 순회(Inorder Traversal) : 왼쪽 -> 루트 -> 오른쪽 순서대로 방문. 이진 탐색 트리에서는 중위 순회 결과가 정렬된 순서가 됨
-후위 순회(Postorder Traversal) : 왼쪽 -> 오른쪽 -> 루트 순으로 방문
-레벨 순회(Lever Order Traversal) : 루트에서 시작하여 레벨별로 방문 -
삽입(Insertion) : 트리에서 새로운 노드를 추가하는 알고리즘. 예를들어, 이진 탐색 트리에서는 규칙에 따라 적절한 위치에 삽입
-
삭제(Deletion) : 트리에서 노드를 제거하는 알고리즘. 이진 탐색 트리에서 노드를 삭제할 때는 자식 노드가 없는경우, 자식 노드가 하나인 경우, 자식 노드가 둘인 경우에 따라 다르게 처리
-
검색(Search) : 특정 값을 가진 노드를 찾는 알고리즘. 이진 탐색 트리에서는 루트부터 시작하여 값을 비교하면서 탐색
