Balanced Tree - B-tree, Red-black tree, AVL tree

Balanced Tree(Balanced Tree)

이진 트리는 자식을 최대 두 개만 가짐으로써 O(log N) 의 탐색 효율을 보인다. 그런데 좌우 서브트리의 균형이 맞지 않을 때는 어느 한 쪽만 탐색하게 되므로 O(N) 이라는 비효율적인 성능을 보여주니 좌우 밸런스를 맞출 필요가 있다. 루트를 기준으로 왼쪽, 오른쪽 서브트리의 노드 개수가 균형적이면 Balanced Tree 라고 한다. Blanced Tree 에는 B-tree, red-black tree, AVL tree  등이 있다. 

 

여기서 '균형이 잡혔다' 라는 뜻은 양쪽 노드의 자식 노드가 2개 이상 차이가 나지 않는, 즉 높이 차이가 2 이상 차이나지 않는 상태를 말한다. (1개 까지는 괜찮다.) 같은 레벨에 꽉 차 있는 경우는 완전 균형이라고 한다.

 

B-tree

이진 트리를 확장해, 하나의 노드가 여러 개의 데이터를 가질 수 있는 트리이다. 노드가 가진 데이터의 개수에 따라 자식 노드의 개수가 정해진다. 한 노드가 최소 n개 이상의 데이터를 가진 B-tree 를 n차 B-tree 라고 하며 홀수차수냐 짝수차수냐에 따라 알고리즘이 다르다. 아래 규칙에 따라 Balanced Tree 형태를 유지한다.

 

B-tree의 규칙

• 노드의 데이터 개수가 n개라면 자식 노드의 수는 n+1개다.
• 각 노드 안의 데이터들은 정렬된 상태여야 한다.
• 데이터의 왼쪽 서브트리는 데이터보다 작은 값들이고, 오른쪽 서브트리는 큰 값들이다.
• 루트 노드는 적어도 2개 이상의 자식을 가져야 한다. (자식 노드의 수가 n+1개여야 하니까)
• n차 B-tree는 루트 노드를 제외한 모든 노드가 적어도 n개 이상의 데이터를 가져야 한다.
• leaf 노드는 같은 레벨에 있어야 한다. 
• 입력된 데이터는 중복될 수 없다.

 

AVL Tree

스스로 균형을 잡는 Self-Balancing 이 적용된 이진 탐색 트리다. 이진 탐색 트리의 경우 뷸균형 상태에서는 O(N)이라는 성능을 띄므로 성능이 떨어지지 않게 균형을 유지하게 한 것이다. 참고로 AVL 은 이 자료구조를 만든 사람들의 앞 이름을 땄다고 한다...

 

AVL 트리에서는 각 노드가 Balance Factor(BF) 정보를 가지고 있다. BF 는 (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이) 이다. 균형이 유지되고 있다면 BF 는 -1, 0, 1의 값을 가진다. 이 이상이 나오면 균형이 깨진 것으로 보고 👉  이진탐색트리처럼 rotation 을 한다.

 

Red-Black Tree

마찬가지로, 스스로 균형을 잡는 Self-Balancing 이 적용된 이진 탐색 트리다. AVL 트리와 균형을 잡는 규칙이 다르다. 각 노드에 Red or Black 색깔을 저장해, 색깔을 기준으로 균형을 맞춘다. 균형은 아래와 같은 규칙으로 유지된다. 아래 규칙을 따르면 루트부터 리프까지 블랙 노드의 개수가 같아진다. 마찬가지로 균형을 잡기 위해 이진탐색트리처럼 rotation 을 한다.

더 설명해자면, 2-3-4트리(3차 B-Tree와 동일한 구조)를 Balanced 하게 유지한 트리이다. 한 노드가 한 노드 안에 들어 있던 3 개의 데이터 가운데를 검정색, 양 옆을 빨간색으로 나눈 것. 

 

Red-Black Tree 규칙

• 모든 노드는 Red or Black 이다.
• 루트와 모든 leaf 노드는 Black 이다.
• Red 노드의 자식 노드는 모두 Black 이다. => No double red
• 같은 레벨의 노드들은 리프노드까지 가는 경로에 같은 수의 Black 노드를 포함한다. => black height

 

AVL Tree vs Red-Black Tree

Red-Black Tree 는 상대적으로 AVL Tree 보다 균형이 느슨해서 rotation이 거의 이루어지지 않는다. 때문에 AVL 트리보다 빠르게 삽입/삭제 연산을 수행한다. 또 AVL 트리는 BF 라는 int 값을 가지고 있어 메모리를 더 잡아먹는다. Red-Black 트리는 2가지 색상이므로 bit 같이 두 가지 값만 표현하면 된다. 이런 이유들로 Red Black Tree 가 많이 쓰이고 있다.