이진 탐색 트리

 

트리는 그래프 이론에서 특별한 종류의 자료 구조로, 다음과 같은 특성을 가집니다:

트리의 정의 및 특성

1. 트리 구조:
  ⦁ 루트 노드: 트리는 하나의 시작점인 루트 노드를 가집니다. 루트 노드는 트리의 최상위 노드입니다.
  ⦁ 자식 노드: 루트 노드를 제외한 모든 노드는 부모 노드와 연결되며, 각 노드는 자식 노드를 가질 수 있습니다.
  ⦁ 부모-자식 관계: 트리에서 노드 간의 관계는 부모-자식 관계로 나타내며, 부모 노드는 자식 노드를 향해 연결됩니다.
  ⦁ 순환 없음: 트리는 순환(cycle)이 없는 연결 그래프입니다. 즉, 어떤 노드에서 시작하여 다시 그 노드로 돌아오는 경로가

                       존재하지 않습니다.

2. 트리의 특성:
  ⦁ 연결성: 트리의 모든 노드는 하나의 경로로 연결되어 있습니다. 즉, 임의의 두 노드 간에는 정확히 하나의 경로가 존재합니다.
  ⦁ 계층 구조: 트리는 계층적인 구조를 가지며, 루트 노드에서 시작하여 레벨이 점차 깊어집니다.
  ⦁ 서브트리: 트리의 각 노드는 그 자식 노드와 연결된 서브트리를 형성합니다. 이 서브트리들도 각각 하나의 트리로 간주됩니다.

트리의 예시

크기가 9이고, 높이가 3인 이진 트리

⦁  루트 노드(root node): 2
⦁  자식 노드(child node): 7, 5 (루트 노드 2의 자식 노드)
⦁  부모(parent)-자식(child) 관계: 2는 7와 5의 부모, 7는 2와 6의 부모, 5는 9의 부모
⦁  자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드): 5, 11, 4

트리의 종류
⦁  이진 트리: 각 노드가 최대 두 개의 자식 노드를 가지는 트리
⦁  완전 이진 트리: 모든 레벨이 가득 채워져 있고 마지막 레벨은 왼쪽부터 채워진 이진 트리
⦁  이진 탐색 트리: 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 이진 트리
⦁  균형 이진 트리: 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 이진 트리 (예: AVL 트리, 레드-블랙 트리)

트리는 순환이 없는 연결 그래프이며, 루트 노드에서 시작하여 부모-자식 관계를 통해 계층적인 구조를 형성합니다. 모든 노드는 유일한 경로로 연결되어 있고, 이러한 특성 덕분에 다양한 알고리즘과 데이터 구조에서 효율적으로 사용됩니다.

 

Binary Search Tree

컴퓨터 과학에서 이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다

 

이진 트리가 데이터를 빠르게 검색할 수 있는 이유는 그 구조적인 특성 때문입니다. 이진 검색 트리(BST, Binary Search Tree)의 예를 통해 설명하겠습니다.

 

이진 탐색 트리의 구조

이진 검색 트리는 다음과 같은 규칙을 따릅니다:
1. 각 노드에는 하나의 키와 두 개의 자식 노드(왼쪽, 오른쪽)가 있습니다.
2. 왼쪽 자식 노드의 모든 키는 부모 노드의 키보다 작습니다.
3. 오른쪽 자식 노드의 모든 키는 부모 노드의 키보다 큽니다.

이러한 구조로 인해 특정 값을 검색할 때 효율적으로 트리를 탐색할 수 있습니다.

이진 검색 트리에서 검색 과정
검색 과정은 다음과 같습니다:
1. 루트 노드부터 시작:
    ⦁  찾고자 하는 값이 현재 노드의 값과 같은지 비교합니다.
    ⦁  같으면, 값을 찾았으므로 검색을 종료합니다.
    
2. 비교 및 이동:
    ⦁  찾고자 하는 값이 현재 노드의 값보다 작으면, 왼쪽 자식 노드로 이동합니다.
    ⦁  찾고자 하는 값이 현재 노드의 값보다 크면, 오른쪽 자식 노드로 이동합니다.
    
3. 반복:
    ⦁  이동한 노드를 새로운 현재 노드로 삼고, 1번 과정부터 반복합니다.
    ⦁  만약 자식 노드가 없다면, 찾고자 하는 값이 트리에 없다는 것을 의미합니다.

 

