알고리즘 분석 | 이진 탐색트리 BST | inorder successor

이전 포스팅

알고리즘 분석 | AVL 트리 | 재편성(restructuring)

이진 탐색 트리(BST)

Fig. 1. BST

BST는 트리 구조를 사용하여 데이터를 저장하고 검색합니다. 각 노드는 하나의 키를 갖고 있으며, 루트 노드부터 시작하여 왼쪽 서브트리는 작은 값의 키를 갖는 노드로, 오른쪽 서브트리는 큰 값의 키를 갖는 노드로 이루어져 있습니다. BST에서는 검색, 삽입, 삭제 작업이 가능하며, 최악의 경우 시간 복잡도는 \(O(n)\)이 될 수 있습니다

 

이진 탐색 트리(BST) Insert

Fig. 2. 이진 탐색 트리 삽

1. BST에서 새로운 요소를 삽입할 때는, 해당 요소의 위치를 찾기 위해 이진 탐색을 수행합니다

2. 삽입하려는 요소가 이미 트리에 존재한다면 삽입 작업을 중지합니다

3. 만약 해당 요소가 트리에 없다면, 그 요소를 삽입할 위치를 찾아서 해당 위치에 요소를 삽입하고, 그 위치를 내부 노드로 변환합니다

예를 들어, 키 값이 5인 요소를 삽입하려면, 해당 키 값을 가진 노드를 찾아서 키 값이 5인 새로운 요소를 삽입하고, 그 위치에 있는 리프 노드를 내부 노드로 변환합니다

 

예를 들어, 아래와 같은 이진 탐색 트리가 있다고 가정해보겠습니다.

          6
        /   \
       3     9
      / \   / \
     1   4 7   10
          \
           5

이때, 리프 노드인 1, 4, 5, 7, 10을 내부 노드로 변환하고자 한다면, 아래와 같이 트리의 구조를 재조정할 수 있습니다.

          6
        /   \
       3     9
      / \   / \
     2   4 8   11
          \
           7

위의 예시에서는 1, 5, 7, 10이 리프 노드였지만, 각각의 노드를 삭제하고 대체하는 새로운 노드를 삽입하여 트리의 구조를 재조정하였습니다. 이때 새로 삽입된 노드는 자식 노드를 가질 수 있으므로, 리프 노드에서 내부 노드로 변환된 것입니다. 이렇게 내부 노드로 변환된 노드는 추가적인 메모리를 사용할 수 있지만, 트리의 구조를 더욱 균형적으로 유지할 수 있습니다.

 

그림에서 2라는 내부 노드는 1이라는 노드를 왼쪽 자식 노드로 가지고 있습니다. 1은 이전에는 2의 오른쪽에 위치한 리프 노드였지만, 2의 자식 노드가 되어 내부 노드가 되었습니다

---

 

이진 탐색 트리(BST) deletion

위 알고리즘은 BST에서 노드를 삭제하는 방법을 설명합니다. 다음과 같은 순서로 수행됩니다.

1. 삭제할 노드를 찾습니다. 이를 remNode라고 부릅니다.
2. 만약 remNode가 leaf이면, 즉 자식 노드가 없으면 즉시 삭제하고 null을 반환합니다.
3. 만약 remNode가 자식 노드를 하나만 가지고 있다면, 그 자식 노드를 반환하여 remNode를 삭제합니다.
4. 그렇지 않은 경우, remNode의 inorder successor를 삭제합니다. 이 때, inorder successor란 BST에서 remNode 다음에 나오는 노드를 말합니다. 이 inorder successor의 key 값을 remNode로 복사한 다음, remNode를 반환합니다.

이렇게 하면, 노드를 삭제할 때, 구조와 균형을 최소화할 수 있습니다. 이 방법은 삭제에 대한 다양한 경우를 모두 다룰 수 있습니다

 

 

inorder successor 이란

inorder successor란 이진 검색 트리에서 삭제할 노드가 두 개의 자식 노드를 가지고 있을 때, 그 노드를 대체할 노드를 말합니다.

이진 검색 트리에서 inorder traversal(중위 순회)를 수행하면, 노드는 오름차순으로 정렬된 순서로 출력됩니다. 예를 들어, 다음과 같은 이진 검색 트리가 있다면,

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

중위 순회를 하면 1, 2, 3, 4, 5, 6, 7 순으로 출력됩니다. 그리고 노드 4를 삭제한다면, 

inorder traversal에서 노드 4 다음으로 오는 노드를 찾아야 합니다.

즉, inorder successor를 찾아야 합니다. 여기서는 5가 inorder successor가 됩니다.

따라서, 삭제할 노드의 inorder successor를 찾아서 그 값을 삭제할 노드에 복사한 후에, inorder successor를 삭제하면 해당 노드를 삭제할 수 있습니다.

 

쉽게 말해 노드 4가 노드 5로 바뀌게 되고, 노드 5가 두개 존재 할 수 없으니, 기존에 부모노드 6 왼쪽 아래 노드에 5를 삭제한다는 의미 입니다

---