Tree (트리)
트리(Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다.
기본 용어
•
노드 (node) : 트리를 구성하는 기본 요소
•
간선 (edge) : 노드와 노드 간의 연결선
•
루트 노드, 부모 노드, 자식 노드
•
리프 노드 : 자식 노드가 없는 노드
•
내부 노드 : 자식 노드를 하나 이상 가진 노드
•
깊이 (depth) : 루트에서 어떤 노드까지의 간선 수
•
높이 (height) : 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수
•
Degree : 노드의 자식 수
•
Breadth : 리프 노드의 수
•
Order : 부모 노드가 가질 수 ㅣㅇㅆ는 최대 자식 수
특징
•
하나의 루트 노드만 가지고, 0개 이상의 하위 트리로 구성
•
데이터를 순차적으로 저장하지 않으므로 비선형 자료구조
•
트리 내에 또 다른 트리(subtree)가 있는 재귀적 자료구조
•
loop를 갖지 않고, 연결된 무방향 그래프 구조
•
노드 간의 부모 자식 관계를 가지는 계층형 자료구조이고, 모든 자식 노드는 하나의 부모 노드만 갖는다.
•
노드가 n개인 트리는 항상 n-1개의 간선을 가진다.
트리 종류
편향 트리 (Skew Tree)
•
모든 노드들이 자식을 하나만 가진 트리
→ 왼쪽 방향으로만 가질 때 left skew tree, 오른쪽 방향으로만 가질 때 right skew tree
이진트리 (Binary Tree)
•
각 노드의 자식 노드가 2개 이하인 트리
이진탐색트리 (Binary Search Tree)
•
순서화된 이진 트리
•
노드의 왼쪽 자식은 부모 노드보다 작은 값
•
오른쪽 자식은 부모 노드보다 큰 값을 가진다.
m-원 탐색 트리 (m-way Search Tree)
•
최대 m개의 서브 트리를 갖는 탐색 트리
•
이진 탐색 트리의 확장된 형태로 높이(height)를 줄이기 위해 사용
균형 트리 (Balanced Tree, B-Tree)
•
m원 탐색 트리에서 높이 균형을 유지하는 트리
트리 순회 방식
Preorder (전위 순회)
Root → Left → right
Inorder (중위 순회)
Left → Root → Right
Postorder (후위 순회)
Left → Right → Root
어디에 쓰이는가?
•
계층적 데이터 저장
•
효율적인 검색 속도
•
힙 (Heap)
•
데이터베이스의 인덱싱 (B-Tree, B+ Tree)
•
Trie(트라이) 자료구조