배열을 이진 탐색 트리로 변환

이진 탐색 알고리즘이란 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나입니다

이진 탐색 트리는 루트 노드를 중간 값으로 선택하여 이진 탐색 트리를 만드는 균형 잡힌 이진 탐색 트리(Balanced Binary Search Tree, BBST)를 구성하는 알고리즘 중 하나입니다. 이는 주로 분할 정복(Divide and Conquer) 기법을 사용합니다. 이 알고리즘은 다음과 같은 단계를 따릅니다:

1. 배열 정렬: 먼저 주어진 배열을 오름차순으로 정렬합니다.
2. 중간 값 선택: 정렬된 배열의 중간 값을 선택하여 루트 노드로 설정합니다.
3. 재귀적 서브트리 구성: 배열을 중간 값 기준으로 좌우 두 부분으로 나누고, 각각의 부분에 대해 재귀적으로 같은 과정을 반복하여 서브트리를 구성합니다.

이 알고리즘은 배열을 분할 정복 방식으로 처리하여 균형 잡힌 이진 탐색 트리를 구성합니다. 이렇게 하면 트리의 높이가 최소화되어, 탐색, 삽입, 삭제 등의 연산에서 시간 복잡도가 O(log n)이 됩니다.

 

정렬되지 않은 배열을 정렬한 후에 이진 탐색 트리를 만드는 과정을 단계별로 설명하겠습니다.

 

예시 배열: [3, -1, 4, 6, 9, -2, 5, 7]

1. 배열 정렬
우선 배열을 오름차순으로 정렬합니다:

[-2, -1, 3, 4, 5, 6, 7, 9]

2. 중간 값 선택 및 트리 구성
정렬된 배열의 중간 값을 선택하여 트리의 루트 노드로 설정하고, 이를 기준으로 왼쪽과 오른쪽 서브트리를 구성합니다.

단계별 트리 변환
1. 중간 값 선택
  ⦁ 중간 값 5를 루트로 설정합니다.

       5

---

중간값

중간값이 왜 5인지 설명을 드리겠습니다. 주어진 배열을 정렬한 후 중간값을 선택하는 이유는 배열을 균등하게 나누어 균형 잡힌 이진 탐색 트리를 만들기 위해서입니다.

배열: [3, -1, 4, 6, 9, -2, 5, 7]

1. 배열 정렬
우선 주어진 배열을 오름차순으로 정렬합니다:

[-2, -1, 3, 4, 5, 6, 7, 9]

 2. 중간값 선택
정렬된 배열의 중간값을 선택합니다. 배열의 길이가 짝수인 경우, 중앙에 가장 가까운 값을 선택합니다.

정렬된 배열의 사이즈

배열 사이즈 = 8 (짝수)

중간값 인덱스 계산
중간값의 인덱스는 배열 사이즈 ÷ 2입니다.

중간값 인덱스 = 8 ÷ 2 = 4

따라서 정렬된 배열에서 인덱스 4에 해당하는 값은 5입니다.

정렬된 배열: [-2, -1, 3, 4, 5, 6, 7, 9]
중간값: 5 (인덱스 4)

왜 중간값을 선택하는가?
중간값을 루트로 선택하면, 배열을 좌우 두 부분으로 나누어 균형 잡힌 이진 탐색 트리를 구성할 수 있습니다. 이 방식은 트리의 높이를 최소화하여, 트리의 연산 (탐색, 삽입, 삭제 등)의 시간 복잡도를 최적화하는데 유리합니다.

전체 과정 요약
1. 배열 정렬:
  ⦁ 주어진 배열 [3, -1, 4, 6, 9, -2, 5, 7]을 오름차순으로 정렬하여 [-2, -1, 3, 4, 5, 6, 7, 9]로 만듭니다.
2. 중간값 선택:
  ⦁ 정렬된 배열의 중간값 5를 루트로 설정합니다.
  ⦁ 배열을 두 부분으로 나눕니다.
    ⦁ 왼쪽 서브트리 배열: [-2, -1, 3, 4]
    ⦁ 오른쪽 서브트리 배열: [6, 7, 9]
3. 재귀적으로 서브트리 구성:
  ⦁ 왼쪽 서브트리와 오른쪽 서브트리 각각에 대해 중간값을 선택하여 재귀적으로 트리를 구성합니다.

