트리 :: batsalee의 작은바지

트리

2024. 1. 21. 12:26

Pasted image 20231130131143.png|600x400

1. 개념

위 사진처럼 생긴 구조로 노드의 아래에 노드를 두는 것
파일시스템 구조같은것을 만들때 사용

용어정리

노드(node) : 트리를 구성하는 기본(위 그림에서의 원들)
루트 노드(root node / root) : 더 이상 부모가 없는 최상위 노드(위 그림에서의 A노드)
부모 노드(parent node) : 위 아래 노드가 있을때 위의 노드(A노드는 B노드의 부모노드)
자식 노드(child node) : 위 아래 노드가 있을때 아래의 노드(B노드는 A노드의 자식노드)
형제 노드(siblings node) : 같은 부모노드를 공유하는 노드들(F노드와 G노드는 형제노드)
가지 노드(branch node) : 루트를 제외하고 자식을 하나라도 가지는 노드
리프(leaf) : 차수가 0인 노드, 제일 끝의 노드(H노드나 E노드 같은 것들), 단말(terminal) 노드라고도 부름
왼쪽 서브트리 : 왼쪽 밑 노드의 서브트리
오른쪽 서브트리 : 오른쪽 밑 노드의 서브트리
링크(link) : 노드를 연결하는 간선
경로(path) : 한 노드에서 다른 한 노드까지 가는 길 사이에 있는 노드들의 순서
길이(length) : 출발 노드에서 도착 노드까지 거치는 노드의 개수
깊이(depth) : 루트노드에서 현재노드까지의 거리
레벨(level) : 0부터 시작하는 링크의 단계
크기(size) : 노드의 전체 개수
높이(height) : 레벨의 역순
너비(width) : 가장 많은 노드를 갖고있는 레벨의 크기(그림에선 레벨2가 DEFG 4개를 가지므로 4의 너비)
차수(degree) : 각 노드의 자식의 개수
트리의 차수(degree of tree) : 트리의 최대 차수(모든 노드의 자식 갯수중 가장 큰 수)
내부 정점(internal vertex) : 차수가 2 이상인 정점
포레스트(forest) : 서로 독립인 트리들의 모임

2. 트리의 종류

일반트리, 이진트리(+이진탐색트리), B-tree, AVL트리(레드블랙트리) 등이 있다

일반트리

하나의 부모에 여러개의 자식이 존재할 수 있음
컴퓨터공학에서 자주 사용하는 구조라기보다는 일반적인 트리의 개념

이진트리

자식노드를 최대 두개로 제한하는 가장 간단한 형태의 트리
- 즉 자식노드가 0개거나, 1개거나 2개
- 보통 자식노드를 left child, right child라고 부름
노드들 간의 대소관계는 고려하지 않음

※ 이진트리의 크기 설정하는 법
크기가 N인 배열은
트리의 높이 = CEIL(log(N))
트리의 크기 = (1 << (트리의 높이 + 1))

이진트리의 종류로는 정이진트리, 편향이진트리, 포화이진트리, 완전이진트리, 이진탐색트리가 있음

1) 정 이진트리(full binary tree)

모든 트리의 자식은 0개이거나 2개이다.

2) 편향 이진트리(skewed binary tree, degenerate tree, pathological tree)

모든 노드가 부모의 왼쪽(or 오른쪽)으로 편향된 경우
링크드 리스트와 성능이 동일함

3) 포화 이진트리(perfect binary tree)

이진트리가 보유할 수 있는 최대의 노드를 갖춘 형태
모든 리프노드의 높이가 같고, 리프노드가 아닌 노드는 모두 2개의 자식을 가짐

4) 완전 이진트리(complete binary tree)

마지막 레벨 제외 모든 레벨이 완전히 채워져 있으면서, 마지막 레벨의 모든 노드들이 왼쪽부터 차있음
즉, 모든 리프노드의 높이가 최대 1차이나고, 모든 노드의 오른쪽 자식이 있다면 왼쪽자식도 있음
트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태
Array를 이용해서 구현
- Heap은 완전이진트리 형태로 구현함, 그러므로 Heap도 Array를 이용해서 구현하게 됨
아래 그림에서 C노드 밑에 왼쪽자식노드가 하나 있어도 역시 완전이진트리

