이진 탐색 트리 (BST) / 레드 블랙 트리 (RED BLACK TREE) (1) 개념요약

이진 탐색 트리(Binary search tree ; 이하 BST)의 개념과 이진 탐색 트리의 일종인 레드블랙 트리(이하 RB트리로 명명)에 대한 설명입니다. 요약하면, RB트리는 BST의 한계를 개선한 트리이며 방대한 데이터를 다룰 때, 성능은 더 우수하고 기능적으로는 동일합니다. 

이진탐색트리(BST)는 왜 나왔을까?

BST, RBTREE 두 가지 모두 방대한 데이터를 효율적으로 관리하기 위한 자료구조 입니다. 여기서 말하는 관리란 탐색(searching), 수정(insert), 삭제(delete)를 의미하는데, 탐색 기능에는 이진 탐색(Binary Seach)이라는 방법을 사용합니다. 요약하자면, 전체 데이터에서 중앙값 기준으로 찾고자 하는 데이터가 왼쪽인지 오른쪽인지 비교판단을 반복하여 탐색 범위를 1/2씩 좁혀나가는 탐색방법입니다.

이진탐색에 대해서는 아래 링크에 간단히 정리해 두었습니다. 

https://campkim.tistory.com/4?category=1015777 

 

이진 트리

이진트리는 위와 같이 모든 노드에 대해서 항상 부모노드의 값은 왼쪽 자식의 값 보다 크고 오른쪽 자식노드의 값 보다 작다라는 명제를 유지 합니다. 이 특성은 하위 트리에도 유지되기 때문에,  모든 노드에 대해서 더 큰 값과 작은 값들로 이뤄진 하위 트리로 나눌 수 있습니다.

 

이진탐색 트리(BST)의 한계

이진탐색 트리의 기능은 크게 두가지로 분류 가능할 것 같습니다. 자료구조 검색 (탐색) / 유지 보수 (삽입 및 삭제) 입니다.

어떻게 트리 자료구조를 유지 보수 하는지에 따라서, 이진트리의 형태가 달라지며 얼마나 우수한 탐색 기능을 하는지 갈립니다.

 

그 이유는, 다음과 같습니다.

'이진트리의 각각의 노드는 자식을 최대 2개만큼 갖으며, 모든 노드에 대해서 항상 부모노드의 값은 왼쪽 자식의 값 보다 크고 오른쪽 자식노드의 값 보다 작다.' 이진트리의 경우 단순하게 이 명제만 만족하면 되기 때문에, 아래 그림과 같은 자료구조 또한 이진트리를 만족합니다. 

그런데, 아래와 같은 트리에서 이진탐색을 실행하면, 각 노드에 대해서 탐색범위를 좁혀나갈 수 없기 때문에 선형탐색과 동일한 시간 복잡도를 갖게 됩니다. 하기 케이스는 일반적인 이진트리(BST)에 오름차순, 혹은 내림차순으로 자료가 삽입(insert)될 때, 만들어지게 됩니다.

이러한 자료구조가 편향되는 문제점을 보완하기 위해 고안된 트리가 레드 블랙트리입니다.

레드 블랙 트리(RB TREE)

레드 블랙 트리.

RB TREE는 하기와 같은 모양을 갖습니다. BST의 알고리즘이 보완되어 유지보수(삽입, 삭제)시에 특정 조건에 따라 트리의 구조를 균형이 맞도록 재구성합니다. 규칙은 아래와 같습니다. 핵심적인 내용을 정리하면, 모든 노드에 대하여 Leaf(최하단) 노드까지 검은색 숫자가 동일해야하고, 레드는 연속으로 나올 수 없다는 규칙으로 인해 가장 긴 부분과 가장 짧은 부분이 최대 2배밖에 나지 않는 균형잡힌 트리가 형성됩니다. 

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

개념적으로는 BST, RBTREE 모두 간단합니다. 하지만 유지보수 (삽입, 삭제) 기능을 실제로 구현할때 RBTREE의 경우 꽤 복잡한 알고리즘을 갖고 있습니다. 위키를 통해 C를 통해 구현했는데, 구현내용은 다음글에 정리해보겠습니다.

 

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전