TIL_Tree, Binary Search Tree

김진경·2020년 4월 3일

IM19

목록 보기

11/21

Tree

Tree의 개념

트리에 대해 이야기 하기 전에 먼저 그래프(Graph)에 대해 간단히 이야기해보자. 그래프(Graph)는 노드(node.데이터를 저장하는 단위)와 간선(edge. 노드들의 사이를 이음)을 하나로 모아놓은 자료 구조이다. 그리고 트리는 이런 그래프의 한 종류이다.

트리는 순환(cycle)이 없는 연결그래프(Connected Graph)이자,
DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류이다.

트리는 스택(Stack), 큐(Queue)와 다른 비선형구조이다. 선처럼 이어지지 않고 그물, 혹은 뿌리 모양으로 데이터가 계층적으로 구성되어있다. 트리는 층마다 노드, 간선의 수가 다르기 때문에 각 계층이 구분되는 특징이 있다. 또한 데이터를 저장, 사용하는 선형 구조와 다르게 데이터를 표현하는 것에 초점이 맞춰져 있다. 컴퓨터의 Directory가 가장 대표적인 예라고 할 수 있다.

Tree의 구조

트리는 다음과 같은 구조적 특징을 가진다.
0. 트리는 언제나 노드의 개수가 간선의 개수보다 1개 많다. node = edge + 1
1. 노드(node): 자료를 저장하는 단위. 정점(vertex)라고도 부른다.
2. 루트 노드(root node): 부모가 없는 노드. 트리는 단 하나의 루트 노드만을 가진다.
3. 단말 노드(leaf node): ‘단말 노드(terminal node)’ 또는 ‘잎 노드’라고도 부른다. 이 노드는 자식이 없다.
4. 내부 노드(internal node): 단말 노드가 아닌 노드. 자식을 가진 노드이다.
5. 간선(edge): 노드를 연결하는 선. link, branch 라고도 부른다.
6. 형제(sibling): 같은 부모를 가진 노드의 관계를 말한다.
7. 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 말한다.
8. 노드의 레벨(level): 트리의 특정 깊이를 공유하는 노드의 집합이다.
9. 노드의 차수(degree): 해당 노드의 자식 수를 말한다.
10. 트리의 차수(degree of tree): 가장 많은 차수을 가진 노드의 차수를 그 트리의 차수라고 말한다.
11. 트리의 높이(height): 트리의 가장 높은 레벨(level)을 높이(height)라고 말한다.
12. 서브 트리(sub tree): 전체 트리에 속하는 작은 트리.

Binary Search Tree(이진탐색트리)

이진 탐색 트리는 이진 트리를 기반으로 탐색하기 위한 자료구조이다.
이진 탐색 트리는 다음의 4가지를 조건으로 구성된다.

1. 모든 노드의 키는 유일하다.

여기서 키는 노드에 들어있는 데이터를 의미한다. 즉 중복된 데이터가 없어야 한다는 조건이다.

2. 왼쪽 서브트리의 키들은 루트의 키보다 작다.

만약 루트 노드의 데이터가 5라고 한다면, 왼쪽 서브 트리에는 무조건 5보다 작은 값만 존재해야 한다.

3. 오른쪽 서브트리의 키들은 루트의 키보다 크다.

왼쪽과 상충하는 개념으로, 오른쪽에는 루트보다 큰 데이터 값만 존재해야 한다.

4. 왼쪽, 오른쪽 서브트리의 키들 역시 이진 탐색트리이다.

루트 아래에 존재하는 모든 서브트리들에도 위 1,2,3의 조건들이 동일하게 적용된다.

위와 같은 조건들을 만족시키는 예시는 다음과 같다.

그렇다면 위 조건을 기반으로 이진 탐색 트리를 구성하는 이진 트리란 뭘까?
이진트리는 모든 노드의 차수가 2 이하인 트리를 말한다.
이때 자식 노드는 왼쪽 노드, 오른쪽 노드가 구분되어 지정된다.
즉 다음과 같이 같은 데이터를 가져도 다른 트리가 존재할 수 있다.