5) 이진탐색트리

이진트리의 일종으로, 노드간의 대소관계를 고려함
노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있음
이렇게 구성해두면 어떤 값 N을 찾을때 루트노드와 비교해서 N이 더 작다면 루트노드보다 더 큰 값들만 모여있는 오른쪽 가지는 전혀 탐색할 필요가 없다.
마찬가지로 루트노드의 왼쪽자식보다 N이 크다면 왼쪽 자식의 왼쪽 가지는 탐색할 필요가 없으니 탐색에 적합한 구조
즉 탐색을 할때 노드 하나를 거칠때마다 탐색해야할 범위가 절반씩 줄어드는 O(logN) 구조
탐색뿐 아니라 값의 삽입/삭제에도 똑같은 과정을 거치게 되므로 이상적인 상황에서 탐색/삽입/삭제 모두 O(logN)
삽입할때 먼저 그 값이 있는지 탐색하고 없으면 없다고 결정난 그 자리에 추가됨
삭제할때 해당 노드의 자식트리가 없으면 그냥 그 노드의 부모노드에서 해당 링크를 null로 수정
- 서브트리가 하나라면 그 노드의 부모노드에서 링크를 서브트리의 하나 노드로 수정
- 서브트리가 두개라면 왼쪽서브트리중 가장 큰값 혹은 오른쪽 서브트리중 가장 작은값을 부모쪽에 연결

※ 1부터 100까지 순서대로 삽입한다면?
만약 값이 오름차순으로 1부터 100까지 순서대로 삽입된다면 오른쪽으로 편향된 트리가 만들어짐
그럼 그냥 단방향리스트와 같은 구조가 되므로 탐색효율이 떨어짐

이런 편향상황을 만들지 않기 위해 사용되는 트리구조를 AVL-Tree이라고 하며
그 중 대표적인것이 레드-블랙 트리

B-트리

이진트리를 확장한 것
- 이진트리는 하나의 노드가 최대 2개의 자식노드를 가짐
- B-트리는 2개 이상의 자식노드를 가질 수 있음
- 자식노드를 가질수 있는 수를 늘린 대신 트리의 높이를 줄인 것(노드에 접근하는 시간이 빨라짐)
- 노드에 접근하는 시간 자체가 노드에서 연산하는 시간보다 길면 B-tree를 쓰면 좋다.
항상 정렬된 상태로 저장됨

order를 나타내는 숫자 m을 가지며, B-tree of order m이라고 함
B-tree of order m은 아래의 조건을 만족시킴

루트노드는 최소 2개 ~ 최대 m개의 자식노드를 가짐
루트 노드를 제외한 내부 노드들은 최소 (m/2)개 ~ 최대 m개의 자식노드를 가진다.
특정 노드의 데이터(key)가 k개라면 자식 노드의 개수는 k+1개여야 한다.
노드내의 데이터는 최소 int(m/2)-1개 ~ 최대 m-1개까지 포함될 수 있음
특정 노드의 왼쪽 서브트리는 특정 노드의 key보다 작은 값들로, 오른쪽 서브트리는 큰값들로 구성
모든 리프 노드들의 높이는 같다.

말이 복잡해서 아래의 B-Tree 예시를 보면 훨씬 이해가 쉬울것임
M=3이면 자식노드로 부모노드보다 작은값들, 중간값들, 더큰값들 세분류로 나눠서 넣는다는 뜻

Pasted image 20231130134831.png|400x300

B-tree의 탐색 과정

루트노드에서 탐색을 시작해서 하향식으로 탐색을 진행함, k를 찾는다고 했을 때

루트노드에서 탐색을 시작한다.
k를 찾았다면 탐색을 종료한다.
k와 노드의 key값을 비교해 알맞은 자식노드로 내려간다.
해당 과정을 리프노드에 도달할때까지 반복한다.
리프 노드에서도 k를 찾지 못한다면 트리에 값이 존재하지 않는 것이다.

3. 트리의 탐색방식

탐색방식으로 대표적으로 너비우선탐색(BFS), 깊이우선탐색(DFS)가 있음