트리 (Tree)
노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조
트리 안에 다른 하위 트리가 계속 존재할 수 있는 재귀적 자료구조
특징
- 하나의 루트 노드와 0개 이상의 하위 트리
- 순환(Loop)가 없는, 연결된 무방향 그래프
- 노드 간 부모-자식 관계를 갖는 계층형 자료구조, 모든 자식 노드는 하나의 부모 노드만 가짐
- 노드가 n개인 트리는 항상 (n-1)개의 간선을 가짐
구성요소
- 정점 (Node, Vertex) : 객체, 위치
- 간선 (Edge) : 정점 간의 관계, 연결선 (Link, Branch)
- 루트 노드 (Root Node) : 부모가 없는 최상위 노드
- 부모 노드 (Parent Node) : 자식을 가진 노드
- 자식 노드 (Child Node) : 부모 노드의 하위 노드
- 형제 노드 (Sibling Node) : 같은 부모를 가지는 노드
[ 활용 예시 ]
- 계층적 데이터 저장 ( 파일, 폴더 구조 등)
- 효율적인 검색 속도 보장
- 힙(Heap = 우선순위 큐)
- 데이터베이스 인덱싱 ( B-Tree, B+Tree, AVL-Tree, ... )
- Trie (사전을 저장하는 데 사용되는 특별한 종류의 트리 )
용어
- 서브 트리 (Sub Tree ) : Tree 구조 내에 있는 모든 부분적인 Tree 들
- 외부(단말, 리프) 노드 (Outer, external / terminal / leaf) : 자식이 없는 노드
- 내부 노드(비단말, 가지) (Inner, internal / non-termial / branch) : 자식 노드가 하나 이상인 노드
- 깊이 (Depth) : 루트에서 어떤 노드까지의 간선 수
- 높이 (Height) : 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수- Level : 루트에서 어떤 노드까지의 간선 수
- Degee : 노드의 자식 수
- Path : 한 노드에서 다른 노드로 가는 중에 위치한 노드들의 순서
- Path length : 해당 경로에 위치한 총 노드의 수
- Size : 자신을 포함한 자손의 노드 수
- Width : 레벨에 있는 노드 수
- Breadth : 리프 노드의 수
- Distance : 두 노드 사이의 최단 경로에 있는 간선의 수
- Order : 부모 노드가 가질 수 있는 최대 자식의 수
트리의 종류
- 편향 트리 (Skew Tree)
모든 노드들이 자식을 하나만 가진 트리
left skew tree, right skew tree
- 이진 트리 (Binary Tree)
각 노드의 차수(자식 노드)가 2 이하인 트리
- 이진 탐색 트리 (Binary Search Tree, BST)
순서화된 이진트리
- 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가지며, 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야 함
복잡도
- O(log N)
> 문자열 탐색 시 문자열의 길이(M)만큼 시간이 걸리므로, O(M log N) 이므로 트라이(Trie)구조를 활용
- m원 탐색 트리 (m-way Search Tree)
최대 m개의 서브 트리를 갖는 탐색 트리
- 균형 트리 (Balanced Tree, B-Tree)
height-balanced m-way tree
m원 탐색 트리에서 높이 균형을 유지하는 트리
