트리

 

 

트리

- 트리는 계층적 관계를 표현하는 자료구조이다.

- 가지를 늘려가며 뻗어가는 형태이다. (위아래 방향은 중요하지 않지만, 보통은 나무를 거꾸로 그린 형태)

- 계층적인 자료를 저장할 때 자주 사용하는 자료구조이다.

ex) 컴퓨터의 파일 디렉토리, 기업의 조직도, 인덱스 등등

- 그래프의 일종. 사이클이 없이 모든 정점이 연결되어있는 그래프. 따라서 정점의 갯수가 n개이면 간선의 갯수는 n-1개이며, 싸이클이 없다는 건 아래로 내려오면 다시 위로 올라가는 길이 없다는 뜻이다. 

- 항상 루트가 있는 건 아니며, 루트가 있는 트리를 rooted tree 라고 한다.

 

용어 정리

- 노드 (node)

A, B, C, D, E, F 와 같은 모든 구성요소

 

- 루트 노드 (root node)

트리 구조에서 최상위에 존재하는 A와 같은 노드

 

- 간선 (edge)

노드와 노드를 연결하는 연결선

노드가 N개인 트리는 항상 N-1개의 간선을 갖는다.

 

- 부모 노드 (parent node)

바로 위 계층으로 직접 연결된 노드

 

- 자식 노드 (child node)

바로 아래 계층으로 직접 연결된 노드

 

- 형제 노드 (sibling node)

부모 노드가 같은 노드

 

- 조상 노드 (ancestor node)

특정 노드 위에 위치한 모든 노드 → D의 조상은 B, A 

 

- 후손 노드 (descendant node)

특정 노드의 아래에 위치한 모든 노드 → A의 후손 노드는 B, C, D, E, F 

 

- 단말 노드 (terminal node) 혹은 잎사귀 노드 (leaf node)

자식 노드가 없는 노드 → C, D, E, F

 

- 내부 노드 (internal node) 혹은 비단말 노드 (nonterminal node)

자식 노드가 있는 노드이자 단말 노드를 제외한 모든 노드 → A, B

 

- 서브 트리 (sub tree)

큰 트리를 이루는 작은 트리 → A의 아래에 B를 루트 노드로 하는 서브 트리가 있음

 

- 레벨 (level)

루트(레벨 0 혹은 레벨 1)부터 시작해서 각 층별로 매긴 숫자. 특정 노드의 레벨을 구하려면 해당 노드에서 루트 노드까지 가는 간선의 수를 세어보면 된다.

 

- 높이 (height)

트리의 최고 레벨

 

- 깊이

루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수. 자식 노드의 깊이는 부모 노드 깊이의 + 1 이다.

기준을 세울 때 루트의 깊이를 0 혹은 1로 설정할 수 있는데, 이에 따라 특정 노드 n에 대한 깊이는 간선수 + 1 이 될 수도 있다.

* 아래에 나오겠지만 깊이 계산 할 때 쉽게 하려면 루트의 깊이를 1로 두어야 한다. 

 

- 차수 (degree)

1. 노드의 차수 (degree of node)

각 노드의 자식 갯수

2. 트리의 차수 (degree of tree)

트리의 최대 차수. 즉 한 트리에 속한 노드들의 디그리 중 최댓값

 

이진트리

이진트리의 정의 

- 디그리의 최댓값이 2개로 제한된 트리. 즉, 자식을 2개까지 가질 수 있다. 

- 루트 아래의 서브 트리도 모두 이진트리어야 한다.

- 이진 트리는 재귀적인 성질을 가진다.

 

그렇다면 아래의 트리는 이진트리가 아닐까?

루트 노드인 A 아래에 있는 C는 아예 자식이 없고, B는 자식이 1개이기 때문에 이진트리가 아니라고 생각할 수 있다. 하지만 이진트리는 자식을 2개까지 가질 수 있는 것이지, 꼭 2개를 갖고 있어야 하는 것이 아니다. 따라서 이진트리에서는  자식 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면 공집합(empty set) 노드가 존재하는 것으로 간주하고 진행 한다. 공집합 노드도 이진트리의 판단에 있어서 노드로 인정되기 때문에 위의 트리는 이진 트리의 조건에 부합한다. 

 

 

이진트리의 성질

