2-3 Tree - Insertion, Deletion

1. Insertion

 

일단 search로 insert해야 할 노드의 위치를 찾아본다. 이 노드가 어떤 상태냐에 따라 다음의 세 가지 경우로 나누어 생각해 볼 수 있다.

 

1. 노드에 키값이 한 개일때

2. 노드에 키값이 두 개고, 그 부모 노드의 키값은 한 개일때

3. 노드에 키값이 두 개고, 그 부모 노드의 키값도 두 개일때

 

❗️노드가 루트고 키값이 두개인 경우,

'노드에 키값이 두 개고, 그 부모 노드의 키값이 0개일때'

라고 할 수 있으나 이런 경우는 발생하지 않는다.

 

 

 

1. 노드에 키값이 한 개일때

이 경우에는 그냥 그 노드에 넣어주면 끝난다. 예를 들어,

 

        30

       /     \

    10     35

 

에 40을 넣으면

 

        30

       /     \

    10     35,40

 

이 되고 끝난다.

 

 

 

2. 노드에 키값이 두 개고, 그 부모 노드의 키값은 한 개일때

 

이 경우에는 일단 노드에 그 키를 넣어본다. 예를 들어 

 

        30

       /     \

    10     35,40

 

여기 50을 넣는다면 

 

        30

       /     \

    10     35,40,50

 

으로 넣는다. 이러면 3개가 한 노드에 들어가므로 오버플로우가 발생한다. 그럼 20,40,50 중 가운데 값인 40을 승격시켜준다.

 

        30,40

       /     \

    10     35,50

 

 

이러면 될까? 안된다. 30, 40으로 두 키값이 들어있는데 자식 노드는 두개밖에 없다. 따라서 35, 50을 쪼개줘야 한다.

 

         30,40

       /     |    \

    10    35   50

 

완성!

 

 

 

3. 노드에 키값이 두 개고, 그 부모 노드의 키값도 두 개일때

 

가장 복잡한 경우이다. 일단 

 

         30,40

       /     |    \

    10    35   50,60

 

여기 70을 넣는다고 가정한다. 일단 넣어본다.

 

         30,40

       /     |    \

    10    35   50,60,70

 

당연히 오버플로우가 발생한다. 여기서 2.번처럼 60을 승격시키고 쪼개면 이렇게 된다.

 

         30,40,60

       /     |    \    \

    10    35   50  70

 

그러면 자식 노드가 네 개인 노드가 생겨버린다. 이제 40을 승격시키고(부모 노드가 없으면 빈 노드를 만들고 부모 노드로 삼는다), 30과 60을 쪼갠다.

 

                40

              /        \

         30          60

       /     \        /    \

    10    35     50  70

 

완성!

 

 

 

 

 

 

2. Deletion

 

deletion은 두 단계로 나뉜다. 

1. 삭제할 키값의 노드가 리프가 아닐 경우, inorder successor인 키값과 해당 키값을 스왑한다.

2. 해당 키값을 삭제하고(노드를 삭제하는게 아니다) 정리한다.

 

 

1. 삭제할 키값의 노드가 리프가 아닐 경우, inorder successor인 키값과 해당 키값을 스왑한다.

 

여기서 inorder successor란 트리를 inorder로 순회했을 때 해당 키값 바로 뒤에 오는 키값을 의미한다. 즉, 노드의 오른쪽 서브트리 내에서 가장 왼쪽에 있는 노드를 의미한다.

 

예를 들면

 

                40

              /        \

         30          55, 60

       /     \        /    |    \

    10    35     50  57   70

 

여기서, 

40의 inorder successor는 50

30 의 inorder successor는 35

55의 inorder successor는 57

60의 inorder successor는 70

이다.

 

55를 삭제한다면 이 단계에서 

 

                40

              /        \

         30          57, 60

       /     \        /    |    \

    10    35     50  55   70

 

이렇게 된다.

 

 

 

2. 해당 키값을 삭제하고(노드를 삭제하는게 아니다) 정리한다.

 

