To-do List
✅ 백준 풀기 | 1110 더하기 사이클, 1182 부분수열의 합
✅ Do it! ~ 읽고 구현 연습 #자료구조 | 이진 검색 트리
🔴 Delayed
☑️ 정답 봤던거 직접 코딩해보기 | 사냥꾼, 하노이탑, nQueen
☑️ Do it! ~ 읽고 구현 연습 #자료구조 | 큐, 스택
☑️ Do it! ~ 읽고 구현 연습 #정렬 | 퀵 정렬(피봇 3선발), 병합 정렬, 힙 정렬
☑️ 슈도 코드 변환 | 버블 정렬, 이분 탐색, 백트래킹
배운 것들
딕셔너리 자료 입력
딕셔너리에 tree[root] = left, right 이렇게 하면 어떻게 입력되는거임
딕셔너리에 tree[root] = left, right처럼 입력하면, tree 딕셔너리에서 root 키는 튜플 (left, right)를 값으로 가지게 됩니다. 이는 각 노드가 left와 right 자식을 가지는 트리 구조를 나타내기 위한 방법입니다.
left: Node = None
left: Node = None 매개변수는 Node 타입의 값을 받으며, 기본값은 None입니다. 즉, left 매개변수는 노드의 왼쪽 자식을 나타내며, 초기화 시에 명시적으로 제공되지 않으면 None으로 설정됩니다.
이진 검색 트리 key, value 차이
이진 검색 트리에서 key랑 value랑 뭐가 다름
이진 검색 트리(BST)에서 key와 value는 다음과 같이 구분됩니다:
Key (키):
- 정의: 키는 노드를 트리에 배치하고 검색할 때 사용하는 기준 값입니다. 이진 검색 트리에서는 키를 기준으로 노드를 정렬하고, 검색, 삽입, 삭제 등의 연산을 수행합니다.
- 역할: 키는 노드의 위치를 결정하며, 트리의 구조를 정의합니다. 예를 들어, 키를 기준으로 노드를 왼쪽 서브트리나 오른쪽 서브트리에 배치합니다.
- 조건: BST의 특성에 따라 왼쪽 자식 노드의 키는 부모 노드의 키보다 작고, 오른쪽 자식 노드의 키는 부모 노드의 키보다 커야 합니다.
Value (값):
- 정의: 값은 키와 연관된 데이터를 의미합니다. 키와 값은 함께 저장되며, 키를 통해 값을 찾을 수 있습니다.
- 역할: 값은 키와 연관된 실제 데이터를 저장합니다. 예를 들어, 데이터베이스에서 레코드를 찾기 위해 키를 사용하고, 해당 레코드의 값은 실제 데이터가 됩니다.
- 조건: 값은 키와 독립적으로 어떤 데이터든 될 수 있습니다. 값은 BST의 구조에 영향을 주지 않습니다.
Do it! 자료구조와 함께 배우는 알고리즘 입문
9-1 트리 구조
트리의 구조와 관련 용어
- 트리 : 노드(node) + 가지(edge)
- 루트 : 맨 위에 있는 노드
- 리프 : 맨 아래에 있는 노드. [ = 단말 노드(terminal node), 외부 노드(external node) ]
- 비단말 노드 : 리프를 제외한 노드. [ = 내부 노드(internal node) ]
- 형제 : 부모가 같은 노드
- 조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드
- 자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드
- 레벨 : 루트에서 얼마나 멀리 떨어져 있는지 (루트는 0)
- 차수 : 각 노드가 갖는 자식의 수
- 높이 : 루트에서 가장 멀리 있는 리프까지의 거리
순서 트리와 무순서 트리
- 순서 트리(ordered tree): 형제 노드의 순서 관계가 있음
- 무순서 트리(unordered tree): 형제 노드끼리 순서 구분 없음
순서 트리의 검색
- 너비 우선 검색(breadth-first search): 낮은 레벨부터 왼쪽에서 오른쪽으로 검색
- 폭 우선 검색, 가로 검색, 수평 검색이라고도 한다
- 같은 레벨에 검색하지 않은 노드가 있다면 먼저 검색한다
- 완전 이진 트리를 리스트로 구현했다면 인덱스 0부터 끝까지 +1하면서 순회 검색
- 깊이 우선 검색(depth-first search): 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로
- 세로 검색, 수직 검색이라고도 한다
- 아래 레벨 노드에 검색 안한게 있으면 일단 아래로 내려갔다온다
전위, 중위, 후위 순회
전위 순회
노드 방문 → 왼쪽 자식 → 오른쪽 자식
중위 순회
왼쪽 자식 → 노드 방문 → 오른쪽 자식
후위 순회
왼쪽 자식 → 오른쪽 자식 → 노드 방문
https://m.blog.naver.com/rlakk11/60159303809
- 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
- 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
- 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문
- 층별 순회(level order traverse) : 위쪽 node들 부터 아래방향으로 차례로 방문
- 전위 순회는 뿌리->왼쪽 자식->오른쪽 자식 순
- 중위 순회는 왼쪽자식-> 뿌리-> 오른쪽 자식
- 후위 순회는 왼쪽자식->오른쪽 자식-> 뿌리
- 층별 순회는 그냥 노드의 순서대로
왜 이렇게 나눠놓은거임 그냥 하나로만 통일하면 되잖아 배우는 사람 헷갈리게 왜
이진 트리에서 다양한 순회(traversal) 방법이 존재하는 이유는 각각의 순회 방법이 트리의 구조나 요소를 다르게 접근하고 처리하는 방식에 따라 다른 용도와 목적을 가지고 있기 때문입니다. 이들 순회 방법은 다양한 알고리즘과 문제 해결에 유용하게 사용됩니다. 각각의 순회 방법을 통해 트리 구조에서 필요한 데이터를 효율적으로 추출하고, 특정 작업을 수행할 수 있습니다.
전위 순회(Preorder Traverse)
방문 순서: 뿌리(root) -> 왼쪽 하위 트리 -> 오른쪽 하위 트리
- 용도:
- 트리의 구조를 복제하는 알고리즘에서 유용합니다.
- 루트 노드를 가장 먼저 방문하므로, 트리의 전체 구조를 빠르게 파악할 수 있습니다.
- 예를 들어, 표현식 트리에서 전위 순회는 접두 표기법(prefix notation)을 만드는데 사용됩니다.
중위 순회(Inorder Traverse)
방문 순서: 왼쪽 하위 트리 -> 뿌리(root) -> 오른쪽 하위 트리
- 용도:
- 이진 탐색 트리(BST)에서 중위 순회는 노드를 오름차순으로 정렬된 순서로 방문합니다.
- 트리에서 순서가 있는 데이터를 출력하거나, 정렬된 리스트로 변환할 때 사용됩니다.
- 예를 들어, 데이터베이스 쿼리에서 중위 순회는 정렬된 결과를 반환하는데 유용합니다.
후위 순회(Postorder Traverse)
방문 순서: 왼쪽 하위 트리 -> 오른쪽 하위 트리 -> 뿌리(root)
- 용도:
- 하위 트리를 먼저 방문하고, 루트 노드를 나중에 방문하므로, 트리의 삭제나 정리 작업에 유용합니다.
- 예를 들어, 디렉토리와 파일 시스템에서 디렉토리를 삭제할 때, 하위 디렉토리와 파일을 먼저 삭제한 후, 상위 디렉토리를 삭제하는 경우가 있습니다.
층별 순회(Level Order Traverse)
방문 순서: 위에서 아래로, 왼쪽에서 오른쪽으로 노드를 방문
- 용도:
- 트리의 레벨 별로 데이터를 처리할 때 유용합니다.
- BFS(너비 우선 탐색)를 사용하여 트리의 레벨 별로 탐색하므로, 특정 레벨의 노드를 찾거나, 레벨 별 통계를 계산하는 데 사용됩니다.
- 예를 들어, 그래프 알고리즘에서 최단 경로를 찾는 알고리즘은 BFS를 기반으로 합니다.
요약
- 다양한 목적: 각 순회 방법은 특정한 문제를 해결하는데 최적화되어 있습니다. 예를 들어, 정렬된 데이터를 얻고 싶다면 중위 순회를 사용하고, 트리의 복사를 원한다면 전위 순회를 사용합니다.
- 효율성: 특정 작업을 수행할 때, 어떤 순회 방법을 사용하는지가 작업의 효율성에 큰 영향을 미칠 수 있습니다.
- 데이터 구조의 유연성: 다양한 순회 방법을 통해 다양한 형태의 트리 구조를 처리하고, 필요한 데이터를 추출할 수 있습니다.
https://www.youtube.com/watch?v=WLvU5EQVZqY
어려워서 이해 못했는데 인도인이 알려줬다.
일단 탐색 순서는 그려진 대로의 경로가 고정.
- 전위 순회 : 처음 만난 노드를 바로 기록
- 중위 순회 : 두번 만난 노드만 기록
- 후위 순회 : 세번 만난 노드만 기록
chatgpt가 만들어준 예제 코드
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
# 전위 순회
def preorder(root):
if root:
print(root.val, end=' ')
preorder(root.left)
preorder(root.right)
# 중위 순회
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
# 후위 순회
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=' ')
# 층별 순회
from collections import deque
def level_order(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 트리 생성 및 순회 예제
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("전위 순회:")
preorder(root)
print("\n중위 순회:")
inorder(root)
print("\n후위 순회:")
postorder(root)
print("\n층별 순회:")
level_order(root)앞으로 이거 기반으로 구현하면 될듯
print()의 위치를 봤더니
대놓고 첫번째, 두번째, 세번째에 있어서
전위, 중위, 후위 순회의 이름 납득됨
코드에서 이해할 땐 전위, 중위, 후위로
순서를 이해할 땐 1번째, 2번째, 3번째 방문으로 이해하면 될듯
09-2 이진 트리와 이진 검색 트리
이진 트리
가지 2개까지만 가질 수 있는 트리.
어렵게 말하면, 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리.
완전 이진 트리
대충 딱 보면 빈틈 없이 꽉 차있는 트리
어렵게 말하면, 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리
- 마지막 레벨을 제외하고 모든 레벨에 노드가 가득 차 있다.
- 마지막 레벨에 한해서 반드시 끝까지 채우지 않아도 된다.
균형 검색 트리
- 이진 검색 트리는 키의 오름차순으로 노드가 삽입되면 트리의 높이가 깊어지는 단점이 있다.
- 예를 들어, 1, 2, 3, 4, 5 순으로 노드를 삽입하면 직선 모양이 된다.
- 균형 검색 트리 : 높이를 O(log n)으로 제한하여 고안된 검색 트리
- 이진 균형 검색 트리 : AVL 트리, 레드블랙 트리 등
- (이진 아닌) 균형 검색 트리 : B 트리, 2-3 트리
이진 검색 트리
이진 검색 트리는 모든 노드가 다음 조건을 만족해야 함.
- 왼쪽 서브트리의 노드의 키값은 자신의 노드 키값보다 작아야 한다.
- 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 한다.
따라서 키값이 같은 노드는 복수로 존재하면 안됨.
모든 키값은 고유해야 함. 안 그럼 규칙 위배함.
- 구조가 단순하다.
- 중위 순회의 깊이 우선 검색을 통하여 노드값을 오름차순으로 얻을 수 있다.
- 이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있다.
- 노드를 삽입하기 쉽다.
# 이진 검색 트리 구현하기
from __future__ import annotations
from typing import Any, Type
class Node:
"""이진 검색 트리의 노드"""
def __init__(self, key: Any, value: Any,
left: Node = None, right: Node = None):
"""생성자(constructor)"""
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:
"""키가 key인 노드를 검색"""
p = self.root # 루트에 주목
while True:
if p is None: # 더 이상 진행할 수 없으면
return None # 검색 실패
if key == p.key: # key와 노드 p의 키가 같으면
return p.value # 검색 성공
elif key < p.key: # key 쪽이 작으면
p = p.left # 왼쪽 서브트리에서 검색
else: # key 쪽이 크면
p = p.right # 오른쪽 서브트리에서 검색노드 검색할 때 4가지 경우
현재 주목 중인 노드가
(1) None이면 : 검색 실패
(2) 찾을 값과 같으면 : 검색 성공
(3) key 쪽이 작으면 : 왼쪽 자식 노드로 넘어가기
(4) key 쪽이 크면 : 오른쪽 자식 노드로 넘어가기
def add(self, key: Any, value: Any) -> bool:
"""키가 key이고 값이 value인 노드를 삽입"""
def add_node(node: Node, key: Any, value: Any) -> None:
"""node를 루트로 하는 서브트리에 키가 key이고 값이 value인 노드를 삽입"""
if key == node.key:
return False # key가 이진 검색 트리에 이미 존재
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)
필요한 질문
1. 루트 노드가 있는지
2. 부모 노드와 자식 노드의 키를 비교
3. 왼쪽/오른쪽 자식이 있는가?
class Node:
def __init__(self, key, value, left=None, right=None):
self.key = key
self.value = value
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def remove(self, key: Any) -> bool:
"""키가 key인 노드를 삭제"""
p = self.root # 스캔 중인 노드를 담음 (루트에서 스캔 시작)
parent = None # 스캔 중인 노드의 부모 노드
is_left_child = True # p는 parent의 왼쪽 자식 노드인지 확인
while True:
if p is None: # 더 이상 진행할 수 없으면
return False # 그 키는 존재하지 않음
if key == p.key: # key와 노드 p의 키가 같으면
break
else:
parent = p # 가지를 내려가기 전에 부모를 설정
if key < p.key: # key 쪽이 작으면
is_left_child = True # 여기서 내려가는 것은 왼쪽 자식
p = p.left # 왼쪽 서브트리에서 검색
else: # key 쪽이 크면
is_left_child = False # 여기서 내려가는 것은 오른쪽 자식
p = p.right # 오른쪽 서브트리에서 검색
if p.left is None: # p에 왼쪽 자식이 없으면
if p is self.root: # p가 루트라면
self.root = p.right # 루트를 원래 루트의 오른쪽 자식으로 바꿈
elif is_left_child: # p가 부모의 왼쪽 노드라면
parent.left = p.right # 부모의 왼쪽 노드는 주목 노드의 오른쪽 노드
else: # p가 부모의 오른쪽 노드라면
parent.right = p.right # 부모의 오른쪽 노드는 주목 노드의 오른쪽 노드
elif p.right is None: # p에 오른쪽 자식이 없으면
if p is self.root: # p가 루트라면
self.root = p.left # 루트를 원래 루트의 왼쪽 자식으로 바꿈
elif is_left_child: # p가 부모의 왼쪽 노드라면
parent.left = p.left # 부모의 왼쪽 노드는 주목 노드의 왼쪽 노드
else: # p가 부모의 오른쪽 노드라면
parent.right = p.left # 부모의 오른쪽 노드는 주목 노드의 왼쪽 노드
else: # p에 왼쪽 자식도 있고 오른쪽 자식도 있으면
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):
"""node를 루트로 하는 서브트리의 노드를 키의 오름차순으로 출력"""
if node is not None: # 노드가 있다면 (리프의 자식을 만난게 아니라면)
print_subtree(node.left) # 왼쪽 서브트리를 오름차순으로 출력
print(f'{node.key} {node.value}') # node를 출력
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이진 검색 트리는
왼쪽 자식은 자신보다 작고, 오른쪽 자식은 자신보다 크니까
왼쪽으로 쭉 가면 최솟값이 나오고, 오른쪽으로 쭉 가면 최댓값이 나온다.
def print_subtree_rev(node: Node):
"""node를 루트로 하는 서브트리의 노드를 키의 내림차순으로 출력"""
if node is not None:
print_subtree_rev(node.right)
print(f'{node.key} {node.value}')
print_subtree_rev(node.left)dump 함수에서 key 오름차순이 아니라 내림차순으로 출력하고 싶으면
right랑 left 순서만 바꾸면 된다.
백준
5639 이진 검색 트리
일단 여기까지 접근 해봤다.
2번 접근 방식도 살짝 생각해보면 좋을듯.
