O(logN)을 보장하는 레드-블랙 트리

지난번 HashSet과 해쉬충돌에 대해 알아보면서 해쉬충돌이 발생한 경우 HashSet(=HashMap)은 Separate Chaining 방식을 사용한다고 언급했었다.

 

특정한 임계치를 넘기 전까진 링크드리스트 구조로 노드를 연결하다가 임계치를 넘으면 자료구조를 Red-Black트리로 변경한다.

 

Red-Black트리가 무엇인지, 자바는 왜 Red-Black트리를 선택했는지 생각해보자.

 

왜 트리 구조로 변경하는가? 하필이면 왜 레드-블랙 트리로?

HashSet의 검색 성능[O(1)]을 보장하기 위해서는 노드를 링크드리스트로 연결하다간 O(N)의 시간 복잡도를 갖을 수 있다.

 

물론 데이터가 적다면 무시할 수 있겠지만 데이터가 많아진다면 O(N)은 절대 무시할 수가 없다.

 

링크드 리스트 대신 이진 탐색 트리를 사용한다면 O(N)을 피해 O(logN)의 복잡도를 갖을 수 있다.

 

하지만 중요한 전제가 있는데 이진 탐색 트리가 균형이 잘 잡혀있어야만 logN을 유지할 수 있다.

 

 

 

위 같은 트리를 편향트리라 부르는데, 링크드리스트와 별반 다른 점이 없다. 모든 노드를 탐색해야만 한다. 즉 최악엔 O(N)의 복잡도를 갖게된다.

 

이런 이유로 자바는 일반적인 이진 탐색 트리를 사용하지 않는다.

 

편향트리에서 균형트리로

트리의 균형만 잡아 줄 수 있다면 HashSet의 성능을 O(logN)으로 크게 떨어뜨리지 않을 수 있다.

 

트리의 균형을 지속적으로 잡아주는 트리 중 하나가 레드-블랙 트리(RB트리)이다. (AVL트리도 존재한다.)

 

이 자료구조 역시 이름이 특성을 잘 타나내고 있다. 모든 노드가 빨간색 혹은 검은색 이여야하는 트리다.

 

레드-블랙 트리는 아래 4가지 조건을 항상 만족하도록 트리를 구성해야하고 아래의 조건이 트리의 균형을 보장한다.

 

1. 루트는 블랙이다.

2. 모든 리프 노드는 블랙이다.

3. 루트로부터 임의의 리프 노드까지 레드 노드는 연속 2번 나타날 수 없다.

4. 루트로부터 임의의 리프 노드까지 만나는 블랙노드 수는 모두 같다.

 

또한 모든 리프노드(제일 마지막 노드)는 null리프노드를 가정한다.

 

2번 조건에 의해서 Null노드는 모두 블랙이다.

 

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

 

 

 

위 그림이 위 조건들을 모두 만족하는 레드-블랙 트리의 예시다.

 

레드-블랙트리의 최단경로가 3개의 노드가 모두 블랙으로 이루져 있다고 가정해보자.

 

이때 최장거리는 3번 조건과 4번 조건에 의해서 블랙-레드-블랙-레드-블랙 으로 길이가 5이다.

 

즉 최장거리는 최단거리보다 2배이상 길어질 수 없다.

 

따라서 시간복잡도가 O(2logN)라 해봐야 O(logN)으로 보장된다.

 

물론 위 조건을 만족시키기 위해선 조건을 위반한 트리를 회전하는 연산이 필요하지만 상수시간에 불과해 여전히O(logN)이다.

 

왜 레드-블랙 트리로 선택했을까

AVL트리는 트리의 높이차가 2이상 벌어지지 않게 유지하는 특성을 가진다.

 

다시말해 레드-블랙 트리보다 더 엄격하게 균형잡힌 트리를 유지하는 것으로 잘 알려져있다.

 

균형이 더 잘 잡혀있다는 것은 조회 시 성능이 더 좋다는 의미다.

 

하지만 보다 더 엄격한 만큼 조건을 위반한 트리를 회전하는 연산이 그만큼 많다.(삽입 삭제 시)

 

반대로 레드-블랙은 AVL보단 느슨하기 때문에 회전연산이 적다.

 

살펴보면 서로 장단이 있다. 개인적으로 자바가 레드-블랙 트리를 사용하는 이유는 범용성을 고려한 결과인게 아닌가 싶다.

 

조회 성능에만 포커스를 맞추지 않고 삽입 삭제에도 가능성을 열어둔 선택이지 않을까 생각한다.

 

극단적인 조회성능에 포커스를 맞췄다면 아마도 AVL을 선택...하지 않았을까?