트리란?
비선형적 데이터 구조중 하나
구조의 계층적 속성을 그래프의 형태로 나타내는 방법
root : 부모가 없는 노드, 트리에는 최대 한 개의 루트 노드가 있을 수 있습니다.
edge : 부모로부터 자식에게 이어지는 연결 선
siblings : 같은 부모를 가지는 노드들
level : 주어진 깊이(depth)의 모든 노드의 집합
leaf : 자식이 없는 노드
depth : 루트에서 어떤 노드 까지의 경로의 길이
height : 루트로부터 가장 깊은 노드까지의 경로의 길이
size : 자신을 포함 자식 노드의 수
이진트리
각 노드가 자식이 없거나, 한 개 혹은 두 개의 자식을 가지는 트리
빈 트리 역시 유효한 이진 트리
이진 트리는 루트와 왼쪽 서브 트리, 오른쪽 서브 트리라고 불리는 두 개의 분리된 이진 트리로 구성되어 있다고 볼 수 있습니다.
종류
엄격한(strict) 이진 트리
모든 노드가 두 개의 자식을 가지거나 자식이 없을 때
포화(full) 이진 트리
모든 노드가 두 개의 자식을 가지고 리프 노드가 같은 레벨에 있을 때
완전(complete) 이진 트리
완전 이진트리에서는 루트부터 시작해서 각 노드에 번호를 매기면 완전한 순열을 얻을 수 있습니다.
이진 트리의 높이를 h라고 했을 때, 모든 리프 노드가 높이 h 나 h-1에 있고, 순열에서 빠진 숫자가 없을 때
구조
탐색
Preorder
자기 자신 → 왼쪽 자식 → 오른쪽 자식
Inorder
왼쪽 자식 → 자기 자신 → 오른쪽 자식
Postorder
왼쪽 자식 → 오른쪽 자식 → 자기 자신
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def preorder(node):
if node:
print(node.data, end=" ")
preorder(node.left)
preorder(node.right)
def inorder(node):
if node:
inorder(node.left)
print(node.data, end=" ")
inorder(node.right)
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.data, end=" ")
이진 검색 트리
Binary Search Tree
이 tree의 주 용도는 검색
검색 연산의 최악의 경우 복잡도가 O(logn) (경사트리인 경우 제외하고)
속성
왼쪽 서브 트리의 모든 항목은 루트 노드의 데이터보다 작아야 하고, 오른쪽 서브 트리의 모든 항목은 루트 노드의 데이터보다 커야 합니다.
주요사항
루트 데이터가 항상 왼쪽 서브 트리 데이터와 오른쪽 서브 트리 데이터 사이에 있기 때문에 중위 탐색을 수행하면 정렬된 리스트가 만들어집니다.
균형 이진 검색 트리 (Balanced Binary Search Tree)
n이 노드 갯수일 때 최악의 경우 복잡도가 O(n)인 다양한 트리를 볼 수 있는데, 최악의 복잡도는 경사 트리일 때 발생합니다.
노드의 갯수가 n일때, 이진검색트리의 높이는 최악의 경우 O(n)
이 절에서는 높이에 제한을 가하여 최악의 경우 복잡도를 O(logn)으로 감소시킴
일반적으로 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차가 k인 height balanced tree를 HB(k)라고 표현
k는 balance factor라고 부릅니다.
완전 균형 이진 검색 트리
HB(k)에서 k=0(balance factor = 0)이면, 이런 이진 검색 트리를 완전 균형 이진 검색 트리라고 함
즉, HB(0) 이진 검색 트리에서는 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이는 최대 0이어야 한다는 것
AVL(Adelson-Velskii and Landis) 트리
HB(k)에서 k=1(balance factor = 1)이면, 이런 이진 검색 트리를 AVL 트리라고 함
속성
어떤 노드 x에 대해서도 x의 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이의 차이가 최대 1