AVL 트리와 Red-Black 트리 비교

2023-03-30 수정

 

 알다시피 트리의 높이는 곧 트리의 탐색시간을 결정한다. 이미 어떤 규칙에 의해 자식들로 나뉘는 트리에서 원하는 노드의 탐색 시간은 곧 일반적인 삽입과 삭제 시간 또한 결정한다. 따라서 트리가 어느 정도 편향되어 있는지, 자식 노드는 몇 개로 어떻게 구성되는지 같은 요소들은 트리의 전체적인 성능을 크게 좌우한다. 자료구조의 시간적 복잡도를 고려하는 과정에서 최악의 경우를 고려하지 않을 수 없다. 가장 안 좋은 트리는 모든 노드가 형제를 갖지 않고 연결된 경우일 것이다. 극단적으로 편향된 이런 트리는 연결리스트와 거의 다를바 없다. 성능 또한 마찬가지일 것이다.

 

 다수의 데이터를 저장하기 위해 만들어진 자료구조인 만큼 이런 최악의 경우뿐만 아니라 '어느 정도 나쁜' 경우도 고려를 해야한다. 이런 경우를 대처하기 위해 사용하는 이진 트리의 종류가 바로 AVL 트리와 Red-Black 트리다. 이 글에서는 두 트리의 자세한 구성 방법은 다루지 않겠다. 각 트리의 자세한 내용은 다음 문서들을 참고하기 바란다.

 

AVL 트리 - 위키백과, 우리 모두의 백과사전

 

Red–black tree - Wikipedia

 

 

트리의 성능 측정

 

 두 트리를 비교하기 위한 방법은 무엇이 있을까? 데이터 관리의 측면에서 데이터 또는 데이터가 있어야 할 곳에 얼마나 빠르게 접근할 수 있느냐가 자료구조의 성능을 결정할 것이다. 이진 트리에서 노드에 접근하는 속도는 어떻게 결정되는가? 탐색하려는 노드가 어떤 높이(또는 깊이)에 위치해 있는지가 곧 그 노드를 탐색하는데 걸리는 시간을 결정한다. 이 시간을 트리 전체 노드에 일반화 시킬 수 있을까? 완전 이진 트리에서는 (절반 + 1) 개의 노드가 리프에 위치한다. 따라서 가장 큰 높이를 가진 리프의 높이가 곧 해당 트리에서 탐색하는 데 필요한 최악의 복잡도를 결정함과 동시에 이것을 다른 노드들에 일반화 시켜도 큰 무리가 없다고 하겠다.

 

 대단히 극단적으로 편향된 트리라면 리프의 높이가 다른 노드들의 복잡도를 대변할 수는 없지만 그런 트리는 이미 다른 노드들 조차 대단히 큰 높이를 갖고 있기 때문에 여기에서 고려하지 않는다.

 

 결론적으로 트리의 성능(시간적 복잡도)은 트리의 높이, 즉 가장 큰 높이를 가진 리프 노드의 높이가 결정한다. 반대로 말하자면 같은 높이일 때 더 많은 노드를 가지고 있을 수록 트리의 성능이 좋다. 다음과 같이 표현할 수 있을 것이다.

$$SearchTime(T_1(h, n)) < SearchTime(T_2(h+i, n))$$

$$SearchTime(T_3(h, n)) == SearchTime(T_4(h, n+j))$$

 트리 T_1의 경우 T_2와 같은 수의 노드를 갖고 있지만 더 작은 높이를 갖기 때문에 탐색시간이 빠르다. 이는 당연하다.

 트리 T_3은 T_4와 같은 높이를 갖고 있지만 더 적은 노드를 갖고 있다. 탐색시간은 둘이 같은데, 탐색 시간은 노드의 개수와는 독립적이고 높이와 비례하기 때문이다. 그러나 트리 T_4는 T_3보다 더 효율적이다. 같은 탐색시간으로 더 많은 노드를 탐색할 수 있기 때문이다. 따라서 우리는 다음과 같은 명제를 얻을 수 있다.

• n이 같을 때, h가 작으면 빠른 트리다.
• h가 같을 때, n이 크면 효율적인 트리다.

 이것들은 뒤에 두 트리를 비교하는 도구로 사용될 것이다.

 

AVL 트리 성능 측정

 먼저 AVL트리의 성능을 측정해보자. AVL트리는 루트의 두 서브트리가 서로 2이상의 높이 차를 갖지 않도록 한다. 다시 말해 두 서브트리는 커봐야 1의 높이 차를 갖는다.

 

 위에서 보였다시피 트리의 성능을 측정하려면 극단적인 상황을 설정할 필요가 있다. 가장 편향된 AVL 트리를 구성한다. 아무리 편향된 AVL 트리라고 해도 두 서브트리는 1의 높이차를 가질 수 밖에 없다. N(h)가 높이 h의 편향된 AVL 트리가 갖는 노드 개수일 때, 3의 높이를 갖는 편향된 AVL 트리는 다음과 같은 노드 수를 가질 것이다.

