21. 이진 트리와 이진 검색 트리(3) 삭제 - 파이썬

노드 삭제하기

 

상당히 복잡합니다. 

먼저 노드에서 특정값을 찾아야 합니다. 
(find 메서드를 고치면 되겠죠?)

    def find(self, item):
        current = self.root
        while True:
            if current is None:
                return None
            if current.item > item:
                current = current.left
            elif current.item < item:
                current = current.right
            else:  # current.item == item
                return current

 

찾은 뒤에는... 

 

1. 특정값을 가진 노드가 자식 노드가 없는 리프 노드라면 노드를 삭제하고, 삭제된 노드를 가리키던 부모의 링크를 None으로 바꿔줍니다. 

 

2. 만약 한 개의 자식이 있으면, 삭제된 노드를 가리키던 부모의 링크를, 삭제된 노드의 자식에게 향하도록 바꿔줍니다. 

 

3. 두 개의 자식이 있다면 좌측 가지에서 가장 큰 값을 삭제한 노드에 옮겨주거나, 우측 가지에서 가장 작은 값을 삭제한 노드에 옮겨줍니다. 

 

---

 

3번에 대해서는 예를 들어 설명하겠습니다. 

 

5를 삭제하면
좌측 가지에서 가장 큰 수(3) 또는
우측 가지에서 가장 작은 수(7)를
5의 자리로 보내야 합니다. 

 

이진 탐색 트리를 만들 때 5보다 작은 숫자는 왼쪽으로 보냈습니다. 
왼쪽 트리에서 제일 큰 숫자(3)를 5의 자리에 올려야 
왼쪽 트리의 요소들은 3보다 작으며 이 이진 탐색 트리가 성립합니다. 

 

마찬가지로
우측 가지는 5보다 큰 숫자들입니다. 
따라서 우측 가지에서 제일 작은 숫자인 (7)이 5의 자리로 올라가야 합니다.
그러면 7의 우측 가지의 구성요소들은 모두 7보다 크며 이 이진 탐색 트리는 성립됩니다. 

 

---

 

값을 옮기는 것은 조금 복잡한 일이지만
재귀적으로 처리할 수 있습니다. 

 

아래 예에서 5를 삭제하는 경우,
우측 가지의 가장 작은 수인 7을 5의 자리로 올린 뒤
8을 7의 자리에 올려야 합니다. 

 

8을 7의 자리에 올리는 것은
7을 삭제하는 것과 같습니다.

 

재귀적입니다. ~!

   [5]
  /  \
[1]   [9]
 \    /
 [3] [7]
 /    \
[2]   [8]

우측 가지에서 가장 작은 값을 옮기도록 코딩했습니다. 

class Node:

    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None


class BST:

    def __init__(self):
        self.root = None

    def insert(self, item):
        new_node = Node(item)
        if self.root is None:
            self.root = new_node
            return
        current = self.root
        while True:
            parent = current
            if item < current.item:
                current = current.left  #
                if current is None:
                    parent.left = new_node  #
                    break
            else:
                current = current.right  #
                if current is None:
                    parent.right = new_node  #
                    break

    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(node.item, end=' ')
            self.inorder(node.right)

    def get_min2(self, current):
        """root가 아닌 노드에서 시작할 수 있도록 get_min을 수정했습니다."""
        while current.left is not None:
            current = current.left
        return current

    def delete(self, item):
        """재귀 함수에게 초기값을 전달해주는 핼프 함수입니다."""
        self.root = self.delete_node(self.root, item)

    def delete_node(self, current, item):
        # find 메서드를 수정했습니다. item을 찾으면 자식 여부를 확인한 뒤...
        if current is None:
            return None
        if current.item > item:
            current.left = self.delete_node(current.left, item)
            return current
        elif current.item < item:
            current.right = self.delete_node(current.right, item)
            return current
        else:  # current.item == item
            if (current.left is None) & (current.right is None):
                # 자식이 없는 노드
                return None
            elif current.left is None:
                # 우측 자식만 있는 노드
                return current.right
            elif current.right is None:
                # 좌측 자식만 있는 노드
                return current.left
            else:
                # 두 자식이 있는 노드. 우측 가지에서 최소값을 가져온 뒤, 최소값은 삭제합니다.
                min_node = self.get_min2(current.right)
                current.item = min_node.item
                current.right = self.delete_node(current.right, min_node.item)
                return current


boo = BST()

boo.insert(5)
boo.insert(1)
boo.insert(9)
boo.insert(3)
boo.insert(7)
boo.insert(2)
boo.insert(8)

boo.inorder(boo.root)  # 1 2 3 5 7 8 9
print()
boo.delete(5)
boo.inorder(boo.root)  # 1 2 3 7 8 9
print()
boo.insert(5)
boo.inorder(boo.root)  # 1 2 3 5 7 8 9
print()
boo.delete(3)
boo.inorder(boo.root)  # 1 2 5 7 8 9
print()
boo.insert(10)
boo.inorder(boo.root)  # 1 2 5 7 8 9 10
print()
boo.delete(1)
boo.delete(2)
boo.delete(5)
boo.delete(7)
boo.delete(8)
boo.delete(9)
boo.inorder(boo.root)
print()
boo.delete(10)
boo.inorder(boo.root)