결과적으로, 중간값을 선택하는 이유는 트리의 균형을 유지하여 연산의 효율성을 높이기 위함입니다. 이 방법을 통해 트리의 높이를 최소화하고, 각 노드에서의 연산이 빠르게 이루어질 수 있습니다.

---

 

2. 왼쪽 서브트리 구성
  ⦁ 왼쪽 서브트리 배열: [-2, -1, 3, 4]
  ⦁ 중간 값 -1을 선택하여 5의 왼쪽 자식으로 설정합니다.

       5
      /
    -1

3. 오른쪽 서브트리 구성
  ⦁ 오른쪽 서브트리 배열: [6, 7, 9]
  ⦁ 중간 값 7을 선택하여 5의 오른쪽 자식으로 설정합니다.

       5
      / \
    -1   7

4. 왼쪽 서브트리의 서브트리 구성
  ⦁ 배열 [-2, -1, 3, 4]에서 중간 값 -1의 왼쪽 서브트리: [-2], 오른쪽 서브트리: [3, 4]
  ⦁ -2를 -1의 왼쪽 자식으로 설정, 3을 -1의 오른쪽 자식으로 설정합니다.

       5
      / \
    -1   7
    / \
  -2   3

5. 오른쪽 서브트리의 서브트리 구성
  ⦁ 배열 [6, 7, 9]에서 중간 값 7의 왼쪽 서브트리: [6], 오른쪽 서브트리: [9]
  ⦁ 6을 7의 왼쪽 자식으로 설정, 9를 7의 오른쪽 자식으로 설정합니다.

       5
      / \
    -1   7
    / \  / \
  -2   3 6  9

6. 왼쪽 서브트리의 오른쪽 서브트리 구성
  ⦁ 배열 [3, 4]에서 중간 값 3의 오른쪽 서브트리: [4]
  ⦁ 4를 3의 오른쪽 자식으로 설정합니다.

       5
      / \
    -1   7
    / \  / \
  -2   3 6  9
        \
         4

최종 트리 구조
정렬된 배열을 이용해 중간 값을 선택하여 이진 탐색 트리로 변환한 결과:

       5
      / \
    -1   7
    / \  / \
  -2   3 6  9
        \
         4

정리
1. 배열 정렬:
  ⦁ 주어진 배열 [3, -1, 4, 6, 9, -2, 5, 7]을 오름차순으로 정렬하여 [-2, -1, 3, 4, 5, 6, 7, 9]로 만듭니다.
2. 중간 값 선택:
  ⦁ 정렬된 배열의 중간 값 5를 루트로 설정하고, 왼쪽과 오른쪽 서브트리를 재귀적으로 구성합니다.
3. 서브트리 구성:
  ⦁ 각 서브트리에서 중간 값을 선택하여 노드를 설정하고, 이를 재귀적으로 반복하여 전체 트리를 구성합니다.

이 과정을 통해 정렬되지 않은 배열을 정렬한 후, 이진 탐색 트리를 구성할 수 있습니다. 이 트리는 중간 값을 루트로 선택하여 균형 잡힌 형태로 구성됩니다.

 

 

주어진 예시의 이진 탐색 트리에서 값 -2를 탐색하는 과정을 단계별로 설명하겠습니다.
정렬된 배열과 이진 탐색 트리
⦁  정렬된 배열: [-2, -1, 3, 4, 5, 6, 7, 9]
⦁  중간값 5를 루트로 설정하여 만든 이진 탐색 트리:

       5
      / \
     3   7
    / \  / \
  -1   4 6  9
  /
-2

 

-2를 탐색하는 과정
1. 루트 노드에서 시작:
  ⦁ 현재 노드: 5
  ⦁ 찾으려는 값 -2는 현재 노드 값 5보다 작습니다.
  ⦁ 따라서 왼쪽 서브트리로 이동합니다.

현재 노드: 5
       5
      / \
     3   7
    / \  / \
  -1   4 6  9
  /
-2
-2는 5보다 작으므로 왼쪽 자식 노드로 이동

2. 왼쪽 자식 노드:
  ⦁ 현재 노드: 3
  ⦁ 찾으려는 값 -2는 현재 노드 값 3보다 작습니다.
  ⦁ 따라서 왼쪽 서브트리로 이동합니다.

현재 노드: 3
       5
      / \
     3   7
    / \  / \
  -1   4 6  9
  /