이진트리의 성질을 3가지만 짚고 넘어가자!

 

1. i번째 레벨은 루트 레벨을 0으로 볼 때 최대 2의 i승, 루트 레벨을 1로 볼 때 최대 2의 (i-1)승 개의 노드를 가질 수 있다.

위와 같이 루트 레벨을 0으로 두면, 레벨 1의 최대 노드 수는 2^1, 즉 2개이다.

루트 레벨을 1로 두었을 때는 마지막 레벨이 3이 되고 레벨 3의 최대 노드의 수는 2^(3-1), 즉 4개이다.

 

2. (루트의 깊이를 1로 두었을 때) 깊이가 k인 이진 트리는 최대 (2의 k승-1)개의 노드를 갖는다.

깊이 2까지의 트리의 구성 요소는 A, B, C 이렇게 3개이다.

이는 2^2-1 과 동일하다.

 

깊이 3까지의 트리의 구성요소는 A, B, C, D, E, F, G 이렇게 7개이다.

이는 2^3-1 과 동일하다.

 

3. 이진 트리의 리프노드의 수는 degree가 2인 노드의 수 + 1 이다.

위와 같은 트리가 있을 때

 

자식이 없는 노드 = degree 0 (n0) : 3개 (F, E, C)

자식이 1개인 노드 = degree 1 (n1) : 1개 (D)

자식이 2개인 노드 = degree 2 (n2) : 2개 (A, B)

노드의 총 갯수 n = n0 + n1 + n2

리프 노드의 수 n0 = n2 + 1

 

이다.

 

증명)

1) 모든 노드의 수를 n개라고 하면 n = n0 + n1 + n2

2) 자식 노드들의 관점에서 세어보면 n = 2n2 + n1 + 1 

※ 디그리가 2인 노드는 자식이 2개일테니 곱하기 2 해주고, n1은 자식이 1이니 1을 곱해주고, 그 어떤 노드의 자식도 아닌 루트 노드를 세어주기 위해 1을 더해줘서 나온 식.

3) 따라서 n0 + n1 + n2 = 2n2 + n1 + 1 → n0 = n2 + 1

 

 

이진트리의 종류

1. 정 이진 트리 (full binary tree, proper binary tree, plane binary tree)

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

2. 포화 이진 트리 (perfect binary tree) 

깊이가 k일 때 2의 k승 - 1 개의 노드를 갖는 이진 트리.

즉, 모든 레벨이 꽉 찬, 최대 노드를 갖는 이진 트리이다.

 

3. 완전 이진 트리 (complete binary tree)

트리의 원소를 위에서 아래로, 왼쪽에서 오른쪽으로 빠짐없이 채워나간 형태이다.

포화이진트리가 아닌 완전 이진 트리는 정 이진 트리일 수도 있고 아닐 수도 있다. 

위 그림에서 마지막 트리는 왼쪽에서 오른쪽으로 채워지지 않고 B의 자식이 오른쪽부터 채워졌기 때문에 완전 이진 트리가 아니다.

 

* 완전 이진 트리의 개념에서 노드 안의 데이터 간의 크기 관계는 상관 없다.

 

* 일반적으로 비선형 구조인 이진트리는 배열로 구현하면 비어있는 자식 노드 자리를 비워놓아야 한다는 문제점 때문에 보통 리스트로 구현하여 각각의 노드가 자식들의 포인터를 갖도록 하지만, 완전 이진 트리의 경우 왼쪽부터 빠짐없이 채워져있다는 성질을 이용해 배열을 사용하여 구현하기도 한다. 1번부터 시작하는 배열을 생각하면 N번째 원소의 왼쪽 자식은 2n, 오른쪽 자식은 2n+1번째 원소로 구성하면 된다. 또 n번째 원소의 부모는 n/2번째 원소가 된다.

 

트리의 탐색

- 루트 노드에서부터 시작해서 트리의 모든 노드를 방문하는 연산

- 모든 트리에서 적용되는 일반적인 탐색은 아래와 같다.

   1. 깊이 우선 탐색 (Depth-first search, DFS)

   2. 넓이 우선 탐색 (Breadth-first search, BFS)

- 이진 트리의 탐색법은 이진 트리에만 적용 된다.

 

이진 트리 탐색법, 이진 트리의 순회 (Traversal)

