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

2024. 7. 3. 03:03

정리중인 문서인데 C++ STL 중 map이 레드-블랙 트리로 구현되어있다고 해서 관련해서 조사하던 중 균형 이진 탐색 트리라는 개념을 알게됐고 그 종류로 AVL트리, 레드-블랙 트리가 있으며 이진탐색트리는 아니지만 균형탐색트리로 B-Tree도 배우게 될 계기가 될 듯 하다. 일단 자료조사하면서 던져두고 있고 나중에 정리 한번 하면서 더 자세히 익혀볼듯하다.

/**********************************************************************************************************************/

avl트리, 레드블랙트리, b트리는 균형트리

avl, 레드블랙은 이진탐색트리

즉 b트리는 균형이진탐색트리는 아닌듯?

1. 균형트리(Balanced Tree)

모든 서브트리의 높이차이가 최대 하나인 이진트리

그래서 검색의 시간복잡도를 최적화할 수 있음

삽입,삭제시에 트리의 균형을 유지하도록 구성됨

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

노드가 최대 두개의 자식노드를 갖고, 왼쪽자식노드는 부모노드보다 작은값을 갖고, 오른쪽자식노드는 부모노드보다 큰 값을 갖는다.

- 검색연산이 효율적임 O(logN)

- 데이터를 정렬된 상태로 유지할 수 있음

- 하지만 편향되면 탐색이 O(N)이 됨

3. 균형이진탐색트리(Balanced Binary Search Tree)

이진탐색트리의 특성인

- 각 노드가 최대 두개의 자식노드를 가짐

- 왼쪽 자식노드는 부모노드보다 작은값을 가짐

- 오른쪽 자식노드는 부모노드보다 큰값을 가짐

을 유지하면서 편항된(불균형한) 상태를 피하기 위해 노드 삽입/삭제시에 트리를 재조정하는 트리

균형 이진 탐색 트리의 대표적인 종류로 AVL트리, 레드블랙트리가 있음

B-Tree도 균형트리인데 이진트리가 아님

avl트리는 삽입할때 리밸런싱을 parent노드 하나씩 타고 가기때문에 O(logN)

레드블랙은 color 개념이 추가되었기때문에 무조건 트리를 회전하는게 아니라 색깔만 바꿔도 되는 등으로 좀 더 느슨하게 리밸런싱해서 트리 회전 횟수가 감소함

그래서 삽입/삭제시에 둘 다 O(logN)이지만 레드블랙은 한번당 관점에서는 O(1)인 경우도 있으니 더 유리하게 됨

결론적으로 AVL트리는 밸런스가 엄격하게 유지되어서 탐색에 유리

레드블랙은 밸런싱을 느슨하게 하기 때문에 AVL에 비해 탐색은 불리하지만 삽입,삭제에 유리

## AVL트리

1. 개요

발명자의 이름인 Adelson-Velsky와 Landis에서 따온 이름

균형 이진 탐색 트리의 하나이며 왼쪽 서브트리와 오른쪽 서브트리의 높이차이가 1을 넘어가지 않도록 유지하는 형태

삽입/삭제 후에 균형유지를 위해 회전연산을 사용함, 그래서 삽입/삭제/탐색이 O(logN)으로 효율적

데이터가 자주 변경되는 경우 적합

위의 경우 왼쪽 서브트리는 8, 5, 11로 이루어진것이고 오른쪽 서브트리는 18과 17로 이루어진것이며 둘의 높이차이는 1이하임

그리고 또 8아래에서 볼때 왼쪽서브트리는 5, 4로 이루어진 것이고 오른쪽은 11로 이루어진 것이며 높이차이는 1이하임

2. 트리 회전

AVL트리는 삽입/삭제연산 후에 균형유지를 위해 자동으로 회전연산을 사용함

1) 단일 왼쪽회전

오른쪽 서브트리에 노드가 추가될때 트리의 균형이 깨지면(왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1을 넘으면) 단일 왼쪽 회전을 수행

2) 단일 오른쪽 회전

왼쪽 서브트리에 노드가 추가될때 트리의 균형이 깨지면 단일 오른쪽 회전을 수행

3) 이중회전 : 왼쪽 - 오른쪽 회전

불균형이 왼쪽자식노드의 오른쪽 서브트리에서 발생하는 경우

아래 그림 기준 왼쪽자식(A)를 기준으로 오른쪽 서브트리(B)에서 불균형이 발생하면 A는 왼쪽회전으로 왼쪽으로 이동하고 B는 오른쪽으로 이동함, 그러면 편향트리가 되므로 다시 B를 기준으로 C를 오른쪽회전해서 완성