$$N(3) = N(2) + N(1) + 1$$

 두 서브트리는 2와 1의 높이를 갖고 최대 높이 차이인 1을 보인다. 두 서브트리의 노드 개수와 루트 노드 1을 더하면 편향된 AVL 트리의 전체 노드 개수를 구할 수 있다. 위 식은 재귀적으로 적용되는데,

$$N(2) = N(1) + N(0) + 1$$

$$N(1) = 1$$

$$N(0) = 0$$

 위 식들을 일반화 해보면 다음과 같다.

$$N(h) = N(h-1) + N(h-2) + 1, N(1) = 1, N(0) = 0$$

파이썬으로 재귀함수를 구현하여 명령행 인자로 높이를 받아 편향된 AVL 트리의 전체 노드 개수를 출력하는 코드

 

Red-Black 트리 성능 측정

 먼저 레드블랙 트리의 기본 가정들을 되짚고 넘어갈 필요가 있다.

1. 모든 노드는 레드, 또는 블랙의 값을 갖는다.
2. 새로 추가되는 노드는 레드 노드이고 루트는 항상 블랙이다.
3. 레드 노드는 연속으로 존재할 수 없다.

 이와 같은 특징들과 노드의 회전으로 인해 레드블랙 트리는 특별한 규칙 하나를 만들어 낸다.

 

 루트에서부터 모든 리프 노드까지 가는 경로에 만나는 블랙 노드의 개수는 항상 같다.

 

 따라서 만약 가장 불균형한 레드블랙 트리가 존재한다면, 레드 노드가 한 쪽 방향으로만 존재하고 나머지 노드들은 블랙 노드인 트리가 될 것이다. 다시 말해, 루트부터 가장 큰 높이를 가진 리프 노드까지 가는 경로에만 레드 노드가 존재하고 그 외의 다른 노드들이 모두 블랙이라면 가장 불균형하다. 이는 다음과 같은 레드블랙 트리의 특징을 이끌어낸다.

$$MAX_H <= 2MIN_H$$

 

 제일 큰 높이를 가진 리프까지의 경로에는 모든 블랙 노드들 사이에 레드 노드가 끼워져 있을 것이고(MAX_H = BN + RN), 가장 작은 높이를 가진 리프까지의 경로에는 블랙 노드만 존재할 것이다(MIN_H = BN). 루트 노드를 경로에 포함하지 않는다면, BN과 RN의 관계는 다음과 같다.

$$RN = BN$$

 

 따라서 MAX_H = 2BN 이고 이는 위 특징을 만족한다. 그렇다면 특정 높이에서 존재할 수 있는 노드는 최소 몇 개일까?

 

 가장 불균형한 레드블랙 트리에서 높이 h에 대하여 루트에서부터 가장 큰 높이를 갖는 리프까지의 경로에 존재하는 블랙 노드의 개수는 h/2일 것이다. 루트에서부터 이에 반대편 서브트리는 모든 노드가 블랙인 완전 이진 트리가 되고 그 높이는 h/2일 것이다. 왜냐하면 루트부터 모든 리프까지 블랙 노드의 개수는 같아야 하기 때문이다.

 

 이런 방식으로 가장 큰 높이의 리프 노드까지의 경로에 있는 반대편 이진 트리를 모두 정의할 수 있다. 최대 높이가 7일 때 가장 불균형한 레드블랙 트리의 모습은 다음과 같다.

 

 최장 높이 경로에서 각각의 서브 루트에 매달린 완전 이진 트리의 높이에 유의하라. 해당 서브 루트부터 리브까지의 블랙 노드 개수는 모두 같아야 하기 때문에 위의 높이를 보인다. 높이가 하나 증가할 때마다 포화 이진트리가 하나와 루트 노드 하나가 증가되니 높이에 따른 최소 노드 개수는 다음과 같이 구할 수 있다.

$$N(h) = N(h-1) + 2^{((h-1)/2)}$$

 

파이썬으로 구현한 Red-Black 트리의 높이에 따른 최소 노드 개수를 출력하는 코드

 

두 트리의 비교

 각 높이에 따른 최소 노드 개수를 비교해보았다.

