[CS 면접 대비] 자료구조/알고리즘 비선형 자료구조(Graph, Tree, Binary Tree, Full Binary Tree, Complete Binary Tree,Binary Search Tree) 개념 & 질문 정리

비선형 구조 (목차)

• Graph
• Tree
• Binary Tree
• Full Binary Tree
• Complete Binary Tree
• Binary Search Tree

---

 

비선형자료구조란? : 하나의 자료 뒤(안)에 여러개의 자료가 존재할 수 있는 것을 의미

---

 

*비선형 자료구조에 대해 정리하기 전, 먼저 전체적인 자료구조의 형태를 이해하기 위해 아래 이미지를 첨부한다.

자료구조의 형태

---

1. Graph

: 그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조. 연결된 노드 간의 관계를 표현할 수 있음

그래프의 특징

- 그래프는 순환 혹은 비순환 구조를 이룬다

- 그래프는 방향이 있는 그래프와 방향이 없는 그래프가 있다.

- 루트 노드의 개념이 없다 / 부모-자식 관계라는 개념이 없다.

- 2개 이상의 경로가 가능하다.(무방향, 방향, 양방향 가능)

- 그래프는 네트워크 모델이다.

 

 

** 오일러 경로(Eulerian tour)

: 그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 되돌아오는 경로를 말한다.
그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다.

---

2. Tree

: 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조, 트리는 그래프 중에서도 특수한 케이스

트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다.

이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다. (부모-자식 관계가 성립하기 때문에 계층형 모델)

트리의 특징

- 부모-자식 관계가 존재해 레벨이 존재한다.(최상위 노드=Root)

- 노드가 N개이면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 2^k개

- 방향성이 존재하고 사이클은 존재하시 않는다.(비순환)

- 트리의 순회는 전위순회, 중위순회, 후위순회 3가지가 존재한다

 

 

트리와 그래프 비교

그래프, 트리 비교

자세한 비교

---

3. Binary Tree (이진 트리)

: 자식노드가 최대 두 개인 노드들로 구성된 트리

정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있음

 

면접질문!

 

? ? BST(Binary Search Tree)와 Binary Tree에 대해 설명해주세요.

: 이진트리(Binary Tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이고,

이진 탐색 트리(BST)는 이진 탐색과 연결 리스트를 결합한 자료구조입니다.

이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있습니다.

이진 탐색 트리는 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 값은 부모 노드보다 커야 하는 특징이 있습니다. 이진 탐색 트리의 탐색 연산은 트리의 높이에 영향을 받아 높이가 h일 때 시간 복잡도는 O(h)이며,

트리의 균형이 한쪽으로 치우쳐진 경우 worst case가 되고 O(n)의 시간 복잡도를 가집니다. 

이런 worst case를 막기 위해 나온 기법이 RBT(Red-Black Tree)입니다.

 

? ? RBT(Red-Black Tree)에 대해 설명해주세요.

: RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식 자료구조이며,

RBT는 BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어졌습니다.

BST를 기반으로 하기 때문에 당연히 BST의 특징을 모두 갖습니다.

노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장합니다. 이러한 NIL들을 leaf node로 간주합니다.

모든 노드를 빨간색 또는 검은색으로 색칠하며, 연결된 노드들은 색이 중복되지 않습니다.

 

 

 

---

4. Full Binary Tree (정 이진트리)

: 모든 레벨에서 노드들이 꽉 채워진(=잎새노드를 제외한 모든 노드가 자식노드를 2개 가짐) 이진트리입니다.

정이진트리

정 이진트리는 잎새노드를 제외한 모든 노드가 자식노드를 2개 또는 0개 가짐

---

5. Complete Binary Tree (완전 이진 트리)

: 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리입니다. 그리고 데이터가 왼쪽부터 채워져야한다.

마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

 

---

6. Binary Search Tree

:  이진 탐색 트리란 정렬된 이진트리를 말한다.

 

** 이진 탐색 트리의 특징

• 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드만 포함
• 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드만 포함
• 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야함
• 중복된 키를 허용하지 않음