1. 트리(Tree)
- 트리는 node와 branch를 이용하여 구성된 데이터구조로 사이클이 없다.
- 트리는 이진트리(Binary Tree)형태의 구조를 이용하여 탐색(검색) 알고리즘 구현에 많이 사용된다.
* 이진트리 - 하나의 node에서 뻗어나가는 branch의 수가 최대 2개인 트리구조
[알아야 할 용어]
- Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 연결되어 있는 다른 노드에 대한 branch정보가 담겨있다.)
- Root Node: 트리 맨 위의 노드
- Level: 최상위 노드인 root node를 level 0으로 하였을 때, branch로 연결된 하위 노드의 깊이를 나타낸다.
- Parent Node: 부모 노드를 의미하며 어떤 node에 연결된 상위 node를 의미한다.
- Child Node: 자식 노드를 의미하며 어떤 node에 연결된 하위 node를 의미한다.
- Leaf Node(= Terminal Node): 자식 노드가 하나도 없는 노드를 의미한다.
- Sibling(= Brother Node): 형제 노드를 의미하며 동일한 부모 node를 가진 자식 노드를 의미한다.
- Depth: 트리에서 node가 가질 수 있는 최대 Level을 의미한다.
1) 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)
- 이진 트리: 하나의 node에서 뻗어나가는 branch의 수가 최대 2개인 트리구조
- 이진 탐색 트리: 이진 트리에서 왼쪽 노드는 반드시 오른쪽 노드보다 작은 값을 갖어야 한다는 것을 의미한다. (아래 사진참조)
2) 이진 탐색 트리의 장/단점과 주요 용도
- 장점: 데이터 탐색(검색)에 용이하다.(탐색 속도를 개선)
- 단점: 구현이 복잡하다. (맨 아래에 더 자세한 설명이 있습니다)
[이진 탐색 트리와 정렬된 배열간의 탐색 속도 비교]
3) 이진 탐색 트리 코드로 구현하기(링크드 리스트를 활용하여 내부구조 구현)
#노드 클래스 정의
class Node:
def __init__(self, value):
self.value = value
#좌측으로 들어갈 노드의 주소값
self.left = None
#우측으로 들어갈 노드의 주소값
self.right = None # 노드를 관리하는 클래스
class NodeMgt:
#루트노드 객체생성
def __init__(self, head):
self.head = head #root node = head
def insert(self, value):
self.current_node = self.head
while True:
# value가 루트 노드보다 작다면(좌측 탐색)
# value가 루트 노드보다 크거나 같다면 우측 탐색
if value < self.current_node.value:
# 좌측 노드에 값이 있는 경우
#(좌측 노드에서도 비교해서 좌우로 나뉘기 떄문)
if self.current_node.left != None:
# 현재 노드를 좌측노드로 바꿔주고 계속 비교
# if문에서 빠져나올 때까지 반복한다.
self.current_node = self.current_node.left
else: # 더이상 좌측 노드가 없다면 좌측에 새로운 노드를 생성
self.current_node.left = Node(value)
break
else: # value가 루트노드보다 큰 경우(우측 탐색)
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
# 현재 노드가 None이 될 때 while문 종료
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
[노드 생성 및 데이터 삽입/검색 테스트]
4) 이진 탐색트리의 특정 노드삭제
- 이진 탐색 트리의 특정 노드를 삭제하는 것은 상당히 복잡하다. 그러므로 여러가지 경우의 수를 미리 생각해야한다.
[노드 삭제 시 경우의 수]
case 1) Leaf Node(Terminal Node) 삭제
- 아래 사진처럼, 15번 노드(19번의 부모노드)가 삭제할 19번 노드를 가리키지 않도록 한다.
case 2) Child Node가 하나인 Node 삭제
- 아래 사진처럼, 15번 노드를 삭제한다면 10번 노드(15번의 부모노드)가 19번노드를 가리키도록 한다.
case 3) Child Node가 두개인 Node 삭제 (두가지 방법 중 하나만 사용)
1. 아래 사진처럼, 삭제할 5번 노드의 오른쪽 자식 중에서 가장 작은값을 10번 노드(5번의 부모노드)가 가리키도록 한다.
2. 삭제할 5번 노드의 왼쪽 자식 중에서 가장 큰 값을 10번 노드(5번의 부모노드)가 가리키도록 한다.
- 위의 두가지 경우 중 한가지 방식을 사용하면 되는데, 간과하는 부분이 존재한다. 1번 방식을 사용하는 경우, 5번노드를 분기점으로 우측 노드 중 가장 작은값을 A노드라고 해보자. A노드를 5번노드의 자리에 올려놓으면 A노드의 부모노드(B노드)가 기존의 A노드의 자리를 더이상 가리키지 않도록 해야한다. 더불어, A노드를 분기점으로 A노드의 우측에 있을 수도 있는 노드를 B노드의 좌측에 연결 시켜야 한다. 기존 A노드의 위치에서 좌측에 자식노드가 없는 이유는 A노드가 가장 작은 값이기 때문이다. (아래 사진참고)
[코드 구현] - 위에서 이진탐색트리 구현해놓은 코드에 메소드로 복붙하면 됩니다.
1) 검증코드
# 1) 삭제할 노드가 트리에 존재하는지 검색
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
### 여기까지 삭제할 노드를 검색해서 찾아냈다. 즉, 삭제할 노드 = self.current_node
2) case 1 - Leaf Node(Terminal Node) 삭제
### case 1 - Leaf Node를 삭제하는 경우
# 1) Leaf Node인지 검증
if self.current_node.left == None and self.current_node.right == None:
# 2) 삭제할 노드의 부모노드가 삭제할 노드를 가리키지 않게 한다.
# 삭제할 노드가 부모노드보다 작다면 좌측
if value < self.parent.value:
self.parent.left = None
# 삭제할 노드가 부모노드보다 크다면 우측
else:
self.parent.right = None
# 3) 노드 삭제
del self.current_node
3) case 2 - Child Node가 하나인 Node 삭제
### case 2 - 자식노드가 1개 있는 노드를 삭제
# 1) 삭제할 노드가 왼쪽에만 자식노드를 갖고 있는 경우
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
# 2) 삭제할 노드가 오른쪽에만 자식노드를 갖고 있는 경우
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
3) case 3 - Child Node가 두개인 Node 삭제
- 전략 1번) 삭제할 노드(15번)의 오른쪽 자식 중 가장 작은 노드(16번)를 삭제할 노드의 부모노드(31번)와 연결한다.
### case 3 - 자식노드를 2개 갖고 있는 노드를 삭제
#전략 1) 삭제할 노드의 오른쪽 자식 중 가장 작은 노드를
# 삭제할 노드의 부모노드가 가리키게 한다
#전략 2) 삭제할 노드의 왼쪽 자식 중 가장 큰 노드를
# 삭제할 노드의 부모노드가 가리키게 한다.
# 주의사항) 전략 1의 가장 작은 노드 또는 전략 2의 가장 큰 노드의 자식노드 유무는 알수 없다.
# 그러므로 이 두가지 경우를 모두 조건문으로 구현한다.
### 전략 1번 (오른쪽, 가장 작은 노드)
# 15번 노드의 자식 노드가 좌우측에 다 있는지 검증
if self.current_node.left != None and self.current_node.right != None:
# 1)삭제할 노드가 부모노드의 왼쪽에 있는 경우
if value < self.parent.value:
#맨 처음에는 아래 두 변수가 15번 노드의 우측 자식(18번)을 가리킴
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
#15번 노드의 우측에 있는 자식노드부터 시작해서
#가장 작은 노드(16번)를 찾기위해 순회한다.
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.chage_node.left
#16번 노드를 찾아서 while문을 탈출하고 수행할 코드
#16번 노드의 부모노드(18번)와 관계를 없앤다.
self.change_node_parent.left = None
#16번 노드의 우측에 자식노드가 있다면 이 자식노드(17번)를
#18번 노드의 좌측에 연결시킨다.
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
#16번 노드를 31번 노드와 연결
self.parent.left = self.change_node
#16번 노드를 18번 노드와 연결
self.change_node.right = self.current_node.right
#16번 노드를 13번 노드와 연결
self.change_node.left = self.current_node.left
# 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.left = self.current_node.left
self.change_node.right = self.current_node.right
2. 이진탐색트리 전체 코드
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.current_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
3. 이진탐색트리 테스트 코드
- 테스트 코드에 오류가 생겼을 때만 출력값이 있습니다.
- 잘 작동한다면 아무런 출력값이 없는게 정상입니다.
[테스트 코드]
# 0 ~ 999 숫자 중에서 임의로 100개를 추출해서, 이진 탐색 트리에 입력, 검색, 삭제
import random
# 0 ~ 999 중, 100 개의 숫자 랜덤 선택
bst_nums = set() #set(): 집합을 사용 / 이유 - 중복된 수를 없애기 위해서
while len(bst_nums) != 100:
bst_nums.add(random.randint(0, 999))
#print (bst_nums)
# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
# 500을 넣은 이유? 0~999 사이의 난수들을 골고루 트리에 넣기 위함
head = Node(500)
bs_tree = NodeMgmt(head)
for num in bst_nums:
bs_tree.insert(num)
# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
if bs_tree.search(num) == False:
print ('search failed', num)
# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums) #index 접근을 위해 list타입으로 변형
#print(bst_nums)
while len(delete_nums) != 10:
delete_nums.add(bst_nums[random.randint(0, 99)])
# 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
for del_num in delete_nums:
if bs_tree.delete(del_num) == False:
print('delete failed', del_num)
4. 이진탐색트리의 시간 복잡도와 단점
a) 이진탐색트리의 시간복잡도
- 이진탐색트리의 시간복잡도는 depth(트리의 깊이)와 연관성이 있다. → O(h)로 표기 (h=depth)
- 노드의 수로 표현한다면 아래의 사진과 같이 표현할 수 있다. * 원래 빅오 표기법에서는 log n의 밑은 2이다.
- 즉, 한번 분기점을 기준으로 좌우를 판단할때 마다 50%의 실행시간을 단축시키는 것을 의미한다.
a) 이진탐색트리의 단점
- 단적인 예를 가지고 설명하겠습니다. (아래 사진참고)
- 위의 사진처럼 데이터가 한쪽 방향으로 저장되게 되면 결국 링크드리스트와 동일한 검색속도를 보인다.
- 이런 불상사를 막기 위해 일부러 노드를 좌우 방향으로 나누기 위한 알고리즘도 존재한다.
'컴퓨터공학기초 개념 > 알고리즘 개념' 카테고리의 다른 글
| Data Structure - Heap(2) (0) | 2020.09.03 |
|---|---|
| Data Structure - Heap(1) (0) | 2020.08.31 |
| Data Structure - Hash Table (2) (0) | 2020.08.22 |
| Data Structure - Hash Table (1) (0) | 2020.08.22 |
| Data Structure - 시간 복잡도(Time Complexity) (0) | 2020.08.21 |
댓글