높이	AVL	Red-Black
1	1	1
2	2	2
3	4	4
4	7	6
5	12	10
6	20	14
7	33	22
8	54	30
9	88	46
10	143	62

 

 입력이 편향되었을 때, AVL트리가 같은 높이에서 레드블랙 트리보다 더 많은 노드를 담을 수 있다. 즉, 같은 노드를 더 작은 높이에서 담을 수 있다는 뜻이며 이는 AVL트리가 더 짧은 탐색시간을 가진다는 것이다. 같은 개수의 노드가 존재할 때 AVL트리에서의 탐색이 더 빠를 것이다.

 

 하지만 실제로 구현하여 운영해보면 알겠지만 AVL트리는 레드블랙 트리보다 많은 노드 재배치를 실행한다. 레드블랙 트리는 레드 노드가 연속해서 존재할 경우에만 노드 재배치를 실행하며 레드 노드의 네 가지 중복 경우 중 두 가지는 더 이상 루트를 향해 올라가지 않아도 된다. 반대로 AVL 트리는 단 2의 높이 차도 허락하지 않으며 비교적 빈번한 현재 노드 재배치와 부모로 올라가는 재배치를 요구한다. 이는 AVL트리가 레드블랙 트리보다 삽입과 삭제에 더 많은 시간을 소모하게 만든다. 

 

 더 직관적으로 설명하자면, 더 균등한 트리를 위해서는 반드시 더 많은 노드 재배치가 필연적으로 필요할 것이다. AVL 트리는 더 균등한 트리를 생성하므로 레드블랙 트리보다 더 많은 노드 재배치가 필요하다. 

 

 쓸데없이 들어간 감이 있지만, 다음과 같이 결론 내릴 수 있다.

• AVL트리는 비교적 빠른 탐색 시간을 갖지만 삽입과 삭제에 더 시간이 걸린다.
• 레드-블랙 트리는 비교적 빠른 삽입, 삭제를 할 수 있지만 탐색에 더 시간이 걸린다.

 

 그렇다면 어떤 트리를 언제 쓰는 것이 더 유리할까?

 

트리의 선택

 교과서적으로 접근하면 답은 간단하다. 삽입, 삭제가 적지만 탐색이 많을 경우 AVL트리를, 반대의 경우 레드블랙 트리를 선택하면 된다. 하지만 궁금하다. 그 차이가 어느 정도일까?

 

 높이 40에서 두 트리가 가장 불균형할 때 존재하는 모든 노드의 개수를 구하여 보았다. 재귀적으로 구현한 함수라 시간이 좀 걸렸지만 결과는 다음과 같다.

$$AVL_N(40) = 267914295$$

$$REDBLACK_N(40) = 2097150$$

 

 가장 불균형한 경우이기 때문에 두 트리의 노드 수가 극단적으로 차이나는 것을 볼 수 있다. 높이 40의 불균형한 레드블랙 트리의 노드 개수는 높이 30의 불균형한 AVL트리의 노드 개수와 거의 동일했다(2178308).

 

 만약 아주 많은 데이터를 아주 많이 탐색해야 하는 경우, 그리고 대부분의 데이터가 미리 저장되고 그 이후에 탐색을 하는 경우 AVL트리는 레드블랙 트리에 비해 훨씬 더 좋은 성능을 보장할 것이다. 데이터의 삽입과 삭제가 최소화되면 될 수록 사용자가 경험하는 분할상환시간이 적어질 것이다.

 

 반대로 데이터가 언제 들어올지 예측 불가능하고 그 수가 그렇게 극단적으로 많지 않은 경우 레드블랙 트리가 더 유리할 것이다. 예를 들어 어떤 학원에서 원생들의 정보를 트리에 저장하려고 한다고 상상해보자. 입소문이 나거나 광고를 하기 전까지 원생은 크게 늘어나지 않을 가능성이 높다. 반대로 학생들이나 엄마들 사이에 소문이 돌거나 대대적인 광고를 한 이후에는 원생들이 갑자기 많이 들어올지 모른다. 즉, 언제 얼마나 데이터가 입력될지 알 수 없다. 하지만 한 가지는 확실하다. 2억 명이 학원에 등록하려고 오지는 않을 것이라는 사실이다. 학원의 크기에 따라 다르겠지만 정말 많아봐야 몇 백명, 전국구에 있는 학원이라봐야 몇 천명 일 것이다. 게다가 학생들의 정보를 자주 열람할 이유도 없다. 오히려 학생들이 등록하고 해지하는 과정에서 정보의 삽입과 삭제가 더 빈번히 일어날 것이다. 이런 경우 많은 연산이 필요한 AVL트리를 사용할 이유가 없다.

 

마치며

 자료구조와 알고리즘 수업에 사용했던 교재에서는 두 트리를 비교하며 간단한 결론만 내리고는 했다. 하지만 구체적으로 데이터가 얼마나 많아야 AVL트리를 선택할 만큼 시간적 복잡도를 차이나게 하는지, 어느 정도의 데이터가 탐색시간의 차이를 감수하고라도 레드블랙 트리를 선택하게 하는지 알 수 없었다.

 

 기말고사가 끝난 이번 기회에 두 트리에 대한 더 깊은 이해를 할 수 있었다. 다음에는 B-트리나 B+트리도 한 번 다루어보고 싶다.

 

 아래는 레드블랙 트리를 구현해 사전의 단어들을 저장했던 과제의 소스코드다. 

GitHub - altair823/Data_Structure