트리형 자료구조란?
트리형 자료구조란 node와 edge를 통해 데이터 간의 계층관계를 표현하는 자료구조이다.
루트(root) : 가장 위쪽에 있는 노드
리프(leaf, terminal node, external node) : 가장 아래쪽의 있는 노드
child : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드
parent : 어떤 노드와 가지가 연결되었을 때 위쪽 노드, 노드의 부모는 하나뿐이며 루트는 부모노드 X
sibling : 부모가 같은 노드(형제)
ancestor : 부모를 따라가며 만나는 모든 노드(조상)
descendant : 자식을 따라가면 만나는 모든 노드(자손)
level : 루트에서부터 얼마나 멀리 떨어져 있는지를 나타냄. 루트의 레벨은 0, 가지가 하나씩 아래로 뻗을때마다 1씩 증가
degree : 차수, 각 노드가 갖는 자식의 수, 모든 노드의 자식이 2개 이하면 이진트리
height : 리프 레벨의 최댓값, 높이
subtree : 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리
Preorder Traversal(전위 순회) (= 깊이 우선 순회, DFT(=Depth First Traversal)
1) Root 노드 방문
2) 왼쪽 서브 트리를 전위 순회
3. 오른쪽 서브 트리를 전위 순회
Postorder Traversal
1) 왼쪽 서브 트리 후위 순회
2) 오른쪽 서브 트리 후위 순회
3) Root 노드 방문
이진트리와 이진검색 트리
노드가 left child와 right child만을 갖는 트리
완전 이진트리
: 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진트리라고 함.
왼쪽 서브트리 노드이 키값은 자신으 ㅣ노드 키값보다 작아야 하며, 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 함.
높이가 k인 완전 이진트리가 가질 수 있는 노드의 수는 최대 2^k+1개 이므로 n개의 노드를 저장할 수 있는 완전 이진트리의 높이는 log n
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 # 검색 실패
if key == p.key: # key와 노드 p의 키가 같으면
return p.value # 검색 성공
elif key < p.key: # key 쪽이 작으면
p = p.left # 왼쪽 서브 트리에서 검색
else: # key 쪽이 크면
p = p.right # 오른쪽 서브 트리에서 검색
# Do it! 실습 9-1[C]
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: # 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:
self.root = p.right
elif is_left_child:
parent.left = p.right # 부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
else:
parent.right = p.right # 부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
elif p.right is None: # p에 오른쪽 자식이 없으면
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: # 가장 큰 노드 left를 검색
parent = left
left = left.right
is_left_child = False
p.key = left.key # left의 키를 p로 이동
p.value = left.value # left의 데이터를 p로 이동
if is_left_child:
parent.left = left.left # left를 삭제
else:
parent.right = left.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