트리 내에 다른 하위트리가 있고 하위 트리 안에 또다른 하위트리가 있는 재귀적 자료구조이다.
컴퓨터의 디렉터리 구조가 트리 구조의 대표적인 예시이다.
트리
노드 : 트리 구조를 이루는 모든 개별 데이터
루트 : 트리의 시작점이 되는 노드
부모 노드 : 자식 노드를 가진 노드 (D,E 의 부모 노드는 B)
자식 노드 : 부모 노드의 하위노드 (A의 자식 노드는 B,C)
형제노드 : 같은 부모를 가지는 노드 (F의 형제노드는 E)
리프 노드 : 자식 노드가 없는 노드 (J)
서브 트리: 루트에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리
깊이(depth)
루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. 루트 노드의 깊이는 1이며 하위 노드부터 1씩 깊어진다.
레벨(level)
같은 깊이를 가지고 있는 노드를 묶어 레벨로 표현한다. 깊이가 0인 루트 노드는 level1, 하위 노드 부터 1씩 증가된다.
높이(height)
어느 한 노드에서 리프노드까지 가장 긴 경로의 간선(Edge) 수
리프 노드의 높이 : 0
A 노드의 높이 : 3
트리 사용 이유
선형 자료구조(배열,큐,스택,연결리스트)와 달리 탐색과 삽입에서 연산 횟수를 대폭 줄일 수 있다.
이진 트리는 데이터를 반씩 제외하며 탐색하기 때문이다.
대용량 데이터에서 압도적인 속도를 낸다.
동적 할당으로 크기를 미리 정할 필요가 없어 유연한 관리가 가능하다.
배열과 트리의 차이점
선형 자료구조는 하나의 자료 뒤에 하나의 자료만 존재하지만 트리는 하나의 자료 뒤에 여러개의 자료가 올 수 있다.
이는 탐색 속도의 차이가 난다.
배열은 정적 할당, 트리는 동적 할당이다.
이진트리(Binary Tree)
이진 트리는 자식 노드가 최대 두개인 노드로 구성된 트리이다.(자식노드가 없을 수도, 1개만 있을 수도 있음)
자식노드는 왼쪽 자식노드, 오른쪽 자식 노드로 표현한다.
이진트리 종류
1. 정 이진트리(Full Binary Tree)
모든 노드가 0개 또는 2개의 자식노드를 가진 트리
정 이진트리
2. 포화 이진트리(Perfect Binary Tree)
모든 노드가 2개 자식을 가지고 리프노드가 모두 같은 레벨인 트리
포화 이진트리
3. 완전 이진트리 (Complete binary tree)
두 가지 조건을 충족해야 완전 이진 트리이다
마지막 레벨을 제외하고 모든 노드가 채워져있어야한다 (마지막 레벨의 노드는 채워져있을수도, 아닐수도)
노드는 왼쪽에서 오른쪽 방향으로 채워져야한다.(오른쪽 노드가 채워져 있는데 왼쪽 노드가 없다면 안됨)
완전 이진트리 성립
완전 이진트리 성립 X
4. 편향 이진트리(Skewed Binary Tree)
모든 노드들이 자식을 하나만 가지고 있는 트리
왼쪽만 가지고 있으면 왼쪽 편향 이진트리, 오른쪽만 가지고 있으면 오른쪽 편향 이진트리라고 한다.
왼쪽 편향 이진트리, 편향 이진 트리, 오른쪽 편향 이진트리
이진탐색트리
앞서 탐색의 속도가 빠르다고 했는데 무슨 원리로 탐색이 빨라지는지를 알기 위해선 이진탐색의 원리를 알아야한다.
이진탐색이란 정렬된 데이터 중에서 특정 값을 빠르게 찾는 알고리즘이다. (데이터를 먼저 정렬해야 함)
반으로 나누는 방식을 사용해 탐색 범위를 줄여 나간다.
트리의 루트노드는 이진 탐색에서 리스트의 중간값이 된다.
루트 노드를 기준으로 왼쪽은 루트노드보다 작은 값, 오른쪽은 큰 값을 가지고 있다.
탐색(Search)
21의 값을 탐색해보자
루트 10과 비교하면 21이 더 큼 => 오른쪽에 있겠구나
서브트리의 루트노드인 17과 비교하면 21이 더 큼 => 오른쪽에 있겠구나
21 탐색 완료
삽입(Insert)
12의 값을 추가해보자
루트 10과 비교하면 12가 더 큼 => 오른쪽에 있어야함
서브트리의 루트노드인 17과 비교하면 12가 더 작음 => 왼쪽에 있어야함
왼쪽 서브트리의 루트노드인 14와 비교하면 12가 더 작음 => 14를 부모 노드로 가지고 왼쪽의 자식노드로 연결
삭제(Delete)
21의 노드가 없다고 생각하자
삭제는 3가지의 경우가 있다.
1. 삭제할 노드의 자식 노드가 없을 때
6을 삭제한다면
부모노드 5와의 링크를 끊는다.
2. 삭제할 노드의 자식 노드가 하나일 때
17을 삭제한다면
자식노드인 14를 부모노드인 10과 바로 연결한다.
3. 삭제할 노드의 자식 노드가 두개일 때
5를 삭제한다면
오른쪽 자식노드로 이동해서 가장 작은 값을 찾는다(노드6)
6을 삭제할 5의 자리에 집어 넣는다.
트리의 정렬상태 (왼쪽 노드 > 오른쪽 노드) 를 유지해야 되기 때문
트리순회방식
특정 목적을 위해 트리의 모든 노드를 한번씩 방문하는 것을 트리순회라고 한다.
전위순회, 중위순회, 후위순회 3가지 방법이 있다.
모든 순회 방법은 왼쪽부터 오른쪽으로 조회한다.
전위 순회 (preorder traverse)
깊이 우선 순회 (DFT, Depth-First Traversal) 라고도 한다.
트리를 복사할 때 사용한다.(부모노드가 자식노드보다 먼저 생성되어야 하기 때문)
루트 노드를 방문하고
왼쪽 서브트리를 전위 순회하고
오른쪽 서브트리를 전위 순회한다.전위 순회 해보세요
루트 노드 (A) 방문 -> 왼쪽 서브트리 전위순회 (B - D - E) -> 오른쪽 서브트리 전위순회(C - F - G)
A - B -D - E - C - F - G
중위 순회 (inorder traverse)
대칭 순회(symmetric traversal)라고도 한다.
오름차순과 내림차순으로 값을 가져올 때 사용한다.
왼쪽 -> ROOT -> 오른쪽으로 순회한다.
왼쪽 서브트리를 중위순회하고
로트 노드를 방문하고
오른쪽 서브트리를 중위순회한다.
중위 순회 해보세요
왼쪽 서브트리 중위순회(D - B - E) -> 루트 노드 방문 (A) -> 오른쪽 서브트리 중위순회(F - C - G)
D - B - E - A - F - C - G
후위 순회 (postorder traverse)
루트 노드를 가장 마지막에 방문한다.
트리를 삭제하는데 사용한다.(부모 노드를 삭제하기 전 자식노드를 먼저 삭제해야하기 때문)
왼쪽 서브트리를 후위순회하고
오른쪽 서브트리를 후위순회하고
루트 노드를 방문한다.
후위순회 해보세요
왼쪽 서브트리 후위순회(D - E - B) -> 오른쪽 서브트리 후위순회(F - G - C) -> 루트노드 방문(A)D - E - B - F - G - C - A
코드 구현
Node 클래스 만들기
class Node:
def __init__(self, value):
self.value = value # 노드의 데이터
self.left = None # 왼쪽 자식 노드 가리키기
self.right = None # 오른쪽 자식 노드 가리키기
노드는 자신을 나타내는 데이터와 왼쪽/오른쪽 자식 노드를 가리키는 포인터를 가진다.
처음 노드를 만들 때는 자식이 없으므로 None 으로 초기화한다.
트리 연결하기
# 1. 노드 생성하기
root = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
# 2. 노드 연결하기 (부모와 자식 관계 설정)
root.left = node2 # 1의 왼쪽에 2
root.right = node3 # 1의 오른쪽에 3
node2.left = node4 # 2의 왼쪽에 4
생성된 트리 모양
데이터 출력하기
def print_tree_preorder(node):
# 노드가 비어있으면 돌아가기
if node is None:
return
# 1. 현재 노드의 데이터 출력
print(node.value, end=" -> ")
# 2. 왼쪽 서브트리 방문
print_tree_preorder(node.left)
# 3. 오른쪽 서브트리 방문
print_tree_preorder(node.right)
# 실행 및 결과 확인
print("전위 순회 결과:")
print_tree_preorder(root)
print("끝")
