- 전체 글 (350)
- Today
- Total
Priv's Blog
16. 트리 본문
1. 트리 (Tree)
데이터 사이의 계층 관계를 표현하는 자료구조.
노드(Node)와 가지(Edge)로 구성되며, 트리의 각 노드는 가지를 통해 다른 노드와 연결된다.
2. 트리 관련 용어
- 루트 (Root): 트리의 가장 위쪽에 있는 노드. 트리마다 1개만 존재한다.
- 리프 (Leaf): 가지가 더 이상 뻗어나갈 수 없는 노드. 단말 노드 (Terminal Node) 또는 외부 노드 (Internal Node)라고도 부른다.
- 비단말 노드 (Non-Terminal Node): 루트 노드를 포함하여 리프를 제외한 모든 노드. 내부 노드(Internal Node)라고도 부른다.
- 부모 노드 (Parent Node): 특정 노드와 가지가 연결되었을 때 가장 위쪽에 있는 노드. 노드의 부모는 1개이다. 루트 노드는 부모를 가지지 않는다.
- 자식 노드 (Child Node): 어떤 노드와 가지가 연결되었을 때 아래쪽에 있는 노드. 노드는 자식을 여러 개 가질 수 있다. 리프 노트는 자식을 가지지 않는다.
- 차수 (Degree): 각 노드가 가지는 자식의 수. 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 부른다.
- 형제 노드 (Sibling Node): 부모가 같은 노드.
- 조상 노드 (Ancestor Node): 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드.
- 자손 노드 (Descendant Node): 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드.
- 레벨 (Level): 루트에서 얼마나 멀리 떨어져 있는가를 의미한다. 루트의 레벨은 0이며, 가지가 1개씩 아래로 뻗어나갈 때마다 레벨이 1씩 증가한다.
- 높이 (Height): 루트에서 가장 멀리 있는 리프까지의 거리. 레벨의 최댓값.
- 서브 트리 (Sub Tree): 어떤 노드를 루트로 하고 그 자손으로 구성된 트리.
- 널 트리 (Null Tree): 노드와 가지가 전혀 없는 빈 트리(None Tree)
3. 순서 트리와 무순서 트리
3.1) 순서 트리 (Ordered Tree)
형제 노드의 순서 관계가 있는 트리.
3.2) 무순서 트리 (Unordered Tree)
형제 노드의 순서 관계를 구별하지 않는 트리.
4. 순서 트리의 검색
4.1) 너비 우선 검색 (BFS: Breath-First Search)
폭 우선 검색, 가로 검색, 수평 검색이라고도 부른다.
낮은 레벨부터 왼쪽에서 오른쪽으로 검색한다.
1 레벨 검색을 마치면 다음 레벨로 내려가는 방법이다.
4.2) 깊이 우선 검색 (DFS: Depth-First Search)
세로 검색, 수직 검색이라고도 부른다.
리프 노드에 도달해서 더 이상 검색할 곳이 없으면, 부모 노드로 돌아가서 다음 자식 노드를 타고 아래로 내려가며 검색한다.
깊이 우선 탐색의 스캔 과정은 아래와 같다.
5. 이진트리 (Binary Tree)
노드로 왼쪽 자식과 오른쪽 자식만 가지는 트리.
두 자식 가운데 1개 또는 2개 모두 존재하지 않아도 무관하다.
왼쪽 자식과 오른쪽 자식을 구분하는 특징이 있다.
(자식 노드가 1개만 있어도 왼쪽/오른쪽에 따라 서로 다른 트리가 된다.)
- 왼쪽 서브 트리 (Left Sub Tree): 왼쪽 자식을 루트로 하는 트리
- 오른쪽 서브 트리 (Right Sub Tree): 오른쪽 자식을 루트로 하는 트리
5.1) 완전 이진트리 (Complete Binary Tree)
루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워진 이진트리.
높이가 K인 완전 이진트리가 가질 수 있는 최대 노드의 수는 2^k+1 - 1개이다.
n개의 노드를 저장할 수 있는 완전 이진트리의 높이는 |Log2 n|
너비 우선 검색에서 스캔하는 순서대로 각 노드에 0, 1, 2, ~ 의 값을 부여하면 배열에 저장하는 인덱스와 1:1 대응이 가능하다.
5.2) 이진 검색 트리 (Binary Search Tree)
모든 노드가 아래 조건을 만족하는 이진트리.
- 왼쪽 서브 트리 키 값 < 자신의 노드 키 값
- 오른쪽 서브 트리 키 값 > 자신의 노드 키 값
- 키 값이 같은 노드는 복수로 존재할 수 없다.
중위 순회에 따른 깊이 우선 검색 시, 키 값을 오름차순으로 나열할 수 있다.
6. 이진 검색 트리의 특성
구조가 단순하고 노드 삽입이 쉽다.
이진 검색과 비슷한 방식으로 빠른 검색이 가능하다.
중위 순회의 깊이 우선 검색을 사용해서 노드 값을 오름차순으로 나열할 수 있다.
7. 이진 검색 트리의 검색
7.1) 값이 트리에 존재하는 경우
키 값이 3인 노드를 이진 검색 트리에서 검색하려고 한다.
이때 트리에 해당 키 값이 존재하는 경우를 가정한다.
7.2) 값이 트리에 존재하지 않는 경우
키 값이 8인 노드를 이진 검색 트리에서 검색하려고 한다.
이때 트리에 해당 키 값이 존재하지 않는 경우를 가정한다.
7.3) 이진 검색 트리의 검색 알고리즘
루트에 주목하고, 주목한 노드는 p라고 설정한다.
p가 None이면 검색에 실패하므로 알고리즘을 종료한다.
검색하는 키(key)와 주목 노드의 키(p.key)를 비교한다.
- key == p.key: 검색 성공 (종료)
- key < p.key: 주목 노드를 왼쪽 자식 노드로 변경
- key > p.key: 주목 노드를 오른쪽 자식 노드로 변경
위 과정을 반복한다.
8. 이진 검색 트리의 삽입
키 값이 1인 노드를 삽입한 뒤, 동일한 트리에 키 값이 5인 노드를 삽입하는 과정을 살펴보자.
8.1) 이진 검색 트리의 삽입 알고리즘
루트에 주목하고, 주목 노드를 node라고 설정한다.
삽입하려는 키(key)와 주목 노드의 키(p.key)를 비교한다.
- key == node.key: 검색 성공 (종료)
- key < node.key: 왼쪽 자식 노드가 없으면 그 자리에 노드를 삽입하고 종료한다. (자식 노드가 없으면 주목 노드를 왼쪽 자식 노드로 변경)
- key > p.key: 오른쪽 자식 노드가 없으면 그 자리에 노드를 삽입하고 종료한다. (자식 노드가 없으면 주목 노드를 오른쪽 자식 노드로 변경)
위 과정을 반복한다.
9. 이진 검색 트리의 삭제
9.1) 자식 노드가 없는 노드(리프)를 삭제하는 경우
삭제할 노드가 부모 노드의 왼쪽 자식이면, 부모의 왼쪽 포인터를 None으로 업데이트한다.
삭제할 노드가 부모 노드의 오른쪽 자식이면, 부모의 오른쪽 포인터를 None으로 업데이트한다.
9.2) 자식 노드가 1개인 노드를 삭제하는 경우
삭제할 노드가 부모 노드의 왼쪽 자식이면, 부모의 왼쪽 포인터가 삭제할 노드의 자식을 가리키도록 업데이트한다.
삭제할 노드가 부모 노드의 오른쪽 자식이면, 부모의 오른쪽 포인터가 삭제할 노드의 자식을 가리키도록 업데이트한다.
9.3) 자식 노드가 2개인 노드를 삭제하는 경우
삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색한다.
검색할 노드를 삭제 위치로 옮긴다. (검색한 노드의 데이터를 삭제할 노드 위치에 복사)
옮긴 노드를 삭제한다.
옮긴 노드에 자식이 없는 경우와 자식이 1개 있는 경우를 나눠서 처리한다.
10. 이진 검색 트리 구현하기
10.1) Node 클래스
Node 클래스의 필드는 다음과 같다.
- key: 키 (임의의 형)
- value: 값 (임의의 형)
- left: 왼쪽 자식 노드에 대한 참조 (왼쪽 포인터)
- right: 오른쪽 자식 노드에 대한 참조 (오른쪽 포인터)
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
10.2) BinarySearchTree 클래스
이진 검색 트리 클래스
BinarySearchTree 클래스의 필드는 다음과 같다.
- root: 루트에 대한 참조를 유지하는 필드
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
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
수고하셨습니다!
'Dev. Study Note > Algorithm (Python)' 카테고리의 다른 글
| 17. 동적 계획법 (0) | 2022.01.25 |
|---|---|
| 15. 리스트 (0) | 2022.01.22 |
| 14. 정렬 알고리즘 (0) | 2022.01.21 |
| 13. 하노이의 탑과 8 Queens (0) | 2022.01.21 |
| 12. 재귀 알고리즘 (0) | 2022.01.19 |
