트리
1. 트리 (Tree) 구조
•
트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
•
실제로 어디에 많이 사용되나?
◦
트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
•
Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
•
Root Node: 트리 맨 위에 있는 노드
•
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
•
Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
•
Child Node: 어떤 노드의 상위 레벨에 연결된 노드
•
Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
•
Sibling (Brother Node): 동일한 Parent Node를 가진 노드
•
Depth: 트리에서 Node가 가질 수 있는 최대 Level
2. 이진 트리와 이진 탐색 트리 (Binary Search Tree)
•
이진 트리: 노드의 최대 Branch가 2인 트리
•
이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
◦
왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!
3. 자료 구조 이진 탐색 트리의 장점과 주요 용도
•
주요 용도: 데이터 검색(탐색)
•
장점: 탐색 속도를 개선할 수 있음
•
단점: 입력이 balanced하게 들어오지 않을 경우에는 $ O(n)$
이진트리와 정렬된 배열간의 탐색 비교
4. 이진 탐색 트리의 시간 복잡도와 단점
4.1. 시간 복잡도 (탐색시)
•
depth (트리의 높이) 를 h라고 표기한다면, O(h)
•
n개의 노드를 가진다면, $h = log_2{n} $ 에 가까우므로, 시간 복잡도는 $ O(log{n}) $
◦
참고: 빅오 표기법에서 $log{n}$ 에서의 log의 밑은 10이 아니라, 2.
▪
한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함
5. 이진 탐색 트리 삭제
•
매우 복잡함. 경우를 나누어서 이해하는 것이 좋음
5.1. Leaf Node 삭제
•
Leaf Node: Child Node 가 없는 Node
•
삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.
5.2. Child Node 가 하나인 Node 삭제
•
삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.
5.3. Child Node 가 두 개인 Node 삭제
1.
삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
2.
삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
5.3.1. 삭제할 Node의 오른쪽 자식중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우
•
경우의 수가 또다시 두가지가 있음
◦
Case5-1-1: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
◦
Case5-1-2: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
▪
가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임
◦
Case5-2-1: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
◦
Case5-2-2: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
▪
가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임
6.1. 구현
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 삭제할 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
# case2 삭제할 Node가 Child를 하나만 가지고 있을 경우 -> 부모 기준 좌우를 or 삭제할 Node의 왼오 먼저하는 방법 둘다 가능
elif self.current_node.left != None and self.current_node.right == None: #삭제할 Node의 왼쪽 자식이 있는 경우
if value < self.parent.value: #삭제할 Node가 부모의 왼쪽 자식일 때
self.parent.left = self.current_node.left #부모의 left에 삭제할 Node의 자식 붙여줌
else: #삭제할 Node가 부모의 오른쪽 자식일 때
self.parent.right = self.current_node.left #부모의 right에 삭제할 Node의 자식 붙여줌
elif self.current_node.left == None and self.current_node.right != None: #삭제할 Node의 오른쪽 자식이 있는 경우
if value < self.parent.value: #삭제할 Node가 부모의 왼쪽 자식일 때
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:
# case 3-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: #대체할 Node의 오른쪽 자식이 있으면
self.change_node_parent.left = self.change_node.right #대체할 Node의 부모의 left에 연결해줌
else:
self.change_node_parent.left = None
self.parent.left = self.change_node #삭제할 Node의 부모의 Left에 대체할 Node를 연결
self.change_node.right = self.current_node.right #삭제할 Node가 기존에 가지고 있던 right,left 정보를 대체 Node로
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
Plain Text
복사
6.2. 테스트
•
random 라이브러리 활용
◦
random.randint(첫번째 숫자, 마지막 숫자): 첫번째 숫자부터 마지막 숫자 사이에 있는 숫자를 랜덤하게 선택해서 리턴
▪
예: random.randint(0, 99): 0에서 99까지 숫자중 특정 숫자를 랜덤하게 선택해서 리턴해줌
# 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)
Plain Text
복사
