[자료구조] 11-2. 계층적 자료구조의 탐색

이번에는 계층적 자료 구조를 알아보자. 지금까지 배웠던 트리 구조가 계층적 자료구조에 속한다.

 

이진 트리의 탐색 연산은 중위, 전위, 후위 우선 탐색이 있었다. 일반적인 트리는 넓이 우선, 깊이 우선을 사용한다.

트리 구조에 저장되어 있는 원소를 찾는 검색 방법에도 두 가지가 있었다. 임의의 원소를 찾는 데엔 이진 탐색 트리, TOP을 찾는 데엔 heap을 사용했다.

트리 탐색의 세 가지 방법은 모두 시간 복잡도가 O(n)이다.

이진 탐색 트리에 대한 복습을 해보자. 이진 탐색 트리는 아래의 네 가지 조건을 만족해야 한다.

1. 각 노드에는 서로 다른 값이 저장된다.

2. 왼쪽 부분 트리의 값은 루트 노드의 값보다 작다.

3. 오른쪽 부분 트리의 값은 루트 노드의 값보다 크다.

4. 왼쪽 부분 트리와 오른쪽 부분 트리는 모두 이진 탐색 트리이다.

현재 내가 찾고자 하는 값이 그 노드에 있는 값인지 물어보고, 같다면 그걸 리턴하고 더 작으면 왼쪽 서브 트리로, 크다면 오른쪽 서브 트리로 가서 서치를 수행한다.

이진 탐색 트리에서 검색의 시간 복잡도는 O(log n)이다.

정렬된 리스트보다 더 좋은 점은 원소 추가 시간이 O(log n)인 것이다. 더 나쁜 점은 최선의 경우과 최악의 경우를 나눠서 분석을 해야 하는데 최악의 경우에는 모든 연산이 O(n)이 걸려 정렬되지 않은 리스트와 유사하다는 것이다.

heap은 우선 순위가 가장 높은 원소가 가장 앞에 오는 큐를 트리 형태로 구현한 것이다. 조건은 완전 이진 트리여야 한다는 것이다.

최대 힙의 경우에는 노드에 저장된 값이 반드시 자식 노드보다 작지 않아야 한다. 반대로 최소 힙은 노드의 값이 자식보다 작아야 한다.

이진 탐색 트리는 최악의 경우 시간 복잡도가 O(n)이 된다는 단점이 있다. 이 단점을 보완하기 위해 균형 이진 탐색 트리를 사용한다.

AVL 트리는 최악의 경우 O(n)의 시간 복잡도가 발생하는 단점을 개선하기 위해 제안되었다. 

AVL 트리는 모든 노드에서 왼쪽과 오른쪽의 height 차이를 1 이하로 유지한다. 오른쪽 height에서 left height를 뺀 값에 절대값을 씌운 것을 balance factor라고 한다.

- 왼쪽 트리의 경우, 8과 12는 자식이 없으므로 0이다.

- 5는 오른쪽 서브 트리와의 height가 1이다. 왼쪽은 0이므로 1-0= 1이 balance factor가 된다.

- 10은 왼쪽 height가 2, 오른쪽 height가 1이므로 1-2 = -1이 된다.

즉, 절대값으로 바꾼 값이 1보다 작거나 같기 때문에 이 경우에는 AVL 트리라고 할 수 있다.

- 오른쪽 트리의 경우, 5의 rchild는 height=1인 서브 트리고 lchild=null이니까 balance factor=1이다.

- 10은 rchild height=0, lchild height=2이므로 0-2=-2가 된다.

즉, 절대값이 1 이상이므로 AVL 트리가 될 수 없다.

현재 이 트리는 AVL 트리다. balance factor를 계산해보면 0 0 0 0 -1에 절대값을 씌우면 1이고 1보다 작거나 같으니까 괜찮다.

만약 여기에 2를 삽입하려면 lchild로 가서 4의 lchild로 삽입할 수 있다.

즉, 왼쪽의 모양이 된다. 이때 balance factor를 계산해보면 10에서 -2가 나오므로 AVL 트리가 아니게 된다.

AVL 트리는 이러한 상황을 위해 네 가지의 연산을 수행한다. 그 중 하나를 해보자. AVL 트리로 다시 바꾸기 위해, balance factor가 깨진 트리의 height가 더 높은 경우에는 오른쪽으로 가져가고 갈곳을 잃은 5의 rchild=7을 10의 lchild로 넣어준다.

이와 같은 연산을 트리를 왼쪽으로 굴린 것 같다고 해서 single left rotate라고 한다.

이 네 가지 연산을 통해 밸런스를 유지한다.

레드 블랙 트리는 이진 탐색 트리이면서 아래의 5가지 성질을 만족해야 한다.

1. 모든 노드는 red나 black으로 표시한다. 이 ppt는 배경색때문에 혼란을 피하기 위해 레드는 옐로우로, 블랙은 화이트로 표현했다.

2. 루트 노드는 반드시 블랙이어야 한다.

3. 모든 리프 노드는 nil 노드 가지면서 black이어야 한다. 즉, null 차일드를 갖는 곳에는 반드시 nil이라고 명시적으로 아무것도 없는 노드를 갖도록 해야 한다.

4. 한 노드가 red라면 자식은 모두 black이어야 한다.

5. 한 노드에서 모든 자식 노드까지는 black 노드의 수가 같아야 한다. 예를 들어, 13을 기준으로 리프까지 오는 데에는 3개의 블랙 노드(3, 1, 11)가 있었다. 그렇다면 오른쪽의 리프 노드도 블랙 노드는 총 3개라는 뜻이다.

위에 나열된 숫자를 차례로 집어 넣어 red-black tree로 만든다고 생각해보자.

처음에 루트 노드에는 38이 들어가고, 38보다 작은 13은 왼쪽에, 더 큰 51은 오른쪽에 갈 것이다. 10을 넣으면 13 아래로 간다. 그런데 여기서 문제가 발생한다. 13과 10은 레드 차일드를 가질 수 없다. 그래서 색을 바꿔주면 조건을 만족하게 된다.

12를 넣으면 또 조건을 위배하게 되므로 아래처럼 부모-자식 관계로 구조를 바꾼다. 이런 걸 restructure라고 한다.

25를 넣으면 또 red node가 차일드를 갖는 상황이 발생했으므로 recolor 해서 조건을 만족시키도록 한다.

이렇게 연산을 반복하면 항상 어떤한 노드가 모든 차일드 노드까지 가는 경로의 길이가 같기 때문에 밸런스가 유지되는 장점이 있다.

2-3 트리는 다음에 얘기할 B+ 트리의 특수한 형태이다. 한 노드는 2개 또는 3개의 자식 노드를 가질 수 있다. 대신, 3개의 자식 노드가 있는 부모 노드는 반드시 2개의 값을 저장해야 한다.

즉, 오른쪽 그림의 노드가 a와 b를 가지고 있다면 p<a<q<b<r를 만족하도록 한다.

위의 숫자를 삽입한다면, 계속 노드를 유지하다가 6이 들어온다면, 1 3과 4 5는 포화이므로 저장할 공간이 부족하게 된다. 그래서 높이를 증가시켜서 h와 같이 된다.

B+ 트리는 한 노드가 여러 개의 자식 노드를 갖는 드리다. k-ary tree라고 한다. 각 노드는 k개의 부분 트리와 k-1개의 key값을 갖는다.

예를 들어, k=4인 트리는 4개의 차일드 노드와 3개의 key값을 저장할 수 있는 공간을 가진다.