4. 트리 (Tree)

트리란?

이진 트리의 예시 (출처=위키디피아)

 

 노드 간에 부모 - 자식 관계를 가지는 방향성이 있는 그래프. 한 부모 노드가 여러 개의 자식 노드를 가질 수 있기 때문에 비 선형 자료 구조이다. 항상 부모가 없는 가장 상위의 루트(root)노드로 부터 시작해 뻗어나가는 모양이 나무와 닮아 tree라는 이름이 붙었다.

 

트리의 용어

 트리에는 사용의 편리함을 위해 사용하는 개념과 용어들이 있다.  아래 트리의 예시를 기준으로 설명하겠다.

 

예시 트리와 용어 설명을 위한 그림 (출처=나무위키)

 

 1. 루트 노드 (root) : 부모가 없는 가장 최상위 노드. 위 트리에서는 가장 상단의 1번 노드이다.

 2. 부모 노드 (parent) : 한 노드와 연결된 상위 노드. 예를 들어 2번 노드의 부모는 1번 노드이고, 6번 노드의 부모는 3번 노드이다.

 3. 자식 노드 (child) : 한 노드와 연결된 하위 노드. 예를 들어 2번 노드의 자식은 4, 5번 노드이다.

 4. 형제 노드 (sibling) : 같은 부모를 가진 노드. 예를 들어 7번 노드의 형제 노드는 6번 노드이다.

 5. 리프 노드 (leaf) : 자식을 가지고 있지 않은 노드. 위 트리에서 리프 노드는 4, 5, 6, 7번 노드이다.

 6. 레벨 (level) : 루트 노드를 시작으로 해당 노드까지 연결된 간선들의 개수. 예를 들어 5번 노드의 레벨은 2이다.

 7. 차수 (degree) : 노드의 자식의 개수. 예를 들어 1번 노드의 차수는 2이다. 

 8. 트리의 차수 (degree of tree) : 트리 내 차수의 최대값. 위 트리의 차수는 2이다.

 9. 길이 (length) : 출발 노드에서 도착 노드까지 거치는 간선의 개수.

 10. 깊이 (depth) : 루트 경로의 길이를 말한다. 예를 들어 6번 노드의 깊이는 2이다.

 11. 높이 (height) : 트리에서 가장 긴 루트 경로를 말한다. 위 트리의 높이는 2이다.

 

트리의 종류

 트리는 차수의 조절, 삽입과 삭제의 규칙을 통해 다양한 형태의 구조로 변형이 가능하다. 상세한 트리의 종류는 이후 이어질 포스팅을 통해 공부할 것이다.

 

1. 이진 트리 (binary tree)

 트리의 차수가 2인 트리이다. 풀어서 말하면 각 노드가 가질 수 있는 자식이 최대 2개인 트리이다. 우리가 생각할 수 있는 가장 단순한 형태의 트리이며, 이를 베이스로 심화된 형태의 트리들이 존재한다.

 

2. 이진 탐색 트리 (Binary Search Tree / BST)

 이진 트리를 활용해 탐색에 용이하게 구성한 트리로, 왼쪽 자식에는 부모노드보다 작은 값, 오른쪽 자식에는 부모노드보다 큰 값을 저장하는 정책을 통해 값을 손쉽게 찾을 수 있는 형태를 갖춘다.

 

3. AVL 트리 (AVL tree)

 BST에 균형 트리의 특징을 혼합한 것으로 BST가 불균형하게 이루어지면 시간 복잡도가 늘어나는 단점을 보완하기 위한 형태이다. 만약 균형이 무너지게 되면 악명높은 회전을 통해 트리의 균형을 이룬다.

 

4. 힙 트리 (heap tree)

 가장 작은 값 혹은 가장 큰 값을 즉시 찾을 수 있도록 구성한 이진 트리의 한 일종이다. 보통 그냥 힙(heap)으로 불린다. 항상 루트노드에 최대 값이 있다면 max-heap(최대힙), 최소값이 있다면 min-heap(최소힙)으로 불린다. 이 또한 삽입과 삭제의 규칙을 통해 항상 루트에 특정 조건의 값이 있도록 유지한다.