Tree(Binary Tree, 포화 이진 트리, 완전 이진 트리, BST)

Tree

트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고 트리 구조로 배열된 일종의 계층적 데이터의 집합이다.

따라서 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 자료를 저장하는 것이 목표라기보다는, 자료 간의 관계를 표현하는 것이 더 우선인 자료구조라고 볼 수 있다.

 

 

Tree의 특징

1. 부모/자식 계층 구조를 가진다.

2. V - 1 = E (노드 수 - 1 = 간선 수)

모든 노드가 자신의 부모 노드와 연결된 간선을 가지고 있는데 루트 노드는 부모 노드가 없기 때문에 간선이 하나 부족하다.

3. 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내에서 특정 노드와 특정 노드까지의 경로는 반드시 존재한다.

 

 

Tree의 구성요소

1. Node(노드) : 트리를 구성하고 있는 각각의 요소

2. Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선

3. Root Node(루트 노드) : 트리 구조에서 최상위에 있는 노드

4. Terminal Node(leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드

5. Internal Node(내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드(루트 노드 포함)

6. Parent Node(상위노드) : 특정 노드의 이전 노드

7. Child Node(하위노드) : 특정 노드의 다음 노드

8. Ancestor of Node(노드의 조상) : 특정 노드로부터 루트까지의 경로에 있는 모든 노드

9. Sibling(형제) : 동일한 상위 노드의 하위 노드

10. Level(레벨) : 루트 노드에서 해당 노드까지의 경로에 있는 간선 수

11. Depth(깊이) : 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리(각 노드마다 다름)

12. Height(높이) : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리 

13. Subtree(서브 트리) : 트리 내의 하위 집합

 

 

Tree의 유형

1. General Tree

일반적인 트리 데이터 구조는 노드 수에 제한이 없다. 즉, 부모 노드가 여러 개의 자식 노드를 가질 수 있다.

2. Binary Tree

이진트리의 노드는 최대 두 개의 하위 노드를 가질 수 있다.

3. Balanced Tree

왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같거나 최대 1 차이가 나는 경우의 트리를 말한다.

4. Binary Search Tree(BST)

이름에서 알 수 있듯이 이진 검색 트리는 다양한 검색 및 정렬 알고리즘에 사용된다. BST에 대한 자세한 설명은 아래쪽에서!

 

 

Binary Tree(이진트리)

이진트리는 자식 노드 수가 두 개 이하인 트리를 의미한다.

이진트리는 다시 크게 5가지로 분류할 수 있다.

1. 정이진 트리(Full Binary Tree): 자식 노드가 0 또는 두 개인 이진 트리
2. 완전 이진 트리(Complete Binary Tree) : 왼쪽에서부터 채워져 있는 이진 트리.
   마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있음(마지막 레벨은 왼쪽부터 채워져 있음)
3. 변질 이진 트리(Degenerate Binary Tree) : 자식 노드가 하나밖에 없는 이진 트리
4. 포화 이진 트리(Perfect Binary Tree) : 모든 노드가 꽉 차 있는 이진 트리
5. 균형 이진 트리(Balanced Bianry Tree) : 왼쪽과 오른쪽 노드의 높이 차이가 1이하인 이진 트리(ex. 레드블랙트리)

배열로 구성된 Binary Tree는 노드의 개수가 n개이고 root가 0이 아닌 1에서 시작할 때,

i 번째 노드에 대해서 parent(i) = i / 2 , left_child(i) = 2*i , right_child(i) = 2*i + 1의 index 값을 갖는다.

 

 

BST(Binary Search Tree, 이진 탐색 트리)

BST는 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다.

노드를 이런 식으로 배치하면 검색하기가 용이해진다. 왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져 있기 때문에 현재 값을 기준으로 내가 왼쪽을 탐색해야 할지, 오른쪽을 탐색해야 할지 파악하기 쉬워지기 때문이다.

숫자를 맞추는 게임에서 마구잡이로 정답을 외치는 것보다 내가 15를 외쳤을 때 출제자가 up 또는 down이라고 말해준다면 나는 정답을 맞히기가 더욱 쉬워질 것이다.

BST에서 요소를 검색할 때는 보통 O(logN)이 걸린다. 하지만 최악의 경우에는 O(n)이 걸린다. 왜일까?

 

 

예를 들어 BST에 1, 2, 3, 4, 5를 삽입한다면 그 형태는 왼쪽과 같을 것이다.

이때 1을 찾고자 한다면 루트에서부터 시작해서 모든 노드를 다 탐색해야 1을 찾을 수 있는 것

BST의 이러한 문제를 해결하기 위해 등장한 것이 AVL 트리(Adelson-Velsky and Landis Tree)이다. 이에 대해서는 나중에 살펴보도록 하자.

 

 

 

 

BST의 4가지 규칙

1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

 

 

References

JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#tree

introduction-to-tree-data-structure-and-algorithm-tutorials

binary-search-tree-data-structure

⌜면접을 위한 CS 전공 지식 노트⌟