트리는 자주 사용되는 추상 데이터 타입이다.
계층 트리 구조이며,
하나의 루트노드를 가지고
루트노드는 0개 이상의 자식 노드를 가지고 있다.
자식 노드는 부모 노드가 될 수 있고 부모노드는 0개 이상의 자식노드를 가질 수 있다.
용어
root node : 최상단 노드
parent node: 자식을 가지고 있는 노드
child node: 부모를 가지고 있는 노드
leaf node: 최하단 노드
internal node: 내부노드( leaf node가 아닌 노드)
edge: 간선
sibling: 같은 부모 노드를 가지는 노드
height / level: 최대 높이, 특정 높이
특장점
계층 구조를 가지고 있는 데이터를 저장할 때 사용될 수 있다
트리는 노드를 쉽게 더하고 지울 수 있으므로 동적이다
일반적인 탐색 알고리즘을 사용하여 탐색, 정렬이 쉽다
사이클이 존재할 수 없다
그래프의 한 종류로, 방향성이 있는 비순환 그래프이다
루트에서 어떤 노드로 가는 경로는 유일하다
노드의 개수가 N이면, 항상 N-1의 간선을 가진다
트리의 종류
Binary Tree, Binary Search Tree, Balanced Tree, Heap
Binary Tree
자식 노드의 수가 0-2개만 허용
중위 순회
왼쪽 가지 -> 현재 노드 -> 오른쪽가지
전위 순회
현재 노드 -> 왼쪽 가지 -> 오른쪽 가지
후위 순회
왼쪽 가지 -> 오른쪽 가지 -> 현재 노드
종류
- Full Binary Tree(전 이진트리)
- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
- Complete Binary Tree(완전 이진트리)
- 트리의 모든 높이에서 노드가 꽉 차 있는 이진트리
- 마지막 레벨은 예외적으로 꽉차 있지 안항도 되지만 왼쪽에서 오른쪽으로 채워져 있어야함
- == 가장 오른쪽의 Leaf node가 제거된 Perfect Binary Tree
- Perfect Binary Tree(포화이진트리)
- 모든 내부노드가 2개의 자식노드를 갖고 있는 트리
- 동일한 깊이를 가진다
- 노드의 개수가 2^(h-1)개 (h: 트리의 높이)
Binary Search Tree
모든 노드가 왼쪽 노드 <= 현재 노드 < 오른쪽 노드를 만족하는 트리
Heap
내부 노드가 2개의 자식 노드를 가지고 있고
단말 노드는 오른쪽 부분을 뺀 나버지 부분이 가득 채워져 있는 트리 구조이고,
