[Data Structure] Tree, Binary Search Tree, Graph

1. 트리(Tree)
트리는 부모-자식의 계층구조를 가진 자료구조를 의미한다. 자식은 여럿일 수 있지만, 부모는 하나라는 특징이 있다. 

 

트리 최상단에 위치한 부모 노드를 루트 노드(Root Node)라고 한다. 그리고, 자식이 없는 노드는 리프 노드(Leaf Node) 혹은 터미널 노드(Terminal Node)라고 한다. 그 외의 노드들은 내부 노드(Internal Node) 라고 한다.

 

아래 그림에서 루트 노드는 A, 리프 노드는 F, G, H 가 된다.

 

 

Tree

트리 관련해서 추가적으로 살펴볼 개념은 다음과 같다. 
- 엣지(Edge) : 노드와 노드를 이어주는 선을 의미한다. 한 노드와 다른 노드와의 관계를 설명한다. 

- 레벨(Level) : 루트 노드로부터의 거리를 의미한다.

                      그림의 경우,  레벨 1은:A, 레벨 2는 B, C  레벨 3은 E, F, G, 그리고 레벨 4는 H이다.

- 높이(Height) : 리프 노드로부터의 거리를 의미한다. 리프 노드가 여러 개일 경우, 루트 노드의 후손 노드중 가장 먼 리프 노드를 기준으로 카운트한다.
그림에서는 리프 노드 H 를 기준으로 카운트한다. 따라서 E의 높이는 B의 높이는 2, A의 높이는 3이다.

- 차수(Degree) : 자식 노드의 개수를 의미한다. A의 차수는 2, G의 차수는 0이 된다.

- 서브트리(Sub Tree) : 트리 내부의 트리. 즉 하위구조 트리를 의미한다. 그림에서는 두 개의 서브트리 X와 Y를 표시하였다. 

- 포리스트(Forest) : 서브트리들의 집합을 의미한다. 이 경우, [X, Y] 가 포리스트가 된다. 

 

2. 바이너리 서치 트리(Binary Search Tree)
일단 바이너리 트리는 자식 노드가 최대 2개인 트리를 의미한다. 따라서 자식이 없거나, 하나만 있어도 바이너리 트리로 인정되며, 자식이 세 개 이상이 되는 경우 바이너리 트리가 될 수 없다.

 

바이너리 서치 트리 역시 바이너리 트리의 일종이다. 바이너리 서치 트리의 특징은 각 노드에 키가 규칙을 가지고 배치되어 있다는 특징이다.  각 노드의 값에 대해, 그 노드의 왼쪽 서브트리에 있는 값들은 해당 노드 값보다 작거나 같고, 오른쪽에 있는 서브트리의 값들은 해당 노드의 값보다 크거나 같다. 

 

Binary Tree (Left), Binary Search Tree(Right)

위 그림을 보면, 루트노드 5를 기준으로 왼쪽에 서브트리 X, 오른쪽에 서브트리 Y가 있다. 루트노드의 값인 5를 기준으로, 왼쪽 서브트리인 X의 노드들은 5 이하의 값을 가지는 반면, 우측 서브트리인 Y의 노드들은 5이상의 값을 가진다. 때문에 위 트리는 바이너리 서치 트리가 된다.

 

자료들이 규칙을 가지고 있기 때문에, 특정 값을 검색하는 데 용이하다. 예를 들어, 4라는 값을 바이너리 서치트리에서 찾는다면 전체 노드를 다 살필 필요 없이, 규칙에 따라 빨간색 화살표를 따라가며 해당 값을 찾아가면 된다. 

 

 

3. 그래프(Graph)

Tree vs. Graph

트리는 들어오는 곳은 하나(루트 노드) 나가는 곳은 여러 개(리프 노드) 즉, 엣지의 방향이 위에서 아래로 향하는 자료구조이다. 

 

Tree vs. Graph

이와 달리 그래프는 위에서 아래 뿐만 아니라 아래에서 위로 향할 수도 있고, 방향이 없을 수도 있으며, 순환하는 등 더 복잡한 구조를 가지고 있다. 엄밀히 말하자면 트리는 그래프의 한 종류로 볼 수 있다. 

Directed Graph vs. Undirected Graph

그래프의 엣지는 방향이 있을 수도, 없을 수도 있다. 있으면 Directed Graph, 없으면 Undirected Graph 가 된다. 트리 역시 원칙으로는 위에서 아래로 흐르는 Directed Graph 이지만, 방향이 한 가지밖에 없기 때문에 일반적으로 화살표를 생략한다. 

Directed Graph vs. Undirected Graph

 

Cyclic Graph vs. Acyclic Graph.

그래프 내의 노드들이 서로 순환할 때 이를 서클이라고 한다. 그래프 내에 하나 이상의 서클이 있는 경우를 Cyclic Graph, 없으면 Acylcic Graph 라고 한다.

 

Cyclic Graph vs. Acyclic Graph

 

* 그래프를 표현 하는 방법 : Adjacency Matrix vs. Adjacency LIst

그래프를 표현하는 방법은 크게 두 가지로 나뉠 수 있다. 

 

1) Adjacency Matrix (인접행렬) : 그래프를 표에 표현하는 방법. 서로 직접 연결된 노드들에는 1을, 연결되지 않은 노드들에는 0을 채워가는 방식이다. 

 

Adjacency Matrix

 

2) Adjacency LIst (인접 리스트): 배열 안에 모든 노드를 집어넣고, 해당 노드와 인접한 노드들을 연결리스트(LInked List)로 나열하여 저장하는 방식. 이 때, 나열의 순서는 바뀌어도 무방하다.   

 

Adjacency List

레퍼런스 : 엔지니어대한민국 (https://www.youtube.com/watch?v=fVcKN42YXXI)