- 트리 기본 용어
1. 루트
: 트리의 가장 위쪽 노드. 트리 하나에 한 개만 존재
2. 리프
: 가장 아래쪽 노드. (= 단말 노드 or 외부 노드)
3. 비단말 노드
: 리프를 제외한 노드. (= 내부 노드)
4. 자식
: 어떤 노드와 가지가 연결되었을 때 아래쪽 노드. 노드는 자식을 몇 개라도 가질 수 O
5. 부모
: 어떤 노드와 가지가 연결되었을 때 가장 위쪽 노드. 노드의 부모는 하나뿐. 루트는 부모를 가지지 X
6. 형제
: 부모가 같은 노드
7. 조상
: 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드
8. 자손
: 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드
9. 레벨
: 루트에서 얼마나 떨어져있는지를 나타내는 척도. 가장 위쪾 노드 레벨 0, 가지가 아래로 뻗어 내려갈 때마다 레벨 += 1
10. 차수
: 각 노드가 갖는 자식의 수.
( n진 트리 : 모든 노드의 차수가 n 이하인 트리)
11. 높이
: 루트에서 리프까지의 거리. 리프 레벨의 최댓값
12. 서브트리
: 어떤 노드를 루트로 하고 그 자손으로 구성된 트리
13. 빈 트리
: 노드와 가지 X
- 순서 트리와 무순서 트리 (ordered tree, unordered tree)
형제 노드의 순서 관계가 있으면 순서트리, 없으면 무순서 트리
- 순서 트리의 검색
1. 너비 우선 검색 (breadth-first search) ( = 폭 우선 검색, 가로 검색, 수평 검색)
낮은 레벨부터 왼 -> 오 검색 후 다음 레벨로 내려감
2. 깊이 우선 검색 (depth-first search) ( = 세로 검색, 수직 검색)
1) 전위 순회 (preorder)
노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
2) 중위 순회 (inorder)
왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
3) 후위 순회 (postorder)
왼쪽 자식 -> 오른쪽 자식 -> 노드 방문
- 이진 트리 (binary tree)
노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리. 두 자식 가운데 하나 or 둘 다 존재하지 않는 노드 있어도 상관X
왼쪽 자식과 오른쪽 자식을 구분함.
- 완전 이진 트리 (complete binary tree)
:루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼 -> 오로 노드가 채워져 있는 이진 트리
1) 마지막 레벨 제외 모든 레벨에 노드가 가득 참.
2) 마지막 레벨에 한해서 왼 -> 오로 노드를 채우되 반드시 끝까지 채우지 않아도 됨
3) 높이 k인 완이트가 가질 수 있는 노드의 수 최대
2\combi{^{k+1}}-1
4) n개의 노드 저장할 수 있는 완이트의 높이 : log n
- 균형 검색 트리 (self-balancing search)
: 높이를 O(logn) 으로 제한하여 고안된 검색 트리
1) 이진 균형 검색 트리 : AVL tree, red-black tree
2) 이진이 아닌 균형 검색 트리 : B tree, 2-3 tree
- 이진 검색 트리 (binary search tree)
1) 왼쪽 서브트리 노드 키값 < 자신의 노드 키값
2) 오른쪽 서브트리 노드 키값 > 자신의 노드 키값
-> 키값 동일한 노드 복수 존재 X
- 이진 검색 트리 함수
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:
# 키가 key인 노드를 검색
p = self.root # 루트에 주목
while True:
if p is None: return None #더 이상 진행할 수 X -> 검색 실패
#근데 왜 이렇게 if 두 개로 쪼갠거지? elif 쓰면 안 되나?
if key == p.key: return p.value #검색 성공
elif key < p.key: p = p.left #key 쪽이 작으면 왼쪽 서브트리에서 검색
else: p = p.right #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)
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: 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
def dump(self, reverese = False) -> None:
def print_subtree(node: Node):
#node를 루트로 하는 서브트리의 노드를 키의 오름차순으로 출력
if node is not None:
print_subtre(node.left)
print(f'{node.key} {node.value}')
print_subtree(node.right)
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)
print_subtree_rev(self.root) if reverse else print_subtree(self.root)
1. search() 함수
def search(self, key: Any) -> Any:
# 키가 key인 노드를 검색
p = self.root # 루트에 주목
while True:
if p is None: return None #더 이상 진행할 수 X -> 검색 실패
if key == p.key: return p.value #검색 성공
elif key < p.key: p = p.left #key 쪽이 작으면 왼쪽 서브트리에서 검색
else: p = p.right #key 쪽이 크면 오른쪽 서브트리에서 검색
1) 주목하는 루트 노드 p로 설정
2) p가 None이면 검색 실패 후 종료
3) key = p : 검색 성공 후 종료
key < p : 주목 노드를 왼쪽 자식 노드로 옮김
key > p : 주목 노드를 오른쪽 자식 노드로 옮김
2. add() 함수
(노드 삽입 시 주의할 점 : 노드 삽입 후 트리의 형태가 이진 검색 트리의 조건을 유지해야 함)
삽입할 위치 찾아낸 후에 수행해야 함
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) 주목하는 루트 node로 설정
2) key = node : 삽입 실패 후 종료
key < node:
- 왼쪽 자식 노드 X : 그 자리에 노드 삽입 후 종료
- 왼쪽 자식 노드 O : 주목 노드 = 왼쪽 자식 노드
key > node:
- 오른쪽 자식 노드 X : 그 자리에 노드 삽입 후 종료
- 오른쪽 자식 노드 O : 주목 노드 = 오른쪽 자식 노드
if self.root is None:
self.root = Node(key, value, None, None)
return True
else:
return add_node(self.root, key, value)
- root 가 None일 때 :
트리가 비어있으므로 루트만으로 구성된 트리를 만들어야 함
왼/오 포인터 모두 None인 노드 생성 후 그 노드를 루트가 참조하도록 한다
- root != None:
내부 함수 add_node()를 호출해 노드 삽입
add_node() 는 node를 루트로 하는 서브 트리에 key value 삽입 (recursive)
3. remove() 함수
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: 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
- 자식 노드가 없는 노드를 삭제하는 경우
포인터 = None으로 설정하면 가리키는 노드가 없어 이검트에서 삭제됨
- 자식 노드가 1개인 노드를 삭제하는 경우
1) 삭제할 노드가 부모 노드의 왼쪽 자식인 경우 :
부모의 왼쪽 포인터가 삭제할 노드의 자식을 가리키도록 업데이트
2) 삭제할 노드가 부모 노드의 오른쪽 자식인 경우 :
부모의 오른쪽 포인터가 삭제할 노드의 자식을 가리키도록 업데이트
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
- 자식 노드가 2개인 노드를 삭제하는 경우
1) 삭제할 노드의 왼쪽 서브트리에서 키값 가장 큰 노드 검색
2) 검색한 노드를 삭제 위치로 이동
3) 옮긴 노드 삭제
옮긴 노드에 자식 X : 자식 노드가 없는 노드의 삭제에 따라 노드 삭제
옮긴 노드에 자식이 1개 : 자식 노드가 1개인 노드의 삭제에 따라 노드 삭제
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
4. dump() 함수
스캔은 중위 순회의 깊이 우선 검색
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)
print_subtree() : node를 루트로 하는 서브트리의 노드를 오름차순으로 출력하는 재귀 함수
1) 노드 1을 참조하는 왼쪽 포인터를 전달하여 print_subtree() 재귀 호출
2) 자신의 노드 데이터인 2 출력
3) 노드 4를 참조하는 오른쪽 포인터를 전달하여 print_subtree() 재귀 호출
5. min_key(), max_key() 함수
맨 끝인 None을 만날 때까지 왼 or 오 자식을 따라가는 알고리즘
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
'4학기 > 자료구조' 카테고리의 다른 글
| 후위 수식(postfix) 정리 (0) | 2022.09.30 |
|---|---|
| [자료구조] 수식 표현과 평가 (0) | 2022.06.30 |