-2
-2는 3보다 작으므로 왼쪽 자식 노드로 이동

3. 왼쪽 자식 노드:
  ⦁ 현재 노드: -1
  ⦁ 찾으려는 값 -2는 현재 노드 값 -1보다 작습니다.
  ⦁ 따라서 왼쪽 서브트리로 이동합니다.

현재 노드: -1
       5
      / \
     3   7
    / \  / \
  -1   4 6  9
  /
-2
-2는 -1보다 작으므로 왼쪽 자식 노드로 이동

4. 왼쪽 자식 노드:
  ⦁ 현재 노드: -2
  ⦁ 찾으려는 값 -2는 현재 노드 값 -2와 같습니다.
  ⦁ 값을 찾았습니다.

현재 노드: -2
       5
      / \
     3   7
    / \  / \
  -1   4 6  9
  /
-2
-2를 찾았습니다.

탐색 과정 요약
1. 루트 노드 5에서 시작:
  ⦁ -2는 5보다 작으므로 왼쪽 자식 노드로 이동합니다.
2. 노드 3:
  ⦁ -2는 3보다 작으므로 왼쪽 자식 노드로 이동합니다.
3. 노드 -1:
  ⦁ -2는 -1보다 작으므로 왼쪽 자식 노드로 이동합니다.
4. 노드 -2:
  ⦁ -2를 찾았습니다.

이와 같이, 이진 탐색 트리에서 특정 값을 찾는 과정은 현재 노드의 값과 찾으려는 값을 비교하여 왼쪽 또는 오른쪽 서브트리로 이동하면서 이루어집니다. 최종적으로 값을 찾으면 탐색이 완료됩니다.

 

 

Skewed Tree

편향된 트리는 한쪽으로 치우쳐 성장하는 이진 트리입니다. 이러한 트리는 한쪽 자식 노드만을 계속 추가하여 만들어집니다. 두 가지 주요 형태는 왼쪽 편향된 트리와 오른쪽 편향된 트리입니다. 각각의 예시는 다음과 같습니다.

왼쪽 편향된 트리 (Left-Skewed Tree)

    1
   /
  2
 /
3
/
4

오른쪽 편향된 트리 (Right-Skewed Tree)

1
 \
  2
   \
    3
     \
      4

이와 같이 편향된 트리는 트리의 깊이가 n인 반면, 균형 잡힌 트리의 경우 깊이는 log(n) 정도가 됩니다. 이는 탐색이나 삽입, 삭제 등의 연산에서 비효율성을 초래할 수 있습니다.

 

편향된 트리의 탐색이 최악이 되는 이유는 다음과 같습니다:

트리의 깊이와 탐색 시간

1. 트리의 깊이: 
  ⦁ 균형 잡힌 이진 트리는 각 노드가 최대 두 개의 자식을 가지며, 각 레벨에 노드가 고르게 분포됩니다. 이 경우 트리의 높이는 log(n)입니다.
  ⦁ 편향된 트리는 한쪽으로만 계속 자식 노드가 추가되어 깊이가 n이 됩니다.

탐색 과정 비교

균형 잡힌 트리
⦁  탐색 시간: O(log n)
⦁  예시: 5를 찾는다고 가정합니다

      4
     / \
    2   6
   / \ / \
  1  3 5  7

 ⦁  원하는 값을 찾기 위해 최악의 경우 3단계(log(7) ≈ 3)만에 찾을 수 있습니다.

4 -> 6 -> 5

 

 

시간 복잡도 B(O)

• 이진 탐색 트리에서의 탐색 시간 복잡도는 트리의 높이에 비례합니다.
• 주어진 트리는 균형 잡힌 이진 탐색 트리로, 높이는 log⁡2(n)입니다.
• 주어진 트리의 노드 수 n은 7입니다.
• 따라서 트리의 높이는 log⁡2(7)≈3입니다.

탐색 과정에서 3개의 노드를 방문했으므로, 이진 탐색 트리에서의 탐색 시간 복잡도는 O(log⁡n)입니다.

편향된 트리
 ⦁ 탐색 시간: O(n)
 예시 (오른쪽 편향된 트리): 6를 찾는다고 가정합니다.

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

  ⦁ 원하는 값을 찾기 위해 최악의 경우 모든 노드를 순차적으로 탐색해야 합니다. 즉, 6를 찾기 위해 6단계를 거쳐야 합니다.

