6.4. 이진 탐색 트리 삭제
이진 탐색 트리에서 특정 노드를 삭제하는 것은 굉장히 복잡하다. 경우의 수를 나눠서 이해하는 것이 좋다.
- Leaf Node 삭제하는 경우 (Branch가 없을 때)
- Child Node가 하나인 Node 삭제하는 경우 (Branch가 한 개일 때)
- Child Node가 두 개인 Node 삭제하는 경우 (Branch가 두 개일 때)
일단, 이전까지 만들었던 이진 탐색 트리에 데이터 넣는 메서드, 탐색하는 메서드가 정리된 NodeMgmt는 다음과 같다.
class NodeMgmt:
def __init__(self, head):
self.head = head
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node.value:
if self.current_node.left != None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right != None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
def search(self, value):
self.current_node = self.head
while self.current_node:
if self.current_node.value == value:
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False
위의 경우의 수 3가지를 나눠서 작성하려면, 일단 삭제할 노드를 탐색하는 코드가 필요하다.
삭제할 노드가 없는 경우도 처리해야 하므로, 이를 위해 삭제할 노드가 없는 경우는 False를 리턴하고, 함수를 종료시켜야 한다.
class NodeMgmt:
def __init__(self, head):
self.head = head
def delete(self, value): # 특정 value를 가진 노드를 삭제하려는 것
searched = False # 트리를 순회하면서 해당 노드를 찾았는지 못 찾았는지 표시하는 것
# current_node는 삭제할 노드를 지칭하게끔 하고, parent는 삭제할 노드의 parent node를 지칭하게 할 것이다.
self.current_node = self.head
self.parent = self.head # 삭제할 때, 해당 노드의 parent node에서도 작업을 해줘야 한다. 지칭하는 주소를 없애버린다든지..
while self.current_node:
if self.current_node.value == value:
searched = True
break
elif value < self.current_node.value: # 해당 노드가 삭제할 노드가 아니라면, 값의 크기를 비교해서 왼쪽, 오른쪽 어디에 있을지 봐야 한다.
self.parent = self.current_node
self.current_node = self.current_node.left
else: # 같거나 큰 경우
self.parent = self.current_node
self.current_node = self.current_node.right
# while 구문을 지나가면 두 가지 경우가 있다.
# 하나는 해당 노드를 찾았으니, searched에는 True가 들어가 있고, current_node는 삭제할 노드, parent는 삭제할 노드의 parent인 상황이다.
# 다른 하나는 결국에는 self.current_node가 None이 돼서 넘어온 경우이고, 이때 searched는 False가 되어 있다. 찾는 노드가 이 트리에 없으니 그냥 종료하면 된다.
if searched == False: # self.current_node가 None이 돼서 넘어온 경우
return False
### 이후부터 Case들을 분리해서 코드 작성
6.4.1. Leaf Node 삭제
첫 번째는 삭제할 노드가 맨 끝에 있는 Leaf Node(Terminal Node)인 경우이다. Leaf Node란 Child Node가 없는 Node이다. 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 하면 된다.
위 그림에서, Leaf Node인 19를 삭제하기로 했다면, 19인 노드를 삭제하고, 15인 노드가 가리키는 Branch를 없애버리면 된다.
# Case 1: 삭제할 Node가 Leaf Node인 경우
if self.current_node.left == None and self.current_node.right == None:
if value < self.parent.value: # parent의 왼쪽에 붙어있냐, 오른쪽에 붙어있냐에 따라 달라질 수 있기에
self.parent.left = None # 작다면 parent의 왼쪽에 있는 branch가 None을 가리키게 하는 것
else:
self.parent.right = None
del self.current_node
위 그림과 코드를 보면, 지우려고 하는 Leaf Node가 parent 노드의 왼쪽에 있는지, 오른쪽에 있는지도 고려해야 한다. 왜냐하면 parent가 가리키는 주소도 None으로 바꿔야 하기 때문이다.
6.4.2. Child Node가 하나인 Node 삭제
두 번째 경우는 Child Node가 하나인 Node를 삭제하는 경우이다. 여기서는 삭제할 노드의 Parent Node가 삭제할 노드의 Child Node를 가리키도록 한다.
예를 들어, 위 그림에서 Child Node를 한 개 가지고 있는 15를 삭제하려고 한다면, 15를 삭제하고 15의 Parent Node인 10이 삭제한 노드 15의 Child Node를 가리키게 해야 하는 것이다.
이 Case 2는 또 두 가지로 나눌 수 있다.
위 그림에서 삭제할 노드가 갈색으로 칠해진 노드라고 할 때,
- 삭제할 노드가 Child Node를 하나 갖고 있는데 왼쪽에 가지고 있을 때
- 삭제할 노드가 Child Node를 하나 갖고 있는데 오른쪽에 가지고 있을 때
우선 첫 번째 경우를 코드로 구현해보겠다.
# Case 2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
# Case 2-1: 삭제할 노드가 Child Node를 왼쪽에 가지고 있을 때
if self.current_node.left != None and self.current_node.right == None:
if value < self.parent.value: # 위 그림 기준으로, parent인 노드 10보다 작은 노드 5를 지우려는 상황
self.parent.left = self.current_node.left # parent인 10의 left를 지우려는 노드 5의 left인 3으로 연결하는 것
else: # 위 그림 기준으로, parent인 노드 10보다 큰 노드 15를 지우려는 상황
self.parent.right = self.current_node.left # parent인 10의 right를 지우려는 노드 15의 left인 12로 연결하는 것
# Case 2-2: 삭제할 노드가 Child Node를 오른쪽에 가지고 있을 때
elif self.current_node.left == None and self.current_node.right != None:
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
이렇게 된다.
이진 탐색 트리를 구현할 때에는 경우의 수를 직접 그림으로 그려보는 것이 중간에 헷갈리지 않고 차근차근 풀어나갈 수 있는 팁이라고 한다.
6.4.3. Child Node가 두 개인 Node 삭제
Child Node가 두 개인 경우, 두 가지 방법 중 하나를 사용하면 된다.
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
가령 첫 번째 방법을 사용한다고 했을 때, 삭제할 노드 5의 오른쪽 자식은 6이다. 6에게는 계속 Branch가 뻗어나가며 자식들이 있을 수 있다. 그러면 결과적으로 이 안에서 가장 작은 것은 노드 6에서 뻗어나가는 자식들 중 가장 왼쪽에 있는 노드이다. 그 가장 작은 노드를 선택하고, 그것을 삭제하는 노드 5의 위치로 올리면 되는 것이다. 위 그림의 오른쪽 트리에 잘 나타나 있다.
반대로 두 번째 방법을 사용한다고 했을 때, 삭제할 노드 5의 왼쪽 자식은 3이다. 3에게는 계속 Branch가 뻗어나가면서 자식들이 있을 수 있다. 이중에서 가장 큰 것은 노드 3에서 뻗어나가는 자식들 중 가장 오른쪽에 있는 노드이다. 그 가장 큰 노드를 선택하고, 그것을 삭제하는 노드 5의 위치로 올리면 되는 것이다.
첫 번째 방법을 사용할 경우 순서대로 정리해 보면,
- 삭제할 Node의 오른쪽 자식 선택
- 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
- 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
- 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
- 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
- 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함
삭제할 Node가 Child Node를 두 개 가지고 있는 경우도 두 가지 경우로 나눠서 접근해야 한다.
- 삭제할 Node가 Parent Node 왼쪽에 있을 때
- 삭제할 Node가 Parent Node 오른쪽에 있을 때
Case 3-1: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때)
이번에는 두 가지 전략 중 첫 번째인, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 하는 전략을 사용할 것이다.
여기서 경우의 수가 또 2 가지로 나뉘는데,
- Case 3-1-1: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- Case 3-1-2: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 있을 때 (가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음. 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문)
Case 3-1을 코드로 구현해보면 다음과 같다.
if self.current_node.left != None and self.current_node.right != None: # Case 3: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
if value < self.parent.value: # Case 3-1: 삭제할 Node가 Parent Node 왼쪽에 있을 때
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right # change_node뿐만 아니라, change_node_parent까지 알고 있어야 한다. 왜냐하면 가리키는 것을 수정해야 하기 때문이다.
while self.change_node.left != None: # 가장 작은 값을 가지는 노드를 찾기 위해 순회
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None: # Case 3-1-2: 가장 작은 값을 가지는 노드의 오른쪽에 Child Node가 있을 때
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None # 가장 작은 노드를 찾았고, 그 노드 오른쪽에 Child Node가 없다면 change_node_parent의 왼쪽 연결고리를 끊어야 한다.
self.parent.left = self.change_node # 위 그림 기준으로, 16을 parent인 31 왼쪽에 연결한다.
self.change_node.right = self.current_node.right
self.change_node.left = self.change_node.left
Case 3-2: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)
이번에도 두 가지 전략 중 첫 번째인, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 하는 전략을 사용할 것이다.
여기서 또 경우의 수가 두 가지로 나뉜다.
- Case 3-2-1: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- Case 3-2-2: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때 (가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없다)
Case 3-2를 코드로 구현해보면 다음과 같다.
else: # Case 3-2: 삭제할 Node가 Parent Node 오른쪽에 있을 때
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.right = self.change_node
self.change_node.left = self.current_node.left
self.change_node.right = self.current_node.right
6.5. 파이썬 전체 코드 구현
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class NodeMgmt:
def __init__(self, head):
self.head = head
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node.value:
if self.current_node.left != None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right != None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
def search(self, value):
self.current_node = self.head
while self.current_node:
if self.current_node.value == value:
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False
def delete(self, value):
searched = False
self.current_node = self.head
self.parent = self.head
while self.current_node:
if self.current_node.value == value:
searched = True
break
elif value < self.current_node.value:
self.parent = self.current_node
self.current_node = self.current_node.left
else:
self.parent = self.current_node
self.current_node = self.current_node.right
if searched == False:
return False
# Case 1: 삭제할 Node가 Leaf Node인 경우
if self.current_node.left == None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = None
else:
self.parent.right = None
del self.current_node
# Case 2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
# Case 2-1: 삭제할 노드가 Child Node를 왼쪽에 가지고 있을 때
if self.current_node.left != None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = self.current_node.left
else:
self.parent.right = self.current_node.left
# Case 2-2: 삭제할 노드가 Child Node를 오른쪽에 가지고 있을 때
elif self.current_node.left == None and self.current_node.right != None:
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
# Case 3: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
if self.current_node.left != None and self.current_node.right != None:
# Case 3-1: 삭제할 Node가 Parent Node 왼쪽에 있을 때
if value < self.parent.value:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.left = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.change_node.left
# Case 3-2: 삭제할 Node가 Parent Node 오른쪽에 있을 때
else:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.right = self.change_node
self.change_node.left = self.current_node.left
self.change_node.right = self.current_node.right
전체 코드는 이렇게 된다.
이 파이썬 코드를 테스트 해보겠다. 0~999 숫자 중에서 임의로 100개를 추출해서 이진 탐색 트리에 입력, 검색 및 삭제 작업을 수행할 것이다.
random 라이브러리를 활용할 것이다. random.randint(첫 번째 숫자, 마지막 숫자)를 사용하면, 첫 번째 숫자부터 마지막 숫자 사이에 있는 숫자를 랜덤으로 선택해서 리턴한다.
import random
# 0 ~ 999 중, 100개의 숫자 랜덤 선택
bst_nums = set()
while len(bst_nums) != 100:
bst_nums.add(random.randint(0, 999))
# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
binary_tree.insert(num)
# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
if binary_tree.search(num) == False:
print('search failed', num)
# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
delete_nums.add(bst_nums[random.randint(0, 99)])
# 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
for del_num in delete_nums:
if binary_tree.delete(del_num) == False:
print('delete failed', del_num)
위 코드로 테스트를 했을 때, search failed, delete failed가 단 하나도 나타나지 않았다. 잘 작동하는 것이다.
[참고자료]
패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료
'Data Structure & Algorithm' 카테고리의 다른 글
| 힙 (Heap) (2) (1) | 2023.01.06 |
|---|---|
| 힙 (Heap) (0) | 2023.01.06 |
| 트리 (Tree) (2) (0) | 2023.01.03 |
| 트리 (Tree) (0) | 2023.01.02 |
| 해시 테이블 (Hash Table) (3) (0) | 2023.01.01 |
