트리(Tree)
트리(Tree)란, 부모/자식관계를 가지는 구조로, 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다.
트리(Tree)의 용어
출처: Tree
- 루트 노드(root node): 트리의 최상단 노드로, 트리는 하나의 루트 노드만을 가짐.
- 단말 노드(leaf node): 자식이 없는 노드로, ‘말단 노드’ 또는 ‘잎 노드’라고도 함.
- 내부(internal) 노드: 단말 노드가 아닌 노드가 아닌 노드
- 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
- 형제(sibling): 같은 부모를 가지는 노드
- 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
- 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
- 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
- 트리의 차수(degree of tree): 트리의 최대 차수
- 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
트리(Tree)의 특징
- 트리는 그래프의 한 형태이다. 즉, 그래프 안에 여러 종류 중 트리가 있다.
- 트리는 방향이 위에서 아래로만 향하는 방향 그래프이다. 즉, 노드들 사이의 선을 간선(edge)라고 하는데, 트리는 간선의 방향이 위에서 아래이다.
- 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다. 즉, loop나 circuit이 없고, self-loop도 없다. 즉, 사이클이 없다.
- 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
트리(Tree)의 종류
- 서브 트리(Sub Tree): 전체 트리는 작은 트리로 구성되어 있는데, 이 작은 트리를 서브 트리(Sub Tree)라고 한다.
- 이진 트리(Binary Tree): 자식 노드가 최대 2개까지만 붙는 트리를 이진 트리(Binary Tree)라고 한다. 즉, 자식 노드가 1개이거나, 2개일 경우 모두 이진 트리이다.
출처: Binary Tree
- 이진 검색 트리(Binary Search Tree): 노드안에 데이터가 왼쪽 노드와 그 이하 자식 노드들은 현재 노드보다 작아야 하고, 오른쪽 노드와 그 이하 노드들은 현재 노드보다 커야 한다. 이 조건을 만족하는 트리를 이진 검색 트리(Binary Search Tree)라고 한다. 노드를 보고, 해당 노드보다 큰 값을 찾고 싶으면, 오른쪽에서 찾으면 되고, 해당 노드보다 작은 값을 찾고 싶으면, 왼쪽에서 찾으면 된다. 따라서, 어떤 값을 찾을 때, 두 갈래 길을 선택해서 가다보면, 그 값을 찾을 수 있다.