4) 이중회전 : 오른쪽 - 왼쪽 회전

불균형이 오른쪽자식노드의 왼쪽 서브트리에서 발생하는 경우

아래 그림 기준 오른쪽자식(C)를 기준으로 왼쪽 서브트리(B)에서 불균형이 발생하면 C는 오른쪽회전해서 오른쪽이르 이동하고 B는 왼쪽으로 이동함, 그러면 편향트리가 되므로 다시 B를 기반으로 A를 왼쪽회전해서 완성

## 레드-블랙 트리

1. 개요

균형 이진 탐색 트리의 한 종류로 각 노드가 레드 또는 블랙인 색깔을 가짐

효율적인 검색연산을 수행할 수 있음

삽입/삭제시에 트리의 균형유지를 위해 회전과 색깔변경을 수행

2. 규칙

1) 각 노드는 레드 또는 블랙의 색을 가짐

2) 루트 노드는 블랙

3) 모든 리프 노드는 블랙(즉 NIL이 블랙)

4) 레드노드의 자식노드는 반드시 블랙

5) 어떤 노드로부터 리프 노드까지의 모든 경로에는 동일한 개수의 블랙 노드가 존재

삽입/삭제시에 위의 규칙을 위반할 수 있으므로 회전이나 색깔변경을 수행하는 것

트리의 높이

2가지 종류의 높이가 있다.

h(x) : x 자신으로부터 leaf노드까지의 가장 긴 경로의 간선 수

bh(x) : x로부트 leaf노드까지의 경로상의 블랙의 수

※ N개의 내부노드를 갖는 레드블랙트리의 높이는 2log(N+1) 이하이다.

3. 회전

1) 왼쪽회전

위 트리에서 1번노드를 왼쪽회전하면 아래와 같은 모양이 된다.

1번이 왼쪽으로 내려가고, 3번이 올라가며 3번노드의 왼쪽자식이었던 4번노드가 1번노드의 오른쪽자식이 된다.

2) 오른쪽 회전

위 트리에서 1번노드를 오른쪽회전하면 2번노드가 루트가되고, 1번노드는 오른쪽으로 내려가고, 2번노드의 오른쪽 자식이 1번노드의 왼쪽자식으로 붙는다.

4. 삽입/삭제

일반적인 이진탐색트리처럼 삽입 후 추가작업을 수행해야한다.

1) 삽입

NIL노드는 레드블랙트리의 성질을 유지시키기 위해 존재할 뿐 데이터는 없는 껍데기 노드이다.

그래서 NIL노드는 여러개 만드는게 아니라 한개만 만들고 NIL노드가 필요한 여러 노드들이 한개의 NIL노드를 가리키는 방식으로 구현한다.

그래서 NIL노드의 자식으로 새로운 노드를 삽입하는 것이 아니라 기존의 NIL노드를 없애고 새로 삽입하는 노드로 대체한 후 새로 삽입한 노드의 자식노드들로 NIL노드들을 추가한다. 그 후 새로 추가한 노드는 레드로 만든다.

그 후 규칙을 검사한다.

이때 규칙 1 ~ 5 중 위반할 수 있는 규칙이 있다.

만약 새로 삽입한 노드가 루트노드 자리로 들어갔다면 "규칙2) 루트노드는 블랙이다" 를 위반하게 된다.

이 경우 그냥 루트노드를 블랙으로 변경하면 끝이다.

또 다른 경우는 삽입한 노드의 부모노드가 레드인 경우이다. "규칙4) 레드노드의 자식노드는 반드시 블랙"을 위반하게 되며 이때는 부모노드의 형제노드인 삼촌 노드의 색상에 따라 해결방법이 나뉜다.

- 삼촌노드가 레드

부모노드와 삼촌노드를 블랙으로 변경, 조부모노드를 레드로 변경, 만약 조부모노드가 원래 레드였다면 조부모노드를 새로 삽입한 노드로 취급해서 규칙을 다시 검사하기 시작, 반복해서 타고 올라가서 부모노드가 블랙일때까지 작업을 반복, 이때 루트는 블랙이므로 반드시 언젠간 멈추게 되어있음

- 삼촌노드가 블랙

먼저 조부모노드 - 부모노드 - 삽입된 노드가 일직선상이 되게 회전시킴

예를들어 부모노드가 조부모노드의 왼쪽자식이라면 삽입된 노드가 부모노드의 왼쪽자식이어야 함