용어
-
node(노드): 트리에서 원소에 해당하는 부분
-
edge(가지): 트리에서 연결 관계를 나타내는 부분
-
root(루트): 트리의 가장 위쪽에 있는 노드
-
leaf(리프) = terminal node(단말노드) = external node(외부노드): 가장 아래쪽에 위치한 노드
-
non-terminal node(비단말노드) = internal node(내부노드): 리프를 제외한 노드
-
child(자식): 두 노드가 가지로 연결되었을 때 아래쪽 노드
-
parent(부모): 두 노드가 가지로 연결되었을 때 위쪽 노드, 모든 노드의 부모는 한개 뿐임
-
sibling(형제): 부모가 같은 노드들
-
ancestor(조상): 한 노드에서 위쪽 가지를 따라가면 만나는 모든 노드들
-
descendant(자손): 한 노드에서 아래쪽 가지를 따라가면 만나는 모든 노드들
-
level(레벨): 루트에서 얼마나 멀리 떨어져 있는지를 나타낸 것, 루트의 레벨은 0
-
degree(차수): 노드가 갖는 자식의 수
-
n진트리: 모든 노드의 차수가 n이하인 트리
-
height(높이): 리프 레벨의 최댓값
-
subtree(서브트리): 트리의 일부로, 한 노드를 루트로 다시 구성되는 트리
-
None tree(빈트리) = null tree(널트리): 노드와 가지가 전혀 없는 트리
-
ordered tree(순서트리): 형제 노드의 순서 관계가 있는 트리(ex 작은값이 왼쪽)
-
unordered tree(무순서트리): 형제 노드의 순서 관계가 없는 트리
-
Breadth-First-Search(너비우선검색=폭우선검색=가로검색=수평검색): 낮은 레벨의 노드부터 검색하고, 한 레벨 검색이 끝나면 다음 레벨로 내려가는 방법
-
Depth-First-Search(깊이우선검색=세로검색=수직검색): 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하고, 리프에 도달하면 일단 부모 노드로 돌아가 다른 자식 노드 검색
-
preorder(전위순회): 노드방문 -> 왼쪽자식 -> 오른쪽자식 순으로 진행
-
inorder(중위순회): 왼쪽자식 -> 노드방문 -> 오른쪽자식 순으로 진행
-
postorder(후위순회): 왼쪽자식 -> 오른쪽자식 -> 노드방문 순으로 진행
-
binary tree(이진트리): 모든 노드의 차수가 2 이하인 트리
-
left subtree(왼쪽서브트리): 이진트리에서 왼쪽 자식을 루트로 하는 서브트리
-
right subtree(오른쪽서브트리): 이진트리에서 오른쪽 자식을 루트로 하는 서브트리
-
complete binary tree(완전이진트리): 루트부터 아래쪽으로, 왼쪽에서 오른쪽으로 노드가 모두 채워져 있는 이진트리, 단 리프에서는 모든 노드가 채워지지 않아도 됨
=> N개의 노드를 저장할 수 있는 완전이진트리의 높이는 logN -
binary search tree(이진검색트리): 모든 노드가 아래 두 조건을 만족하는 트리
=> 1. 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작다
=> 2. 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 크다
=> 구조가 단순함
=> 중위순회의 DFS를 통해 노드값을 오름차순으로 얻을 수 있음
=> 아주 빠르게 검색 가능
=> 노드를 삽입하기 쉬움
실습
이진검색트리
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
is_left_child = key < p.key
p = p.left if key < p.key else 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(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
tree = BinarySearchTree()
while True:
option = int(input("(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료\n"))
if option == 1:
key = int(input("삽입할 키(자연수)를 입력하세요: "))
value = input("삽입할 값(문자)를 입력하세요: ")
if not tree.add(key, value):
print("이미 등록된 키입니다.")
elif option == 2:
if tree.remove(int(input("삭제할 키(자연수)를 입력하세요: "))):
print("삭제 완료")
else:
print("없는 키입니다.")
elif option == 3:
result = tree.search(int(input("검색할 키(자연수)를 입력하세요: ")))
if result:
print(f"해당 키에 해당하는 값은 '{result}' 입니다.")
else:
print("없는 키입니다.")
elif option == 4:
tree.dump()
elif option == 5:
print(f"키의 최소값은 {tree.min_key()}, 최대값은 {tree.max_key()}입니다.")
elif option == 6:
break
# 실행결과 ==========================================
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
1
삽입할 키(자연수)를 입력하세요: 92
삽입할 값(문자)를 입력하세요: 영호
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
1
삽입할 키(자연수)를 입력하세요: 49
삽입할 값(문자)를 입력하세요: 민철
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
1
삽입할 키(자연수)를 입력하세요: 33
삽입할 값(문자)를 입력하세요: 순자
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
1
삽입할 키(자연수)를 입력하세요: 112
삽입할 값(문자)를 입력하세요: 민식
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
1
삽입할 키(자연수)를 입력하세요: 7
삽입할 값(문자)를 입력하세요: 민지
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
4
7 민지
33 순자
49 민철
92 영호
112 민식
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
5
키의 최소값은 7, 최대값은 112입니다.
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
3
검색할 키(자연수)를 입력하세요: 33
해당 키에 해당하는 값은 '순자' 입니다.
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
3
검색할 키(자연수)를 입력하세요: 17
없는 키입니다.
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
2
삭제할 키(자연수)를 입력하세요: 112
삭제 완료
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
4
7 민지
33 순자
49 민철
92 영호
(1)삽입 (2)삭제 (3)검색 (4)덤프 (5)키의범위 (6)종료
6정리
책의 마지막 부분인 트리에 대한 정리가 끝났다.
알고리즘 문제를 풀다가 우선순위 힙을 구현하는 과정이
이부분과 연관있어보여 8장 연결리스트보다 먼저 정리한다.
내용상으로는 어렵지 않았지만,
이를 밑바닥부터 혼자 구현해보라고 하면 할 수 있을지 잘 모르겠다.
손에 익혀 실제 구현문제가 나왔을때 써먹을 수 있게 해야겠다.
