트리(Tree)
개념
나무 가지처럼 연결된 노드로 이루어진 자료 구조
비선형으로, 가계도와 같은 계층적인 구조를
표현할 때 사용할 수 있다.
관련 용어
-
노드(node): A, B, C, D, E, F, G, H, I , J
트리를 구성하고 있는 기본 요소
노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.
-
간선(edge):
노드를 연결하는 선 (link, branch 라고도 부름) -
루트 노드(root node): A
부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. -
부모 노드 (parent node): H, I 의 부모 노드는 D
자식 노드를 가진 노드 -
자식 노드 (child node): D의 자식 노드는 H, I
부모 노드의 하위 노드 -
형제 노드 (sibling node): H, I는 형제 노드
같은 부모를 가지는 노드 -
단말 노드(terminal node): H, I, J, F, G
= 외부 노드(external node, outer node)
= 말단 노드 = 리프 노드(leaf node)
자식이 없는 노드 -
내부(internal) 노드: A, B, C, D, E
자식을 하나 이상 가진 노드
-
깊이(depth): D의 깊이 = 2
루트에서 어떤 노드에 도달하기 위해 거쳐야 하는
간선의 수 -
높이(height): A 노드의 높이 = 3
어떤 노드에서 리프 노드까지
가장 긴 경로의 간선(Edge) 수
= 깊이의 최댓값 -
레벨(level):
트리의 특정 깊이를 가지는 노드의 집합 -
차수(degree): A의 차수 = 2
하위 트리 개수 / 간선 수 (degree) =
각 노드가 지닌 가지의 수
Leaf node의 degree : 0 -
트리의 차수(degree of tree):
트리의 최대 차수
-
경로(path): A & H 경로 : A-B-D-H
한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서 -
경로 길이(path length): A & H 경로 길이 = 4
해당 경로에 있는 총노드의 수 -
크기(size): 노드 B의 size = 6
자신을 포함한 모든 자손 노드의 개수 -
너비(width): Level 2 width = 4
레벨에 있는 노드 수 -
폭(breadth): Breadth = 5
리프 노드의 수 -
거리(distance): D와 J의 Distance = 3
두 노드 사이의 최단 경로에 있는 간선(Edge)의 수 -
order:
부모 노드가 가질 수 있는 최대 자식의 수
ex. Order 3
= 부모 노드는 최대 3명의 자식을 가질 수 있다.
특징
- 하나의 루트 노드와
0개 이상의 하위 트리로 구성 - 데이터를 순차적으로 저장하지 않기 때문에
비선형 자료구조 - 트리내에 또 다른 트리가 있는 재귀적 자료구조
- 단순 순환(Loop)을 갖지 않고,
연결된 무방향 그래프 구조이다. - 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조
- 모든 자식 노드는 하나의 부모 노드만 갖는다.
- 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다.
- 루트에서 어떤 노드로 가는 경로는 유일하다.
임의의 두 노드 간의 경로도 유일하다.
즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
순회(Tree Traversal)
개념
트리 자료구조에 포함된 노드를
특정한 방법으로 한 번씩 방문하는 방법.
트리의 정보를 시각적으로 확인할 수 있다.
방법
- 전위 순회(pre-order traverse)
루트를 먼저 방문 - 중위 순회(in-order traverse)
왼쪽 자식 방문 후 루트 방문 - 후위 순회(post-order traverse)
오른쪽 자식 방문 후 루트 방문
구현
인접 배열 이용
- 1차원 배열에 자신의 부모 노드만 저장하는 방법
- 트리는 부모 노드를 0개 또는 1개를 가지기 때문
- 부모 노드를 0개: 루트 노드
- 이진 트리의 경우,
2차원 배열에 자식 노드를 저장하는 방법
- 이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문
- ex) A[i][0]: 왼쪽 자식 노드,
A[i][1]: 오른쪽 자식 노드
인접 리스트 이용
- 가중치가 없는 트리의 경우
ArrayList< ArrayList > list = new ArrayList<>();- 가중치가 있는 트리의 경우
1)class Node { int num, dist; // 노드 번호, 거리 }정의
2)
ArrayList[] list = new ArrayList[정점의 수 + 1];종류
편향 트리 (skew tree)
모든 노드들이 자식을 하나만 가진 트리
왼쪽 방향으로 자식을 하나씩만 가질 때 left skew tree 오른쪽 방향으로 하나씩만 가질 때 right skew tree 라고 함.
이진트리 (Binary Tree)
각 노드의 차수(자식 노드)가 2 이하인 트리
완전 이진 트리(Complete Binary Tree)
- 트리의 모든 높이에서 노드가 꽉 차있는 이진 트리.
즉, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. - 마지막 레벨은 꽉 차있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
- 마지막 레벨 h에서 (1~2h-1)개의 노드를 가질 수 있다.
- 또 다른 정의는 가장 오른쪽의 잎 노드가 제거된 포화 이진 트리다.
- 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.
전 이진 트리
(Full Binary Tree 또는 Strictly Binary Tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리.
포화 이진 트리(Perfect Binary Tree)
- 전 이진 트리이면서 완전 이진 트리인 경우
- 모든 말단 노드는 같은 높이에 있어야 하며,
마지막 단계에서 노드의 개수가 최대가 되어야 한다. - 모든 내부 노드가 두 개의 자식 노드를 가진다.
- 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.
- 노드의 개수가 정확히 2^(k-1)개여야 한다.
(k: 트리의 높이)
-> 흔하게 나타나는 경우가 아니다.
즉, 이진 트리가 모두 포화 이진 트리일 것이라고 생각하지 않는다.
이진 탐색 트리 (Binary Search Tree, BST)
순서화된 이진 트리
노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야 하며 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야 함.
(모든 왼쪽 자식 <= 부모 노드 < 모든 오른쪽 자식)
m 원 탐색 트리(m-way search tree)
최대 m개의 서브 트리를 갖는 탐색 트리
이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용함.
균형 트리 (Balanced Tree, B-Tree)
m원 탐색 트리에서 높이 균형을 유지하는 트리
height-balanced m-way tree라고도 함.
ex. 레드 - 블랙 트리, AVL 트리
사용 사례
계층 적 데이터 저장
트리는 데이터를 계층 구조로 저장하는 데 사용
ex. 파일 및 폴더는 계층적 트리 형태로 저장
효율적인 검색 속도
효율적인 삽입, 삭제 및 검색을 위해 트리 구조를 사용
힙(Heap)
힙도 트리로 된 자료 구조이다.
힙(heap)이란 참고
- 최소힙(Min Heap)
트리의 마지막 단계에서
오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는
완전 이진 트리이며,
각 노드의 원소가 자식들의 원소보다 작다.
즉, key(부모 노드) >= key(자식 노드)인 완전 이진 트리
가장 큰 값은 루트 노드이다.
N개가 힙에 들어가 있으면 높이는 log(N)이다. - 최대힙(Max Heap)
원소가 내림차순으로 정렬되어 있다는 점에서만 최소힙과 다르다.
각 노드의 원소가 자식들의 원소보다 크다.
데이터 베이스 인덱싱
데이터베이스 인덱싱을 구현하는데 트리를 사용
ex) B-Tree, B+Tree, AVL-Tree..
트라이(Trie)
사전을 저장하는 데 사용되는 특별한 종류의 트리
접두사 트리(Prefix Tree)라고도 부름.
n-차 트리(n-ary Tree)의 변종
각 노드에 문자를 저장하는 자료구조
따라서 트리를 아래쪽으로 순회하면 단어 하나가 나온다.
접두사를 빠르게 찾아보기 위한 흔한 방식으로,
모든 언어를 트라이에 저장해 놓는 방식이 있다.
유효한 단어 집합을 이용 하는 많은 문제들은 트라이를 통해 최적화할 수 있다.
💡 참고 포스팅
코딩 테스트를 위한 트리(Tree) 자료구조 10분 핵심 요약
[자료구조] 트리 (Tree)
[자료구조] 트리(Tree)란
