트리 이론 기본편4 -이진 탐색 트리 + heap(힙) 간단하게-
1. 수식 트리(expression binary tree)
수식을 표현하는 이진 트리
수식 이진 트리라고도 부른다
연산자는 루트 노드이거나 가지 노드
루트와 잎 사이의 중간 노드들을 가지 노드라고 하나봐
피연산자는 모두 잎 노드에 존재함
전위, 중위, 후위순회를 이용해서 순회하면 수식의 전위표기법, 중위표기법, 후위표기법이 된다
2. 예시
다음과 같은 트리를 전위, 중위, 후위순회 해서 전위표기법, 중위표기법, 후위표기법을 구해보면?
2-1) 구현 예시
#class 정의
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
#tree 정의
root = Node('+')
root.left = Node('*')
root.right = Node('4')
root.left.left = Node('*')
root.left.right = Node('5')
root.left.left.left = Node('/')
root.left.left.right = Node('3')
root.left.left.left.left = Node('1')
root.left.left.left.right = Node('2')
#전위순회
def preorder(node):
if node:
print(node.data,end=' ')
preorder(node.left)
preorder(node.right)
print('전위순회')
preorder(root)
print()
##중위순회
def inorder(node):
if node:
inorder(node.left)
print(node.data,end=' ')
inorder(node.right)
print('중위순회')
inorder(root)
print()
##후위순회
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.data,end=' ')
print('후위순회')
postorder(root)
전위순회
+ * * / 1 2 3 5 4
중위순회
1 / 2 * 3 * 5 + 4
후위순회
1 2 / 3 * 5 * 4 +
3. 이진 탐색 트리
탐색 작업을 효율적으로 하기 위한 자료구조
모든 원소는 서로 다른 유일한 키를 갖는다
key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
>> 무슨 말이냐면 루트 노드 기준으로 왼쪽 값들은 루트 노드보다 작고
오른쪽 값들은 루트 노드보다 크다는 소리
왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리
중위 순회하면 오름차순으로 정렬된 값을 얻는다 real???
4. 이진탐색트리 탐색연산
1) 루트에서 시작
2) 탐색할 키 값 x를 루트 노드의 값과 비교
> (x < 루트 노드의 키 값): 루트 노드의 왼쪽 서브트리로 이동해서 탐색
> (x> 루트 노드의 키 값): 루트 노드의 오른쪽 서브트리로 이동해서 탐색
> (x == 루트 노드의 키 값): 원하는 원소를 찾았으니 탐색 성공
서브 트리에 대해 순환적으로 탐색 연산을 반복
4-1) 예시
13을 찾고자 할때 9부터 시작해서 13 > 9니까 오른쪽 이동
다시 13 > 12 이므로 오른쪽 이동
다시 13 < 15이므로 왼쪽 이동
13 = 13이므로 탐색 성공
5. 삽입 연산
1) 이진탐색트리는 유일한 값들을 가지므로, 탐색 연산을 먼저 수행함
>> 삽입할 원소와 같은 원소가 트리에 존재하면 삽입할 수 없기 때문
2) 탐색에서 탐색 실패가 결정되는 위치가 원소를 삽입할 위치가 된다
5-1) 예시
5를 삽입하고자 할때, 9부터 탐색을 시작
5<9 이므로 왼쪽으로 이동, 5>4이므로 오른쪽으로 이동, 5<6이므로 왼쪽으로 이동
그런데 더 이동할 노드가 없으므로 6의 왼쪽 자식에 5를 삽입
6. 삭제 연산
경우의 수가 많아서 난이도가 매우 높다
가장 간단한 리프노드를 지운다면..?
그냥 지우면 끝인데
중간에 예를 들어 12를 지운다면??
저기 15 - 13 - 17 이 부분을 위로 올리는 작업이 필요함
그런데 루트 노드 9를 지운다면??? 골치 아파짐
왼쪽과 오른쪽에서 뭘 루트로 올려야할지 고민임..
작은 값을 올려줄지..? 큰 값을 올려줄지..?
7. 이진탐색트리 연산 성능
탐색, 삽입, 삭제 시간 복잡도는 트리의 높이 h만큼 걸린다고 함
기본 시간복잡도는 O(h)라는 말
여기서 n은 노드 수인가??
평균 시간복잡도는 이진 트리가 균형적으로 잘 퍼지면 O(logn)
최악의 시간 복잡도는 한쪽으로 치우친 편향이진트리에서 O(n)으로 순차 탐색과 같다
7-1) 검색 알고리즘 비교
배열 순차탐색 > O(N)
정렬된 배열의 이진 탐색 > O(logN) <정렬이 되어있고, 고정된 배열 크기, +삽입,삭제시에 추가 연산이 필요함>
이진탐색트리 > 평균 O(logN), 최악 O(N)
##이건 뭔소린지 모르겠네새로운 원소 삽입으로 완전 이진 트리나 균형트리로 바꾸면 최악의 경우를 없앨 수 있다는데
새로운 원소 삽입으로 평균과 최악의 시간이 O(logN)으로 같다는데 뭔소린지 모르겠다
해쉬 검색 > O(1)?
엄청 큰 수를 큰 소수로 나눠서 키를 구한 다음에 미리 만든 테이블에서 빠르게 찾는 방법이라는데
8. 힙(heap)
완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조
위 그림은 빨간색 부분때문에 완전이진트리가 아니라서 heap이 아님
8-1) 최대힙(max heap)
키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
부모 노드의 키 값 > 자식 노드의 키 값
루트 노드는 키 값이 가장 큰 노드이다.
8-2) 최소힙(min heap)
키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
부모 노드의 키 값 < 자식 노드의 키 값
루트 노드는 키 값이 가장 작은 노드이다.
8-3) 삽입연산
완전 이진 트리니까 마지막 레벨에서 빈 노드에 삽입을 할건데
최대힙이냐, 최소힙이냐에 따라서 삽입한 노드의 위치를 바꿔줘야함
최대힙이면 부모 노드 > 자식 노드이고 최소힙이면 부모 노드 < 자식 노드니까
8-4) 삭제연산
힙에서는 루트 노드의 원소만을 삭제할 수 있다
루트 노드의 원소를 삭제하고 반환
최대힙이냐, 최소힙이냐에 따라 최댓값, 최솟값을 구하게 된다
루트 노드 23을 삭제하고 반환하면
이제 힙은 완전이진트리니까 마지막 노드인 10을 삭제하고 루트 노드로 올린다
그런데 최대힙이므로 10을 19와 자리를 바꿔서 19를 루트노드에 위치시키고, 10은 19 자리에 둔다
9. 우선순위 큐
힙의 키를 우선순위로 활용해서, 우선순위 큐를 만들 수 있다
우선순위가 가장 높은 노드를 루트 노드로 보내는 자료구조
힙은 이제 최댓값(값이 가장 클수록), 최솟값(값이 가장 작을수록)이 각각 우선순위가 된거고
다른 우선순위를 정해서 만들면 그게 우선순위 큐가 될거
10. 이진탐색트리 알고리즘 구현 예시
위에서 배운 그대로 삽입연산과 탐색연산을 그대로 구현함
삽입연산은?
루트 노드부터 탐색을 시작해서, target과 현재 루트 노드이 같다면 그대로 return
target이 더 작다면 왼쪽으로 이동
target이 더 크다면 오른쪽으로 이동
이동했는데 now가 None이 되면 반복문 종료하고 None을 return
삽입연산은?
루트부터 탐색을 시작하는데..
당연하지만 넣고자 하는 값이 존재하지 않는다는 것을 보장하는 상태에서 수행해야하고
p에 now를 미리 저장해두고, 넣고자 하는 값과 현재 node의 값을 비교해서
넣고자 하는 값이 더 작다면 왼쪽으로 이동하고
더 크다면 오른쪽으로 이동하고
근데 이동했더니 None이라면, 이전에 저장해두었던 p에 대해 왼쪽이나 오른쪽으로 삽입하면 된다
#node class 정의
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
#이진탐색트리 class 정의
class BST:
def __init__(self):
self.root = None
#탐색 연산
def search(self,target):
#루트부터 탐색을 시작함
now = self.root
cnt = 0
while now: #루트 노드가 없어질때까지 탐색을 계속
print(now.data) #node 출력
if target == now.data: #목표를 찾았으면
return now
elif target < now.data: #목표가 현재 노드보다 더 작다면
now = now.left #현재 노드를 왼쪽으로 이동함
elif target > now.data: #목표가 현재 노드보다 더 크다면
now = now.right #현재 노드를 오른쪽으로 이동
cnt += 1 #탐색 횟수?
return now #반복이 끝났는데도 찾는 target이 존재하지 않는 경우
#삽입 연산
def insert(self,node):
#루트부터 탐색을 시작
now = self.root
if now == None: #루트부터 존재하지 않으면, 바로 삽입하고 return함
self.root = node
return
while 1: #탐색을 수행하여, 탐색을 실패한 지점에 노드를 삽입함
p = now
#넣고 싶은 데이터 node.data가 현재 node값인 now.data보다 작다면
if node.data < now.data:
now = now.left #왼쪽으로 이동하고
if not now: #왼쪽으로 갔는데, 왼쪽이 존재하지 않는다면(None)
#여기서 p는 왼쪽으로 이동하기 전에 저장해놓은 now이다
#왼쪽으로 이동했더니 now가 None이면, 이동하기 전인 p의 왼쪽에
#삽입을 하면 된다
p.left = node
return
#넣고 싶은 데이터 node.data가 현재 node값인 now.data보다 크다면
#당연히 삽입은 넣고 싶은 데이터가 존재하지 않는다는 것을 보장한 상태에서 수행해야함
else:
now = now.right #오른쪽으로 이동함
if not now: #오른쪽으로 이동했더니 오른쪽이 존재하지 않는다면(None)
#여기서 p는 오른쪽으로 이동하기 전에 저장해놓은 now이다
#오른쪽으로 이동했더니 now가 None이면, 이동하기 전인 p의 오른쪽에
#삽입을 하면 된다
p.right = node
return
예시로 한번 만들어보면..
bst = BST()
data_list = [9,4,12,3,6,15,13,17] #[9,12,4,6,3,13,15,17]
node_list = [Node(i) for i in data_list]
#삽입
for node in node_list:
bst.insert(node)
#오른쪽
bst.search(17)
#왼쪽
bst.search(3)
9
12
15
17
9
4
3
<__main__.Node at 0x7f541c6d2e10>
루트 9의 오른쪽에는 9보다 큰 값들이 들어가고 왼쪽에는 작은 값들이 들어간걸로 보아 잘 만들어진듯
'알고리즘 > 그래프 이론 정복기' 카테고리의 다른 글
| 그래프 이론 - 서로소집합(disjoint set) 기본개념1 - (0) | 2022.09.29 |
|---|---|
| 트리 이론 기본편 -중위 순회의 특징 응용하기- (0) | 2022.09.15 |
| 트리 이론 기본편3 -이진 트리를 표현하는 방법 + 순회 구현 - (0) | 2022.09.13 |
| 트리 이론 기본편2 -이진 트리 용어 + 트리의 순회 - (0) | 2022.09.13 |
| 트리 이론 기본편1 -용어 정리- (0) | 2022.09.13 |