삭제 자체는 별게 아니다. 위에서 55를 삭제한다고 했으니 계속 이어나가보자. 

 

                40

              /        \

         30          57, 60

       /     \        /    |    \

    10    35     50   -    70

 

이렇게 된다. 노드를 삭제하는게 아니라고 했다. 따라서 노드는 그대로 두되, 그 자리에 -를 써놓는다.

 

이걸 정리해야 한다. 이 부분이 굉장히 복잡하다.

 

 

 

정리하는 방법

 

-가 들어있는 노드에 대해 2 X 2 + 1의 다섯 가지 경우로 나누어 생각할 수 있다.

 

 

⓵ 리프 노드인경우

② 리프 노드가 아닌 경우 (위에서 스왑했는데 왜 이런 경우가 생기냐면 뒤에 나온다)

 

X

 

⓵ 형제 중 키값을 두개 이상 가지고 있는 있는 형제가 있는 경우

② 형제 중 키값을 두개 이상 가지고 있는 형제가 없는 경우

 

+

 

〇 루트인 경우

 

 

 

 

 

0. 〇 루트인 경우

 

               -

               |

         30,40 

       /     |      \  

    10    20  50,57   

 

없애면 된다.

 

         30,40 

       /     |      \  

    10    20  50,57   

 

끝.

 

 

 

1. ⓵ 리프 노드인경우 ➕ ⓵ 형제 중 키값을 두개 이상 가지고 있는 있는 형제가 있는 경우

 

                40

              /          \

         30              57, 60

       /     \        /          |    \

    10    35     45,50   -    70

 

이러면 형제 중 45,50 을 가지고 있는 노드가 '키값을 두개 이상 가지고 있는 형제'이다. 이 부유한 형제에게서 하나만 뺏어오면 된다. 단, 50을 그대로 뺏어오면 부모 노드의 57과 순서가 꼬이기 때문에, 부모에게서 57을 뺏어오고 부모가 45,50중 50을 뺏어오면 된다.

 

                40

              /          \

         30              60

       /     \        /      |    \

    10    35     45    57    70

 

완성!

 

 

2. ⓵ 리프 노드인경우 ➕ ② 형제 중 키값을 두개 이상 가지고 있는 형제가 없는 경우

 

이건 이 경우이다.

 

                40

              /        \

         30          57, 60

       /     \        /    |    \

    10    35     50   -    70

 

뺏어올만큼 부유한 형제가 없다. 그럼 형제중 하나와 한집살림을 하는 동시에 부모에게서 하나를 뺏어와야 한다.

 

                40

              /        \

         30          - , 60

       /     \        /     \

    10    20     50,57    70

 

그럼 부모 노드가 -를 가지게 된다. 이 다음은 어떻게 하나? 뭘 어떻게 하나요. 그냥 -를 없애면 된다.

 

                40

              /        \

         30           60

       /     \        /     \

    10    20     50,57    70

 

 

 

3. ② 리프 노드가 아닌 경우 ➕ ⓵ 형제 중 키값을 두개 이상 가지고 있는 있는 형제가 있는 경우

 

바로 위의 트리를 조금만 변형해보면 이 경우가 된다.

 

                  40

              /          \

         30,32          - , 60

       /    |    \           /        \

    10   31    35    50,57    70

 

그럼 뺏어오는건 마찬가진데, 그 아래 식솔들도 다 데려와야 한다. 이 경우 35를 데리고 와야한다.

 

                  32

              /          \

         30           40 , 60

       /    |         /      |        \

    10   31      35   50,57    70

 

 

 

4. ② 리프 노드가 아닌 경우 ➕ ⓵ 형제 중 키값을 두개 이상 가지고 있는 형제가 없는 경우

 

 

                40

              /        \

         30           - 

       /     \          |    

    10    20     50,57    

 

뺏어올 형제가 없으니 부모에게서 뺏어오면서 동시에 합쳐야 한다.

 

               -

               |

         30,40 

       /     |      \  

    10    20  50,57   

 

이제 0번으로 가면 된다.