AVL 트리와 Red-Black 트리 - 균형 이진 탐색 트리

• AVL 트리란 무엇인가?

 

AVL 트리(Adelson-Velsky and Landis Tree)는 자기 균형 이진 탐색 트리(Balanced Binary Search Tree)로, 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 인자, balance factor)가 1을 넘지 않도록 균형을 맞추는 트리입니다. 이 규칙을 통해 탐색, 삽입, 삭제 연산을 O(log N) 시간 복잡도로 수행할 수 있습니다. AVL 트리는 트리가 항상 균형을 이루고 있어, 성능이 매우 예측 가능합니다.

 

AVL 트리의 특징:

• • 균형 인자: 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이를 구하고, 그 차이가 1을 초과하지 않도록 유지합니다.
• • 자기 균형성: 삽입 또는 삭제 연산 후, 트리가 불균형해지면 회전(rotation) 연산을 통해 트리의 균형을 맞춥니다.
• • 회전: 불균형한 트리를 균형 상태로 만들기 위해 단일 회전 또는 이중 회전을 사용합니다.

 

AVL 트리에서의 회전 종류:

• • 단일 회전 (Single Rotation):
• • 왼쪽 회전: 왼쪽 서브트리가 더 높을 때.
• • 오른쪽 회전: 오른쪽 서브트리가 더 높을 때.
• • 이중 회전 (Double Rotation):
• • 왼쪽-오른쪽 회전: 왼쪽 자식의 오른쪽 서브트리가 높을 때.
• • 오른쪽-왼쪽 회전: 오른쪽 자식의 왼쪽 서브트리가 높을 때.

 

AVL 트리 예시:

        30
       /  \
     20    40
    /  \     \
  10    25    50

     

위 트리는 AVL 트리의 균형을 맞춘 상태를 보여줍니다.

 

• AVL 트리의 주요 연산

1. 탐색 (Search):

AVL 트리는 이진 탐색 트리이므로, 탐색 연산은 O(log N) 시간이 걸립니다. 탐색 시, 트리의 균형이 유지되기 때문에 항상 일정한 시간에 탐색을 완료할 수 있습니다.

2. 삽입 (Insert):

삽입 연산은 일반적인 이진 탐색 트리와 유사하지만, 삽입 후 트리가 불균형 상태가 되면 회전 연산을 통해 균형을 맞추어야 합니다. 삽입 후 균형을 맞추는 데 O(log N) 시간이 걸립니다.

3. 삭제 (Delete):

삭제 연산은 트리에서 특정 노드를 제거한 후, 해당 노드의 부모부터 다시 균형을 맞추는 과정이 필요합니다. 삭제 후 균형을 맞추는 데 O(log N) 시간이 걸립니다.

 

AVL 트리의 장점:

• • 균형이 항상 유지되어 **최악의 경우에도 O(log N)**의 시간 복잡도를 보장합니다.
• • 탐색, 삽입, 삭제가 빠르고 효율적입니다.

 

단점:

• • 삽입과 삭제 시 회전 연산이 필요하여 연산이 복잡하고, 구현이 어렵습니다.
• • 트리의 균형을 맞추는 추가적인 작업으로 인해 메모리 사용량이 늘어날 수 있습니다.

 

• Red-Black 트리란 무엇인가?

 

Red-Black 트리는 자기 균형 이진 탐색 트리로, 각 노드가 **두 가지 색(빨간색, 검은색)**을 가지며, 트리의 균형을 유지합니다. Red-Black 트리는 AVL 트리보다 간단한 구현과 빠른 성능을 제공합니다. 이 트리는 특정 규칙을 따르며 균형을 맞추기 때문에 삽입과 삭제가 더 빠르고 구현이 쉬운 장점이 있습니다.

 

Red-Black 트리의 규칙:

• • 루트 노드는 항상 검은색입니다.
• • 모든 리프 노드는 검은색입니다.
• • 빨간색 노드는 두 개의 빨간색 자식 노드를 가질 수 없습니다(즉, 빨간색 노드는 연속적으로 나올 수 없습니다).
• • 각 노드에서 루트까지의 경로에 있는 검은색 노드의 개수는 모두 동일해야 합니다(즉, 각 경로에서 검은색 노드의 수가 균일합니다).

 

Red-Black 트리의 예시:

        10(B)
       /     \
    5(R)     20(R)
              /   \
           15(B)  25(B)

   

• Red-Black 트리의 주요 연산

1. 탐색 (Search):

Red-Black 트리는 이진 탐색 트리의 특성을 그대로 가집니다. 따라서 O(log N) 시간에 탐색을 완료할 수 있습니다.

2. 삽입 (Insert):

삽입 후 트리의 균형을 맞추기 위해 회전 및 색 변경을 사용합니다. 이 연산은 O(log N) 시간이 걸리며, AVL 트리보다 구현이 간단합니다.

3. 삭제 (Delete):

삭제 후 트리의 균형을 맞추기 위해 노드 색상 변경과 회전을 사용합니다. 이 연산도 O(log N) 시간이 걸립니다.

 

Red-Black 트리의 장점:

• • 구현이 간단하고 메모리 사용이 적습니다.
• • 삽입 및 삭제 시 회전 연산이 적고, 트리의 균형을 맞추는 데 필요한 작업이 적어서 성능이 빠릅니다.
• • 트리가 균형을 유지하며, 탐색 연산이 항상 O(log N) 시간에 이루어집니다.

 

단점:

• • 세그먼트 트리처럼 균형이 완벽히 유지되는 것은 아니므로, 최악의 경우 성능이 AVL 트리보다는 다소 낮을 수 있습니다.

 

• AVL 트리 vs Red-Black 트리

특징	AVL 트리	Red-Black 트리
구조	트리 기반	트리 기반
탐색 시간	O(log N)	O(log N)
삽입 시간	O(log N) (회전 필요)	O(log N) (회전 필요)
삭제 시간	O(log N) (회전 필요)	O(log N) (회전 필요)
회전 연산	자주 필요	덜 필요
구현 난이도	상대적으로 복잡	상대적으로 간단
성능	균형이 엄격하게 유지됨	성능이 빠르고 구현이 간단
메모리 사용	O(N)	O(N)

 

결론:

• • AVL 트리는 균형을 엄격하게 유지하므로 최악의 경우에도 O(log N) 시간 복잡도를 보장합니다. 하지만 구현이 복잡하고, 삽입과 삭제에서 회전 연산이 많습니다.
• • Red-Black 트리는 구현이 간단하고, 성능이 빠르며 메모리 사용도 효율적입니다. 그러나 균형이 완벽하지 않기 때문에 AVL 트리보다는 다소 느릴 수 있습니다.