트리(Tree)
Stack, Queue 등과는 다르게 계층적 구조를 표현할 수 있는 비선형적인 자료구조이다. (가계도와 같은 표현)
- 트리의 구성 요소 및 용어
- Node (노드) : 트리를 구성하고 있는 각각의 요소
- root node : 부모가 없는 최상위 노드
- leaf node : 자식이 없는 노드 (=terminal node, 단말 노드)
- internal node : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다. (비단말 노드)
- Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
- Size (크기) : 트리에 포함된 모든 노드의 개수
- depth (깊이) : 루트 노드로부터의 거리
- height (높이) : 깊이 중 최댓값
- degree (차수) : 각 노드의 (자식 방향) 간선 개수
- Node (노드) : 트리를 구성하고 있는 각각의 요소
기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개가 된다.
이진 트리 (Binary Tree)
부모 밑의 자식 노드 개수를 2개로 제한하는 가장 간단한 형태의 트리이다.
루트 노드를 중심으로 두개의 서브트리로 나뉘고 나뉘어진 두 서브트리도 각각 이진 트리이어야 한다.
트리의 각 층별로 숫자를 매기고 Level(레벨)이라고 한다.
레벨은 0부터 시작하고 루트노드의 레벨은 0이다.
(루트를 1부터 시작하는 경우도 있으나 일반적으로는 0부터 시작한다.)
- Perfect Binary Tree (포화 이진 트리)
모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다.
-> 모든 리프 노드의 높이가 같고 리프 노드가 아닌 노드는 모두 2개의 자식을 갖는다. 이진 트리에서 리프 높이의 최대치가 n일 때 가장 많이 존재할 수 있는 노드의 수는 2n-1개인데 포화 이진 트리는 이 개수를 모두 채운 이진 트리라고도 볼 수 있다. 또한, 모든 포화 이진 트리는 정 이진 트리이다. - Complete Binary Tree (완전 이진 트리)
위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다.
-> 모든 리프노드의 높이가 최대 1 차이가 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 있는 이진트리이다. 다시 말해 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태이다. 포화 이진 트리는 완전 이진 트리의 부분집합이다. 단, 포화 이진 트리가 아닌 완전 이진 트리는 정 이진 트리일 수도 있고 아닐 수도 있다. - Full Binary Tree (정 이진 트리)
모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가리켜 정 이진 트리라고 한다.
배열로 구성된 Binary Tree는 노드의 개수가 n 개이고 root가 0이 아닌 1에서 시작할 때, i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.
트리의 순회 (Tree Traversal)
트리 자료구조에 포함된 노드를 특정 방법으로 한번씩 방문하는 방법
-> 트리의 정보를 시각적으로 확인할 수 있다.
- 전위 순회(pre-order traverse): 루트를 먼저 방문, (자신 > 왼쪽 > 오른쪽)
- 중위 순회(in-order traverse): 왼쪽 자식을 방문하고 루트를 방문 (왼쪽 > 자신 > 오른쪽)
- 후위 순회(post-order traverse): 오른쪽 자식을 방문하고 루트를 방문 (왼쪽 > 오른쪽 > 자신)
- 레벨 순서 순회(Level-order traversal): 너비 우선 순회(Breadth-First traversal)라고도 한다. 노드를 레벨 순서로 방문하는 순회 방법. 위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면 레벨 순서 순회는 큐를 활용해 구현할 수 있다.
위의 트리를 순회 결과
In-order: 1 3 4 6 7 8 10 13 14
Pre-order: 8 3 1 6 4 7 10 14 13
Post-order: 1 4 7 6 3 13 14 10 8
Level-order: 8 3 10 1 6 14 4 7 13
이진 탐색 트리 (Binary Searych Tree)
이진 탐색이 동작할 수 있도록 고안된 자료구조로 이진 트리의 일종이다.
- 특징 : 왼쪽 자식노드 < 부모노드 < 오른쪽 자식노드
- 부모노드보다 왼쪽 자식 노드가 작고, 오른쪽 자식 노드가 크다.
- 탐색 과정
- 루트 노드를 방문하여 탐색을 진행.
- 현재 노드와 찾는 원소 값을 비교.
- 찾는 원소의 대소 관계에 따라 작으면 왼쪽 크면 오른쪽을 방문
- 반복하여 비교 > 탐색 후 종료
이진 트리의 탐색은 O(log n)의 시간 복잡도를 갖는다. 하지만 이진 탐색트리는 한쪽에만 노드가 추가되는 편향트리(Skewed Tree)가 될 가능성이 있다. 이 경우에는 성능에 영향을 미치게 되고 worst case에서 시간 복잡도는 O(n)이 된다.
효율적인 이진 탐색을 하기 위해서는 트리구조의 좌우 균형이 잡혀있어야 한다.
배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다. 이를 해결하기 위해 Rebalancing 기법이 등장한다. (균형을 잡기 위한 트리 구조의 재조정) 이 기법을 구현한 트리에는 여러 종류가 존재하는데 그 중에서 하나가 Red-Black Tree이다.
Binary Heap
Red Black Tree
Zed0202 블로그
...
이진 트리의 코드 구현
class Node:
def __init__(self,key):
self.key = key
self.parent = None
self.left = None
self.right = None
def __str__(self): # print문의 출력값
return str(self.key)
'''
a = Node(6)
b = Node(9)
c = Node(1)
d = Node(5)
a.left = b
a.right = c
b.parent = a
b.right = d
a.parent = a
'''- 이진트리 순회
class Node:
def __init__(self,key):
self.key = key
self.parent = None
self.left = None
self.right = None
# 각 함수를 재귀적으로 호출한다.
def preorder(self):
if self != None:
print(self.key) ### MLR
if self.left:
self.left.preorder()
if self.right:
self.right.preorder()
def inorder(self):
if self != None:
if self.left:
self.left.inorder()
print(self.key) ### LMR
if self.right:
self.right.inorder()
def postorder(self):
if self != None:
if self.left:
self.left.postorder()
if self.right:
self.right.postorder()
print(self.key) ### LRM
