Preface
오늘 공부한 트리 구조를 끝으로 자료구조와 알고리즘 책을 모두 마쳤다.
트리 구조와 이진 트리는 힙 정렬 알고리즘에서 이미 한 번 봤던 내용이라 쉽게 이해하며 넘어갈 수 있었고, 코드 자체도 선형 검색 방법을 따르므로 큰 어려움 없이 금방 작성할 수 있었다.
처음 알고리즘 공부를 시작했을 땐 간단한 코드만 이해할 수 있었을 뿐, 조금만 길고 복잡한 코드를 접하면 겁부터 났었는데, 몇 달 간 다양한 코드를 눈으로 보고 직접 작성해 본 탓인지 그래도 이전보다 조금은 성장한 것 같다고 느껴 나름의 성취감이 생긴다.
이번 주말엔 그동안 업로드했던 코드들을 천천히 복습하며 푹 쉰 후, 다음주부터 데이터베이스 공부를 시작할 생각이다.
1. 트리 구조
- 루트 : 트리의 가장 위쪽에 있는 노드
- 리프(단말 노드, 외부 노드) : 가장 아래쪽에 있는 노드
→ 물리적으로 가장 밑이 아닌, 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 의미이다.
- 비단말(내부) 노드 : 리프를 제외한 모든 노드
- 자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드
- 부모 : 어떤 노드와 가지가 연결되었을 때 가장 위쪽에 있는 노드
- 형제 : 부모가 같은 노드
- 조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드
- 자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드
- 레벨 : 루트에서 얼마나 멀리 떨어져 있는지를 나타내는 것
- 차수 : 각 노드가 갖는 자식의 수
- 높이 : 리프 레벨의 최댓값
- 서브트리 : 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리
- 빈(널) 트리 : 노드와 가지가 전혀 없는 트리
- 순서 트리 : 형제 노드의 순서 관계가 있는 트리
- 무순서 트리 : 형제 노드의 순서를 구별하지 않는 트리
- 순서 트리의 검색 방법
1) 너비 우선 검색(폭 우선·가로·수평 검색) : 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하는 방법
2) 깊이 우선 검색(세로·수직 검색) : 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 방법
→ 깊이 우선 검색에선 각 노드를 최대 3번 지나간다.
- 깊이 우선 검색 방법
1) 전위 순회
2) 중위 순회
3) 후위 순회
2. 이진 트리와 이진 검색 트리
- 이진 트리 : 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리
→ 왼쪽 자식과 오른쪽 자식을 구분한다.
- 완전 이진 트리 : 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리
- 균형 검색 트리 : 높이를 O(log n)으로 제한하여 고안된 검색 트리
- 이진 검색 트리 조건
1) 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다.
2) 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 한다.
- 이진 검색 트리 특징
1) 구조가 단순하다.
2) 중위 순회의 깊이 우선 검색을 통하여 노드값을 오름차순으로 얻을 수 있다.
3) 이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있다
4) 노드를 삽입하기 쉽다.
- 이진 검색 트리 코드
# 이진 검색 트리 구현하기
from __future__ import annotations
from typing import Any, Type
class Node:
def __init__(self, key: Any, value: Any, left: Node = None,
right: Node = None):
self.key = key
self.value = value
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def search(self, key: Any) -> Any:
p = self.root
while True:
if p is None:
return None
if key == p.key:
return p.value
elif key < p.key:
p = p.left
else:
p = p.right
def add(self, key: Any, value: Any) -> bool:
def add_node(node: Node, key: Any, value: Any) -> None:
if key == node.key:
return False
elif key < node.key:
if node.left is None:
node.left = Node(key, value, None, None)
else:
add_node(node.left, key, value)
else:
if node.right is None:
node.right = Node(key, value, None, None)
else:
add_node(node.right, key, value)
return True
if self.root is None:
self.root = Node(key, value, None, None)
return True
else:
return add_node(self.root, key, value)
def remove(self, key: Any) -> bool:
p = self.root
parent = None
is_left_child = True
while True:
if p is None:
return False
if key == p.key:
break
else:
parent = p
if key < p.key:
is_left_child = True
p = p.left
else:
is_left_child = False
p = p.right
if p.left is None:
if p is self.root:
self.root = p.right
elif is_left_child:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p is self.root:
self.root = p.left
elif is_left_child:
parent.left = p.left
else:
parent.right = p.left
else:
parent = p
left = p.left
is_left_child = True
while left.right is not None:
parent = left
left = left.right
is_left_child = False
p.key = left.key
p.value = left.value
if is_left_child:
parent.left = left.left
else:
parent.right = left.left
return True
def dump(self) -> None:
def print_subtree(node: Node):
if node is not None:
print_subtree(node.left)
print(f'{node.key} {node.value}')
print_subtree(node.right)
print_subtree(self.root)
def min_key(self) -> Any:
if self.root is None:
return None
p = self.root
while p.left is not None:
p = p.left
return p.key
def max_key(self) -> Any:
if self.root is None:
return None
p = self.root
while p.right is not None:
p = p.right
return p.key
- 이진 검색 트리 프로그램 코드
from enum import Enum
from bst import BinarySearchTree
Menu = Enum('Menu', ['삽입', '삭제', '검색', '덤프', '키의범위', '종료'])
def select_menu() -> Menu:
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep=' ', end='')
n = int(input(': '))
if 1 <= n <= len(Menu):
return Menu(n)
tree = BinarySearchTree()
while True:
menu = select_menu()
if menu == Menu.삽입:
key = int(input('삽입할 키를 입력하세요.: '))
val = input('삽입할 값을 입력하세요.: ')
if not tree.add(key, val):
print('삽입에 실패했습니다.')
elif menu == Menu.삭제:
key = (int(input('삭제할 키를 입력하세요.: ')))
tree.remove(key)
elif menu == Menu.검색:
key = (int(input('검색할 키를 입력하세요.: ')))
t = tree.search(key)
if t is not None:
print(f'이 키를 갖는 값은 {t}입니다.')
else:
print('해당하는 데이터가 없습니다.')
elif menu == Menu.덤프:
tree.dump()
elif menu == Menu.키의범위:
print(f'키의 최솟값은 {tree.min_key()}입니다.')
print(f'키의 최댓값은 {tree.max_key()}입니다.')
else:
break
'Algorithm > 자료구조와 함께 배우는 알고리즘(Python)' 카테고리의 다른 글
| 원형 이중 연결 리스트 (0) | 2022.01.18 |
|---|---|
| 커서를 이용한 연결 리스트 (0) | 2022.01.15 |
| 연결 리스트, 포인터를 이용한 연결 리스트 (1) | 2022.01.13 |
| 브루트 포스법, KMP법, 보이어·무어법 (0) | 2022.01.12 |
| 힙 정렬, 도수 정렬 (0) | 2022.01.10 |
댓글