2020. 10. 30. 19:23ㆍIT공부/자료구조&알고리즘 연습
5.3 이진트리 탐색
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
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)
BST.search(-1)
5.4 이진 탐색 트리 삭제
-> 매우 복잡한 경우를 나눠 이해하는 것이 좋습니다
5.4.1 Leaf Node 삭제
-> Leaf Node: Child Node 가 없는 Node
-> 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다
5.4.2 Child Node 가 하나인 Node 삭제
-> 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다
5.4.3 Child Node가 두 개인 Node 삭제
1. 삭제할 Node의 오른쪽 지식 중 가장 작은 값을 삭제할 Node의 Parent Node가 가리키
2. 삭제할 Node의 왼쪽 자식 중 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록한다
5.4.3.1 삭제할 Node의 오른쪽 자식중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우
- 삭제할 Node의 오른쪽 자식 선택
- 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
- 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
- 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
- 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
5.5 이진 탐색 트리 삭제 코드 규현과 분석
5.5.1 삭제할 Node 탐색
- 삭제할 Node가 없는 경우도 처리해야 한다
이를 위해 삭제할 Node가 없는 경우 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
5.5.2 Case1: 삭제할 Node가 Leaf Node인 경우
# self.current_node 가 삭제할 Node, self.parent는 삭제할 Node의 Parent 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
5.5.2 Case2 : 삭제할 Node가 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
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
5.5.3 Case3-1 : 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
(삭제할 Node가 Parent Node 왼쪽에 있을 때)
- 기본 사용 가능 전략
1. 삭제할 Node의 오른쪽 자식 중 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다
2. 삭제할 Node의 왼쪽 자식 중 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다
- 기본 사용 가능 전략 중 1번 전략을 사용해 코드를 구현하기로 함
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가 있다는 뜻이기 때문입니다.
if self.current_node.left != None and self.current_node.right != None: # case3
if value < self.parent.value: # case3-1
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
강의에 대해 정확하게 알고 싶다면
'IT공부 > 자료구조&알고리즘 연습' 카테고리의 다른 글
| [패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 14회차 미션 (0) | 2020.11.01 |
|---|---|
| [패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 13회차 미션 (0) | 2020.10.31 |
| [패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 11회차 미션 (0) | 2020.10.29 |
| [패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 10회차 미션 (0) | 2020.10.28 |
| [패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 9회차 미션 (0) | 2020.10.27 |