탐색 경로

1 -> 2 -> 3 -> 4 -> 5 -> 6

 

시간 복잡도 B(O)
⦁  주어진 트리는 편향된 이진 트리로, 각 노드마다 하나의 자식 노드만 가지므로 이 트리는 선형 구조를 가집니다.
⦁  이 경우, 트리의 높이는 노드 수와 동일합니다. 즉, 주어진 트리의 높이는 n = 7입니다.
⦁  따라서 이진 탐색 트리에서 최악의 경우 시간 복잡도는 트리의 높이에 비례하여 O(n)이 됩니다.

 

주어진 편향된 이진 트리에서 값 6을 찾기 위한 시간 복잡도는 O(n)이며, 여기서 n = 7이므로 시간 복잡도는 O(n)로 표현됩니다.

비효율성의 원인
1. 탐색 경로의 길이:
  ⦁ 균형 잡힌 트리에서는 탐색 경로가 짧아 효율적입니다.
  ⦁ 편향된 트리에서는 탐색 경로가 길어 비효율적입니다.

2. 재귀 호출/반복문 횟수:
  ⦁ 균형 잡힌 트리는 적은 재귀 호출/반복문으로 탐색을 완료할 수 있습니다.
  ⦁ 편향된 트리는 많은 재귀 호출/반복문이 필요합니다.

편향된 트리에서는 모든 노드를 순차적으로 탐색해야 할 수 있어 최악의 경우 시간 복잡도가 O(n)이 됩니다. 반면 균형 잡힌 트리는 탐색 경로가 짧아 최악의 경우에도 시간 복잡도가 O(log n)이므로 효율적입니다. 이 때문에 편향된 트리는 탐색, 삽입, 삭제 등의 연산에서 비효율적이 됩니다.

 

Red-Black Tree

레드-블랙 트리는 이진 검색 트리의 일종으로, 자가 균형을 유지하여 삽입, 삭제, 검색 연산에서 최악의 경우에도 O(log n)의 시간 복잡도를 보장합니다. 레드-블랙 트리의 각 노드는 레드 또는 블랙 색상을 가지며, 몇 가지 균형 조건을 만족합니다.

 

레드-블랙 트리의 주요 속성

1. 각 노드는 레드 또는 블랙입니다.
2. 루트 노드는 항상 블랙입니다.
3. 모든 리프(nil 노드)는 블랙입니다.
4. 레드 노드의 자식은 항상 블랙입니다. (즉, 레드 노드가 연속으로 나타나지 않습니다.)
5. 어떤 노드에서든 그 노드로부터 리프 노드까지 가는 모든 경로에는 동일한 개수의 블랙 노드가 있습니다.

 

레드-블랙 트리에서 노드를 레드(Red)와 블랙(Black)으로 설정하는 이유는 트리의 균형을 유지하여 연산의 효율성을 높이기 위해서입니다. 레드-블랙 트리는 이진 탐색 트리의 일종으로, 특정한 규칙을 통해 트리의 높이를 제한하고, 탐색, 삽입, 삭제 등의 연산에서 시간 복잡도를 O(log n)으로 유지할 수 있습니다.

이유 및 목적

1. 트리의 균형 유지:
  ⦁ 레드-블랙 트리의 규칙을 통해 트리가 한쪽으로 치우치지 않도록 균형을 유지합니다. 트리가 균형을 잃지 않으면, 탐색, 삽입, 삭제 연산에서 최악의 경우에도 O(log n)의 시간 복잡도를 보장할 수 있습니다.

2. 높이 제한:
  ⦁ 레드-블랙 트리는 특정 규칙을 통해 트리의 최대 높이가 제한됩니다. 정확히 말하면, 레드-블랙 트리의 높이는 가장 짧은 경로의 두 배를 넘지 않습니다. 이는 트리의 깊이가 log(n)에 비례하도록 유지하는 데 기여합니다.

3. 자기 균형 유지:
  ⦁ 레드-블랙 트리는 삽입 및 삭제 연산 후에 트리의 균형이 깨질 경우, 회전 및 색상 변경을 통해 자동으로 균형을 맞춥니다. 이는 트리의 효율성을 유지하는 데 중요한 역할을 합니다.

레드-블랙 트리의 규칙

