* 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다.
📌 노드 클래스 만들기
✔️ Node 는 data값과 brach에 대한 정보를 가지고 있다.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
📌 이진 탐색 트리 삽입/ 탐색 구현
✔️ 이진 탐색 트리를 control 하는 class를 생성한다. => NodeMgmt
class NodeMgmt:
def __init__(self, head):
# 제일 위에있는 root node를 설정
self.head = head
def insert(self, value):
# root node 부터 시작
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):
# root node 부터 시작
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)
print(BST.search(0)) # True
print(BST.search(8)) # True
print(BST.search(-1)) # False
📌 이진 탐색 트리 삭제 구현
이진 탐색 트리에서 삭제는 구현하기 매우 복잡하다. 경우를 크게 3개로 다음과 같이 나눈다.
- Leaf Node 삭제
- Child Node 가 하나인 Node 삭제
- Child Node 가 두개인 Node 삭제
✔️ case1: Leaf Node 삭제
- Leaf Node는 자식 노드가 없는 노드
- 이 경우 노드만 제거하면 끝남! 제일 간단한다.
- 삭제할 노드의 (부모 노드)가 삭제할 노드를 가리키지 않도록 한다.
- 즉 parent_node.right = None 또는 parent_node.left = None
✔️ case2: Child Node 가 하나인 Node 삭제
- 삭제할 노드의 (부모 노드)가 삭제할 노드의 (자식 노드)를 가리키게 함.
- 즉 parent_node.right/left = current_node.right/left
✔️ case3: Child Node 가 두개인 Node 삭제
- 이 경우가 제일 복잡하다.
- 삭제할 노드의 (오른쪽 자식 중, 가장 작은 노드)를 (삭제할 노드의 부모 노드)가 가리키도록 한다.
- 이 방법도 크게 2가지 case로 나눠진다
- [삭제할 노드의 오른쪽 자식중 가장 작은 노드]가 [오른쪽 자식]이 없는 경우
- [삭제할 노드의 오른쪽 자식중 가장 작은 노드]를 [삭제할 노드 위치]로 이동시킴
- [삭제할 노드의 오른쪽 자식중 가장 작은 노드]가 [오른쪽 자식]이 있는 경우
- [삭제할 노드의 오른쪽 자식중 가장 작은 노드]를 [삭제할 노드 위치]로 이동시킴
- [삭제할 노드의 오른쪽 자식중 가장 작은 노드]의 오른쪽 자식을 [삭제할 노드의 오른쪽 자식중 가장 작은 노드 의 부모노드]의 [왼쪽 자식]으로 설정함
- [삭제할 노드의 오른쪽 자식중 가장 작은 노드]가 [오른쪽 자식]이 없는 경우
✔️ 삭제 구현 코드
class NodeMgmt:
def __init__(self, head):
self.head = head
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
# case1
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
# case2
elif 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
# case 3
elif self.current_node.left != None and self.current_node.right != None:
# case3-1
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
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.right = self.current_node.right
self.change_node.left = self.current_node.left
return True
📌 이진 탐색 트리 전체 코드
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
# case1
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
# case2
elif 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
# case 3
elif self.current_node.left != None and self.current_node.right != None:
# case3-1
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
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.right = self.current_node.right
self.change_node.left = self.current_node.left
return True참고: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html
Eunji Kim @ CAU - 파이썬을 사용한 이진 트리와 순회 알고리즘 구현 (1)
이진 트리 (binary tree)는 최대 두 개의 자식 노드를 가지는 트리 형태의 자료구조로서, 단순히 값을 저장하기 위한 용도로 사용되기 보다는 효율적인 탐색 혹은 정렬을 위해 사용된다. 이진 탐색
ejklike.github.io
✔️ 전체 코드 테스트
# 0 ~ 999 숫자 중에서 임의로 100개를 추출해서, 이진 탐색 트리에 입력, 검색, 삭제
import random
# 0 ~ 999 중, 100 개의 숫자 랜덤 선택
bst_nums = set()
while len(bst_nums) != 100:
bst_nums.add(random.randint(0, 999))
# print (bst_nums)
# 선택된 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)
📌 이진 탐색 트리 시간 복잡도
✔️ 평균 시간 복잡도 : O(logn)
이는 트리가 균형잡혀 있을 때의 평균 시간 복잡도이다.
✔️ 최악의 시간 복잡도 : O(n)
다음과 같이 구성되어 있다면, 링크드 리스트와 같은 성능을 보여준다.
'Algorithm > data structure' 카테고리의 다른 글
| [자료 구조] 트리(Tree) - 1.구조 이해 (0) | 2021.06.25 |
|---|---|
| [자료구조] 힙(Heap) - 2. 파이썬 구현 (0) | 2021.06.25 |
| [자료구조] 힙(heap) - 1.구조 이해 (0) | 2021.06.25 |