이진 트리의 탐색 방법에는 여러가지가 있으며, 다음의 방법들이 제일 유명하다.

1. 전위 순회 (pre-order) 

부모 노드를 먼저 방문하는 순회 방법

부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드

 

2. 중위 순회 (in-order)

부모 노드를 중간에 방문하는 순회 방법

왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드

 

3. 후위 순회 (post-order)

부모 노드를 마지막에 방문하는 순회 방법

왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 

 

이진 트리의 종류

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

출처 : 나무위키

- 노드의 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

- 노드의 오른쪽 서브 트리에는 그 노드의 값보다 큰 값들만 지닌 노드들로 이루어져있다.

- 좌우 서브 트리를 구성할 때도 같은 규칙(왼쪽은 부모 노드보다 작은 값, 오른쪽은 큰 값)으로 적용 되어야한다. (즉, 서브 트리도 전부 이진 탐색 트리여야 한다.) 

* 위 규칙으로 인해 루트에서 왼쪽으로만 타고 내려가서 제일 아래에 있는 값이 최솟값, 루트에서 오른쪽으로만 타고 내려가서 제일 아래에 있는 값이 최댓값이다.

- 중복된 노드는 허용하지 않는다. (탐색을 위한 트리이기에 굳이 중복값을 넣어서 검색 속도를 느리게할 필요가 없기 때문이다.)

- 이상적인 상황에서 탐색/삽입/삭제 모두 시간복잡도가 O(log N) 이 된다.

- 값이 삽입되거나 삭제될 때 최악의 경우 O(N) 의 시간이 걸린다.

(1부터 10까지의 수를 순서대로 삽입한다면 1부터 오로지 오른쪽으로만 트리가 뻗어나가기 때문)

 

이진 탐색 트리의 성능 분석

정렬된 배열과 비교해보도록 하겠다. 

 

- 삽입/제거의 경우

정렬된 배열 : O(n)

이진 탐색 트리 최선 : O(log n)

이진 탐색 트리 최악 : O(n)

 

- 검색의 경우

정렬된 배열 : O(log n) → 이진탐색을 쓸 경우이다.

이진 탐색 트리 최선 : O(log n)

이진 탐색 트리 최악 : O(n)

 

- 최대값 찾기

정렬된 배열 : O(1)

이진 탐색 트리 최선 : O(log n)

이진 탐색 트리 최악 : O(n)

 

- 최대값 제거

정렬된 배열 : O(n) → 요소를 삭제한 뒤 한 칸씩 앞으로 밀어줘야하므로

이진 탐색 트리 최선 : O(log n)

이진 탐색 트리 최악 : O(n)

 

이진 탐색 트리는 최악의 경우 모두 O(n) 으로 배열보다 성능이 나쁘다.

따라서 이진 탐색 트리는 항상 균형을 유지하도록 하는 것이 중요하다.

그래서 나온 것이 균형 이진 탐색 트리이다.

 

균형 이진 탐색 트리 (Balanced Binary Search Tree, BBST)

 

자가 균형 이진 탐색 트리 (Self-balancing Search Tree) 혹은 높이 균형 이진 탐색 트리 (Height-balanced Search Tree) 라고도 한다. 이진 탐색 트리가 최악의 경우에 O(n)의 시간이 걸리는 것을 보완하기 위해 나온 트리이다.

 

균형 트리란 모든 하위 트리의 높이(height) 차가 1 이하인 트리이고, 자가 균형 이진 탐색 트리는 삽입과 삭제가 일어나는 경우에 자동으로 height를 최소로 유지하도록 설계되어 있다.

 

대표적인 자가 균형 이진 탐색 트리

- AVL tree

- Red-black tree

- 2-3 tree

- B+ tree

 

힙

힙은 다른 포스트에서 우선순위 큐와 함께 다루도록 하겠다.

 

참고한 내용들의 출처 :

책 윤성우의 열혈 자료구조

https://makemethink.tistory.com/125?category=768133 

[자료구조] 7-1. 트리의 개념

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC#%EC%9E%AC%EA%B7%80%EC%A0%81_%EC%A0%95%EC%9D%98

이진 트리 - 위키백과, 우리 모두의 백과사전

 

https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)#s-4 

트리(그래프) - 나무위키