AVL Tree와 Red-Black Tree는 모두 이진 탐색 트리의 높이를 O(log n)으로 유지하기 위한 균형 트리입니다. 일반 BST는 정렬된 값이 순서대로 들어오면 linked list처럼 한쪽으로 치우칠 수 있고, 이때 탐색·삽입·삭제가 O(n)이 됩니다.
AVL Tree는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이를 최대 1로 유지합니다. Red-Black Tree는 노드에 red/black 색을 두고 red가 연속되지 않으며 모든 root-to-leaf 경로의 black 노드 수가 같다는 규칙으로 높이를 제한합니다. AVL은 조회에 유리한 편이고, Red-Black Tree는 삽입·삭제가 잦은 상황에서 많이 쓰입니다.
두 트리의 차이는 "균형을 얼마나 엄격하게 지킬 것인가"라는 트레이드오프로 요약됩니다. 균형이 엄격할수록 트리가 낮아져 조회는 빨라지지만, 그 균형을 유지하느라 삽입·삭제 때 손봐야 할 것이 많아집니다.
수치로 보면 AVL의 높이는 최악에도 약 1.44·log₂n 이하, Red-Black Tree는 2·log₂(n+1) 이하로 보장됩니다. 둘 다 O(log n)이지만 AVL이 더 낮게 유지됩니다. 대신 Red-Black Tree는 균형 조건이 느슨한 만큼 수정 후 복구 작업이 가벼워, 읽기와 쓰기가 섞인 범용 상황에서 표준 라이브러리들의 선택이 되었습니다.
꼬리질문
조금 더 깊게 물어본다면
답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.
AVL Tree의 balance factor는 무엇인가요?
각 노드에서 왼쪽 서브트리 높이와 오른쪽 서브트리 높이의 차이입니다.
balance factor = left height - right height
AVL에서는 이 값이 -1, 0, +1 안에 있어야 합니다. +2나 -2가 되면 회전으로 균형을 복구합니다.
허용 범위가 0이 아니라 ±1인 데에는 이유가 있습니다. 모든 노드에서 높이 차이가 정확히 0인 완전 균형을 요구하면, 노드 수가 특정 형태일 때만 성립할 수 있고 삽입 하나마다 트리 전체를 재구성해야 할 수 있습니다. ±1은 "조회 성능은 사실상 완전 균형과 같으면서, 국소적인 회전만으로 유지 가능한" 가장 엄격한 조건입니다.
구현 측면에서는 각 노드에 서브트리 높이(또는 balance factor)를 저장해 두고, 삽입·삭제 후 root 방향으로 올라가며 갱신합니다. 매번 높이를 새로 계산하면 O(n)이 되므로, 저장해 둔 값을 경로 위에서만 갱신하는 것이 O(log n) 유지의 핵심입니다.
AVL Tree의 회전은 왜 BST 규칙을 깨지 않나요?
회전은 노드들의 상대적인 정렬 순서를 유지하면서 부모-자식 관계만 바꾸는 작업입니다. 예를 들어 1, 2, 3이 오른쪽으로 기울어져 있어도, 왼쪽 회전 후에는 2가 root가 되고 1 < 2 < 3 순서는 그대로 유지됩니다.
즉 회전은 “정렬 순서 변경”이 아니라 “높이를 줄이기 위한 구조 변경”입니다.
회전이 순서를 보존하는 이유는 inorder 순회 결과가 불변이기 때문입니다. 왼쪽 회전에서 자리가 바뀌는 것은 부모-자식 관계와 가운데 서브트리(새 root의 원래 왼쪽 자식)의 소속뿐인데, 그 서브트리는 "두 노드 사이 값"이라는 위치가 회전 전후로 동일합니다. 포인터 두세 개만 바꾸면 되므로 회전 한 번은 O(1)입니다.
회전에 네 케이스(LL, RR, LR, RL)가 있는 이유는 기울어진 방향의 조합 때문입니다. 같은 방향으로 두 번 기울면(LL, RR) 회전 한 번으로 끝나지만, 지그재그로 기울면(LR, RL) 한 번의 회전으로는 기울기가 반대쪽으로 옮겨갈 뿐이라, 먼저 아래쪽을 회전해 같은 방향 케이스로 만든 뒤 다시 회전하는 이중 회전이 필요합니다.
Red-Black Tree에서 red 노드가 연속되면 왜 안 되나요?
Red가 연속될 수 있으면 특정 경로에 red 노드를 계속 끼워 넣어 길이를 크게 늘릴 수 있습니다. Red 노드의 자식을 black으로 제한하면 경로 길이가 black 노드 수에 의해 간접적으로 제한됩니다.
이 규칙과 black height 규칙이 함께 작동해서 전체 높이가 O(log n) 안에 머물도록 만듭니다.
두 규칙이 높이를 제한하는 논리를 이어 보면, 어떤 노드에서 leaf까지 가장 짧은 경로는 전부 black일 때이고, 가장 긴 경로는 black과 red가 번갈아 나올 때입니다. 모든 경로의 black 수가 같으므로(black height 규칙) 가장 긴 경로도 black 수는 최단 경로와 같고, 그 사이에 red를 끼워 넣을 수 있는 최대치는 black 하나당 red 하나입니다.
따라서 최장 경로는 최단 경로의 2배를 넘을 수 없습니다. 최단 경로가 log₂n 수준이므로 전체 높이는 2·log₂(n+1) 이하로 묶입니다. AVL의 ±1처럼 정밀하지는 않지만, "가장 긴 쪽이 가장 짧은 쪽의 2배 이내"라는 느슨한 균형만으로도 O(log n)을 보장하기에 충분합니다.
AVL Tree와 Red-Black Tree는 언제 각각 유리한가요?
AVL은 균형 조건이 더 엄격해서 트리 높이가 더 낮은 편입니다. 그래서 조회가 매우 많은 상황에서 유리할 수 있습니다.
Red-Black Tree는 균형 조건이 더 느슨해서 삽입·삭제 때 조정 비용이 상대적으로 적은 편입니다. 그래서 Java의 TreeMap, C++의 map/set처럼 범용 ordered map/set 구현에 자주 연결됩니다.
수정 비용 차이가 가장 크게 벌어지는 것은 삭제입니다. Red-Black Tree는 삭제 후 복구에 필요한 회전이 최대 3회로 상수인 반면, AVL은 삭제 하나가 root까지 올라가며 경로 위 여러 노드의 균형을 연쇄적으로 깨뜨릴 수 있어 회전이 O(log n)번 필요할 수 있습니다. 색 변경은 회전과 달리 포인터를 건드리지 않는 값싼 연산이라, Red-Black Tree의 복구는 대부분 색 변경으로 처리됩니다.
실제 채택 사례를 보면 Red-Black Tree는 Java TreeMap, C++ map/set 외에 Linux 커널에서도 프로세스 스케줄러(CFS)의 실행 대기열, 프로세스의 가상 메모리 영역 관리 등에 널리 쓰입니다. 커널처럼 삽입·삭제가 끊임없이 일어나는 곳에서 수정 비용의 상수 보장이 중요하기 때문입니다.
둘 다 시간복잡도는 어떻게 되나요?
둘 다 균형을 유지하므로 탐색, 삽입, 삭제가 O(log n)입니다. 차이는 Big-O보다 상수 비용, 회전 빈도, 구현 복잡도 쪽에 가깝습니다.
AVL은 더 엄격하게 균형을 맞추고, Red-Black Tree는 약간 느슨한 균형으로 실용적인 수정 비용을 노립니다.
"둘 다 O(log n)"이라는 답에서 멈추지 않고 상수를 비교하면 차이가 보입니다. 높이 상한이 AVL은 약 1.44·log₂n, Red-Black Tree는 2·log₂(n+1)이므로, 같은 데이터에서 조회 시 비교 횟수는 AVL이 더 적을 수 있습니다. 반대로 수정 시 조정 비용은 Red-Black Tree가 더 작습니다.
그래서 선택 기준은 "조회와 수정의 비율"이 됩니다. 한 번 만들어 놓고 조회만 반복하는 조회 위주 워크로드라면 AVL의 낮은 높이가 이득이고, 삽입·삭제가 계속 섞이는 워크로드라면 Red-Black Tree의 싼 수정이 이득입니다. 범용 라이브러리는 워크로드를 예측할 수 없으니 수정 비용이 안정적인 Red-Black Tree를 기본값으로 택한 것입니다.
부가 설명
BST의 장점은 현재 노드와 비교해서 왼쪽 또는 오른쪽 중 한 방향만 보면 된다는 점입니다. 하지만 이 장점은 트리 높이가 낮을 때만 유지됩니다.
1 \ 2 \ 3 \ 4
이렇게 한쪽으로 기울면 높이가 n에 가까워지고, 탐색도 결국 하나씩 따라가는 형태가 됩니다. AVL과 Red-Black Tree는 삽입·삭제 후 균형이 깨지면 rotation을 통해 BST의 정렬 규칙은 유지하면서 모양을 바꿉니다.
AVL은 balance factor를 봅니다.
balance factor = left subtree height - right subtree height허용 값: -1, 0, +1
이 범위를 벗어나면 LL, RR, LR, RL 같은 케이스에 따라 회전합니다. 조건이 엄격한 만큼 트리가 더 낮게 유지되는 편입니다.
Red-Black Tree는 색깔 규칙을 봅니다.
1. 모든 노드는 red 또는 black2. root는 black3. red 노드의 자식은 black4. 모든 NIL leaf는 black5. 어떤 노드에서 leaf까지 가는 모든 경로의 black 노드 수는 동일
이 규칙 때문에 red가 무한히 연속될 수 없고, 한쪽 경로만 과하게 길어지는 것도 제한됩니다. 균형은 AVL보다 느슨하지만 삽입·삭제 때 필요한 조정이 상대적으로 적은 편입니다.
한 줄 정리
AVL은 높이 차이를 엄격히 관리하는 균형 BST이고, Red-Black Tree는 색깔 규칙으로 O(log n) 높이를 유지하는 조금 더 느슨한 균형 BST입니다.