레드-블랙 트리는 다음과 같은 규칙을 통해 균형을 유지합니다:
1. 노드 색깔: 각 노드는 빨강 또는 검정 중 하나의 색깔을 가집니다.
2. 루트 노드 색깔: 루트 노드는 항상 검정색입니다.
3. 레드 규칙: 빨강 노드의 자식 노드는 항상 검정색입니다. 즉, 빨강 노드가 연속해서 나타날 수 없습니다.
4. 블랙 규칙: 루트에서 모든 리프 노드(NIL 노드)까지의 경로에는 같은 수의 검정 노드가 있어야 합니다.
5. 리프 노드: 모든 리프 노드는 검정색입니다. 리프 노드는 실제 데이터가 아닌 NULL 노드를 의미합니다.

삽입 및 삭제 후 트리의 재조정

레드-블랙 트리에서는 삽입과 삭제 연산 후, 트리의 규칙을 위반할 수 있습니다. 이 경우 트리의 균형을 유지하기 위해 노드의 색상을 변경하거나 트리를 회전하는 추가 작업이 필요합니다.

삽입 과정
1. 새 노드 삽입: 새 노드는 항상 빨강색으로 삽입됩니다. 이는 새 노드가 삽입될 때 트리의 블랙 높이(루트에서 리프까지의 검정 노드 수)를 유지하기 위함입니다.
2. 레드 규칙 위반 확인: 삽입된 노드의 부모 노드가 빨강색일 경우, 레드 규칙이 깨지므로 트리 재조정이 필요합니다.
3. 트리 재조정: 삽입된 노드의 삼촌 노드의 색깔에 따라 회전 및 색상 변경을 수행하여 균형을 맞춥니다.

삭제 과정
1. 노드 삭제: 삭제된 노드가 검정색일 경우, 블랙 규칙이 깨질 수 있으므로 트리 재조정이 필요합니다.
2. 트리 재조정: 삭제된 노드의 형제 노드의 색깔 및 형제의 자식 노드의 색깔에 따라 회전 및 색상 변경을 수행하여 균형을 맞춥니다.

회전 연산
레드-블랙 트리에서는 균형을 맞추기 위해 회전 연산을 사용합니다. 회전에는 두 가지 유형이 있습니다:
1. 좌회전(Left Rotation):
  ⦁ 특정 노드를 중심으로 오른쪽 자식 노드를 부모로, 부모 노드를 왼쪽 자식으로 변경합니다.

2. 우회전(Right Rotation):
  ⦁ 특정 노드를 중심으로 왼쪽 자식 노드를 부모로, 부모 노드를 오른쪽 자식으로 변경합니다.

레드-블랙 트리에서 노드를 레드와 블랙으로 설정하는 이유는 트리의 균형을 유지하고, 최악의 경우에도 효율적인 연산을 보장하기 위함입니다. 이를 통해 탐색, 삽입, 삭제 등의 연산에서 일관된 O(log n)의 시간 복잡도를 유지할 수 있습니다. 레드-블랙 트리는 데이터베이스, 파일 시스템 등 다양한 분야에서 널리 사용되는 중요한 자료 구조입니다.

 

레드-블랙 트리 삽입

레드-블랙 트리의 루트 노드는 기본적으로 삽입하는 첫 번째 노드로 시작됩니다. 삽입 후, 레드-블랙 트리의 규칙을 유지하기 위해 필요한 조정 작업이 수행됩니다. 이를 통해 트리의 균형을 유지하고, 루트 노드는 항상 검정색이 됩니다.

레드-블랙 트리의 삽입 및 루트 노드 선택 과정
1. 첫 번째 노드 삽입:
  ⦁ 트리가 비어 있는 경우, 첫 번째로 삽입되는 노드는 루트 노드가 됩니다.
  ⦁ 첫 번째 노드는 처음에는 빨강색으로 삽입됩니다. 그러나 루트 노드는 항상 검정색이어야 하므로, 삽입 후 이 노드의 색을 검정색으로 변경합니다.

2. 추가 노드 삽입:
  ⦁ 새로운 노드는 항상 빨강색으로 삽입됩니다.
  ⦁ 삽입된 노드가 레드-블랙 트리의 규칙을 위반하는 경우, 회전 및 색상 변경을 통해 트리의 균형을 맞춥니다.
  ⦁ 루트 노드는 항상 검정색으로 유지됩니다.

예시

