15. 정렬과 검색
#@title 무작위
import random as r
def sequential_search(alist, target):
for element in alist:
if element == target:
return True
return False
ss_list = [r.randint(1,30) for _ in range(8)]
print(ss_list)
target = r.randint(1,30)
print(target)
print(sequential_search(ss_list, target))
import random as r
def binary_search_rec(alist, target, start, end):
if start > end:
return None
mid = (start + end) // 2
if target == alist[mid]:
return mid
elif target < alist[mid]:
return binary_search_rec(alist, target, start, mid - 1)
else:
return binary_search_rec(alist, target, mid+1, end)
bs_list = [r.randint(1,10) for _ in range(8)]
bs_list.sort()
print(bs_list)
target = r.randint(1,10)
print(target)
print(binary_search_rec(bs_list, target, 0, len(bs_list) - 1))
15-1. 이진 탐색 트리(BST; Binary Search Tree)
+ 특징
+ 각 노드당 키 값은 하나
+ 키 값은 모두 다르다
+ 최상위에 루트 노드, 각 노드는 최대 2개의 자식노드
+ 임의 노드의 키값은 왼쪽 아래에 있는 모든 노드 키값보다 크고,
오른쪽 아래에 있는 모든 키값보다 작다
15-1-1. ADT 구조
+ 노드 : Node
+ item : 키 -> 값
+ left : 왼쪽 노드
+ right : 오른쪽 노드
+ 이진 탐색 트리
+ 속성(데이터)
+ root : 루트 노드
+ 메서드
+ .search(x) : 원소 x를 검색
+ .insert(x) : 원소 x를 삽입
+ .delete(x) : 원소 x를 삭제
+ .is_empty() : 키 -> 값이 없는가?
+ .clear() : 키 전체 삭제
+ 트리 순회 : tree traversal
+ 주어진 정책(알고리즘)에 따라 트리 전체 또는 일부를 차례를 방문
+ 중위 순회 : inorder traversal
+ 왼 -> 자기 -> 오
+ 전위 순회 : preorder traversal
+ 자기 -> 왼 -> 오
+ 후위 순회 : postorder traversal
+ 왼 -> 오 -> 자기
+ 레벨 순서 순회 : level-order traversal
+ 위 -> 아래, 왼 -> 오
+ 힙
15-2. 기능
15-2-1. 검색
```
# 루트 노드가 t인 트리에서 키(값) x
search(t, x):
if (t == None | t.item == x)
return t
else if x < t.item
return search(t.left, x)
else
return search(t.right, x)
```
15-2-2. 삽입
```
insert_sketch(t, x):
if t == None
x를 키(값)으로 하는 노드를 t의 부모 밑에 매달고 끝냄.
else if x < t.item
insert_sketch(t.left, x)
else
insert_sketch(t.right, x)
```
+ 재귀버전
```
insert(x):
root <- insert_item(root, x)
insert_item(t, x):
if t == None
r.item <- x
r.left <- None
r.right <- None
return r
else if x < t.item
t.left <- insert_item(t.left, x)
return t
else
t.right <- insert_item(t.right, x)
return t
```
+ 비재귀버전
```
insert(x):
r.item <- x; r.left <- None; r.right <- None
if root == None
root == r
else
t <- root
while (t != None)
parent <- t
if x < parent.item
parent.left <- r
else
parent.right <- r
```
15-2-3. 삭제
```
# r = 삭제하려는 노드
delete_sketch(r):
# Case 1
if r == 리프노드
그냥 r을 버린다
# Case 2
else if (r의 자식이 하나만 있다)
r의 부모가 r의 자식을 직접 가리키도록 한다 = 연결시킨다
# Case 3
else
r의 오른쪽 서브 트리의 최소 원소노드 s를 찾는다
s를 r자리로 복사하고 s 삭제
```
```
# r : 삭제할 노드, p : 부모 노드
delete(r, p):
# 부모노드 기억방법
# 1. 부모 노드 알려주는 것 <-
# 2. 부모 노드가 필요로 하는 링크 정보를 리턴하도록 하는 것 <- 재귀
if r == root
root <- delete_node(root)
else if r == p.left
p.left <- delete_node(r)
else # r == p.right
p.right <- delete_node(r)
delete_node(r):
# Case 1
if (r.left == r.right == None)
return None
# Case 2
else if (r.left == None and r.right != None) # 오른 자식
return r.right
else if (r.left != None and r.right == None) # 왼자식
return r.left
# Case 3
else
# 오른 서브트리부터 시작
s <- r.right
while (s.left != None)
parent <- s
s <- s.left
# 우 서브트리의 최소값 복사
r.item <- s.item
if s == r.right
r.right <- s.right
else
parent.left <- s.right
return r
```
```python
# t : 루트노드, 서브트리의 루트 노드, x : 삭제 원소
# 삭제 원소 확인 과정 (해당 원소, 왼쪽, 오른쪽)
delete(t, x):
if t == None
에러(Not Found)
else if (x == t.item)
# 자식 확인 작업
t <- delete_node(t)
return t
# x가 왼쪽
else if x < t.item
# 노드를 직접 삭제하는 게 아니라, 왼쪽 내려가기
t.left <- delete(t.left, x)
return x
else
t.right <- delete(t.right, x)
return t
# Case 나누기 : 노드 삭제, 자식 확인
delete_node(t):
# Case 1
if t.left == None and t.right == None
return None
# Case 2 : 오른쪽 자식
else if t.left == None
return t.right
# Case 2 : 왼쪽 자식
else if t.right == None
return t.left
else
# 우 서브 트리 기준으로 최소값과 최소값의 자식노드 찾기
(min_item, node) <- delete_min_item(t.right)
t.item <- min_item
t.right <- node
return t
delete_min_item(t):
if t.left == None
return t.item, t.right
else
# 이미 내려온 상태 <- 왼쪽으로 계속 진행
(min_item, node) = delete_min_item(t.left)
# t가 min값이니 위로 올릴 것이기 때문
t.left <- node
# 처음에만 연결해주고, 나머지는 일관성 유지
return (min_item, t)
```
15-2-4. 순회
+ 전위순회
+ 자기 -> 왼 -> 오른쪽
```
pre_order(r):
if r != None
r.visited == True
pre_order(r.left)
pre_order(r.right)
```
+ 중위 순회
+ 왼 -> 자기 -> 오
```
in_order(r):
if != None
in_order(r.left)
r.visited == True
in_order(r.right)
```
+ 후위 순회
+ 왼 -> 오 -> 자기
```
post_order(r):
if r != None
post_order(r.left)
post_order(r.right)
r.visited == True
```
15-3. 구현
class TreeNode:
def __init__(self, new_item, left, right):
self.item = new_item
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.__root = None
# 검색
def search(self, x) -> TreeNode:
return self.__search_item(self.__root, x)
def __search_item(self, node: TreeNode, x) -> TreeNode:
if node == None:
return None
elif x == node.item:
return node
elif x < node.item:
return self.__search_item(node.left, x)
else:
return self.__search_item(node.right, x)
# 삽입
def insert(self, new_item):
self.__root = self.__insert_item(self.__root, new_item)
def __insert_item(self, node: TreeNode, new_item) -> TreeNode:
if node == None:
node = TreeNode(new_item, None, None)
elif new_item < node.item:
node.left = self.__insert_item(node.left, new_item)
else:
node.right = self.__insert_item(node.right, new_item)
return node
# 삭제
def delete(self, x):
self.__root = self.__delete_item(self.__root, x)
def __delete_item(self, node: TreeNode, x) -> TreeNode:
if node == None:
return None
elif x == node.item:
node = self.__delete_node(node)
elif x < node.item:
node.left = self.__delete_item(node.left, x)
else:
node.right = self.__delete_item(node.right, x)
return node
def __delete_node(self, node: TreeNode) -> TreeNode:
'''
Case 1 : node가 리프노드
Case 2 : node 자식이 하나
Case 3 : node 자식이 둘
'''
if node.left == None and node.right == None:
return None
elif node.left == None:
return node.right
elif node.right == None:
return node.left
else:
(min_item, ret_node) = self.__delete_min_item(node.right)
node.item = min_item
node.right = ret_node
return node
def __delete_min_item(self, node: TreeNode) -> tuple:
if node.left == None:
return (node.item, node.right)
else:
(min_item, ret_node) = self.__delete_min_item(node.left)
node.left = ret_node
return (min_item, node)
# 기타
def is_empty(self) -> bool:
return self.__root == None
def clear(self):
self.__root = None
15-3-1. 테스트
bst = BinarySearchTree()
bst.insert(10)
bst.insert(20)
bst.insert(5)
bst.insert(80)
bst.search(20)
bst.delete(5)