초기 상태
⦁  배열: [10]
⦁  트리가 비어있으므로 첫 번째 노드 `10`이 루트 노드가 됩니다.

    10R (빨강색으로 삽입됨)

⦁  루트 노드는 검정색이어야 하므로, `10`을 검정색으로 변경합니다.

    10B (검정색으로 변경됨)

 

추가 노드 삽입
⦁  배열: [10, 20]
⦁  20을 삽입합니다.

10B
    \
     20R (빨강색으로 삽입됨)

⦁  루트 노드는 변하지 않으며, 삽입된 노드는 빨강색을 유지합니다.

규칙 위반 해결 예시
⦁  배열: [10, 20, 30]
⦁  30을 삽입합니다.

    10B
       \
       20R
           \
           30R (빨강색으로 삽입됨)

⦁  두 연속된 빨강 노드(20R과 30R)가 있으므로, 트리의 균형을 맞추기 위해 회전 및 색상 변경이 필요합니다.

1. 왼쪽 회전:

    20B (루트가 변경됨)
   /   \
  10R  30R

2. 색상 변경:

    20B
   /   \
  10B  30B

이 과정을 통해 트리는 균형을 유지하며, 루트 노드는 항상 검정색으로 유지됩니다.

요약
⦁  첫 번째 노드 삽입: 루트 노드는 처음 삽입되는 노드이며, 검정색으로 설정됩니다.
⦁  추가 노드 삽입: 새로운 노드는 항상 빨강색으로 삽입되며, 트리의 균형을 유지하기 위해 필요에 따라 회전 및 색상 변경이 수행됩니다.
⦁  트리 균형 유지: 레드-블랙 트리의 규칙을 통해 루트 노드는 항상 검정색으로 유지됩니다. 삽입 및 삭제 연산 후 트리의 균형을 맞추기 위해 회전 및 색상 변경이 수행됩니다.

 

 

레드-블랙 트리 삭제

레드-블랙 트리에서 노드를 삭제하는 과정은 조금 복잡하지만, 중요한 것은 트리의 균형을 유지하고 레드-블랙 트리의 속성을 지키는 것입니다. 이를 위해 삭제 후에는 회전과 색상 변경을 통해 트리를 재조정해야 할 때가 많습니다. 다음은 레드-블랙 트리에서 노드를 삭제하는 과정을 단계별로 설명하겠습니다.

레드-블랙 트리의 속성
레드-블랙 트리는 다음과 같은 속성을 가지고 있습니다:
1. 노드는 빨강(Red) 또는 검정(Black) 중 하나의 색을 가집니다.
2. 루트 노드는 항상 검정색입니다.
3. 모든 리프 노드는 검정색입니다. (리프 노드는 NIL 노드를 의미합니다)
4. 빨강 노드의 자식 노드는 항상 검정색입니다. (빨강 노드가 연속해서 나타날 수 없습니다)
5. 루트에서 모든 리프 노드(NIL 노드)까지의 경로에는 같은 수의 검정 노드가 있어야 합니다.

삭제 과정
레드-블랙 트리에서 노드를 삭제하는 과정은 일반적인 이진 탐색 트리에서의 삭제 과정과 비슷합니다. 그러나 삭제 후 트리의 균형을 유지하기 위해 추가적인 작업이 필요합니다.

1. 노드 삭제
노드를 삭제하는 과정은 다음과 같은 세 가지 경우로 나눌 수 있습니다:
1. 삭제할 노드가 리프 노드(NIL 노드)인 경우
2. 삭제할 노드가 하나의 자식만 가지는 경우
3. 삭제할 노드가 두 개의 자식을 가지는 경우

예시: 값을 5로 하는 노드 삭제

초기 상태
레드-블랙 트리의 초기 상태는 다음과 같습니다:

       6B
      / \
     3R  9B
    / \  / \
   1B 5B 7R 10R

노드 5를 삭제하는 과정을 단계별로 설명합니다.

1. 삭제할 노드가 리프 노드(NIL 노드)인 경우
⦁  이 경우, 노드를 단순히 제거하면 됩니다.
⦁  레드-블랙 트리의 속성을 위반할 가능성이 낮습니다.

2. 삭제할 노드가 하나의 자식만 가지는 경우
⦁  이 경우, 삭제할 노드를 자식 노드로 대체합니다.
⦁  만약 삭제한 노드와 자식 노드가 모두 빨강색인 경우, 단순히 대체하면 됩니다.
⦁  그렇지 않은 경우, 추가적인 조정이 필요할 수 있습니다.

3. 삭제할 노드가 두 개의 자식을 가지는 경우
⦁  이 경우, 삭제할 노드를 그 다음 큰 값(오른쪽 서브트리에서 가장 작은 값)으로 대체합니다.
⦁  그 다음 큰 값을 가진 노드를 삭제합니다.
⦁  이 과정에서 경우 1 또는 2로 변경됩니다.

예시에서 5 삭제
1. 삭제할 노드 찾기: 값이 5인 노드를 찾습니다.

2. 노드 삭제: 노드 5를 삭제합니다. 이 경우, 삭제할 노드는 하나의 자식(리프 노드)을 가집니다.

       6B
      / \
     3R  9B
    /   / \
   1B  7R 10R

3. 트리 조정:
  ⦁ 삭제된 노드 5는 검정색이었으므로, 레드-블랙 트리의 속성이 위반될 수 있습니다.
  ⦁ 따라서 트리의 균형을 맞추기 위해 추가적인 조정이 필요합니다.

트리 재조정
삭제 후, 레드-블랙 트리의 속성을 유지하기 위해 회전 및 색상 변경을 통해 트리를 재조정합니다. 이 과정은 여러 단계를 거칠 수 있으며, 형제 노드의 색상 및 자식 노드의 색상에 따라 다릅니다.

경우 1: 형제 노드가 빨강색인 경우
⦁  형제 노드를 검정색으로 바꾸고 부모 노드를 빨강색으로 바꾼 후, 부모 노드를 기준으로 회전합니다.

경우 2: 형제 노드가 검정색이고, 형제의 자식이 모두 검정색인 경우
⦁  형제 노드를 빨강색으로 바꿔서 부모 노드가 하나의 검정색을 잃게 만듭니다. 부모 노드에서 이 과정을 재귀적으로 반복합니다.

경우 3: 형제 노드가 검정색이고, 형제의 먼쪽 자식이 빨강색이고, 가까운쪽 자식은 검정색인 경우
⦁  형제 노드를 빨강색으로 바꾸고, 형제의 먼쪽 자식을 검정색으로 바꾼 후, 형제를 기준으로 회전합니다.

경우 4: 형제 노드가 검정색이고, 형제의 가까운쪽 자식이 빨강색인 경우
⦁  형제의 가까운쪽 자식을 검정색으로 바꾸고, 부모 노드를 빨강색으로 바꾼 후, 부모를 기준으로 회전합니다.

예시에서 트리 재조정
1. 형제 노드 색상 확인:
  ⦁ 노드 5의 형제 노드 7은 빨강색입니다.

2. 색상 변경 및 회전:
  ⦁ 형제 노드 7을 검정색으로, 부모 노드 6을 빨강색으로 변경한 후, 부모 노드 6을 기준으로 왼쪽 회전합니다.

       7B
      / \
     3B  9B
    /   / \
   1B  6R 10R

3. 색상 조정:
  ⦁ 부모 노드 6을 검정색으로 변경합니다.

       7B
      / \
     3B  9B
    /   / \
   1B  6B 10R

이제 레드-블랙 트리의 모든 속성이 유지됩니다.

요약
레드-블랙 트리에서 노드를 삭제하는 과정은 다음과 같습니다:
1. 노드 삭제: 삭제할 노드를 찾고, 일반적인 이진 탐색 트리 방식으로 삭제합니다.
2. 트리 재조정: 삭제 후, 레드-블랙 트리의 속성을 유지하기 위해 회전 및 색상 변경을 통해 트리의 균형을 맞춥니다.

레드-블랙 트리는 이러한 규칙과 조정 과정을 통해 균형을 유지하며, 효율적인 연산을 보장합니다.

 

레드-블랙 트리 탐색

레드-블랙 트리의 탐색 과정은 일반적인 이진 검색 트리와 동일하게 작동합니다. 다만, 레드-블랙 트리는 삽입이나 삭제 후에도 균형을 유지하므로, 최악의 경우에도 O(log n)의 시간 복잡도를 보장합니다. 이는 트리가 편향되거나 불균형해지는 것을 방지하여 검색, 삽입, 삭제 등의 연산이 효율적으로 이루어질 수 있도록 합니다.