트리 (Tree)
노드(Node)와 간선(Edge)으로 이루어진 계층형 비순환 그래프.
1개의 루트 노드, 각 노드는 0개 이상의 자식 노드를 갖고있다.
루트 노드 : 부모가 없는 노드
단말 노드 : 자식이 없는 노드
내부 노드 : 단말 노드를 제외한 노드
형제: 같은 부모를 가지는 노드
크기(Size) : 자신과 자식 노드의 수
계층(Level) : 노드의 차수
깊이(Depth) : 루트로부터 노드까지 거치는 간선 수
차수(Degree) : 하위 노드/간선 수
높이(Height) : 가장 깊은 노드의 깊이
이진 트리(Brinary Tree)
노드의 최대 차수가 2인 트리를 이진트리라고 한다.
- 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨의 노드가 채워져있는 트리. 왼쪽 -> 오른쪽으로 노드가 채워져야 한다.
- 포화 이진 트리(Full Binary Tree) : 모든 노드 자식의 개수가 2개인 트리
이진 탐색 트리(Binary Search Tree, BST)
부모노드를 기준으로 왼쪽 자식 노드는 작은 값, 오른쪽 자식 노드는 큰 값을 가지고 있는 이진 트리. 균형이 맞춰져 있을 때를 기준으로 O(logn) 의 시간 복잡도로 탐색을 수행할 수 있다.
삽입(Insert) : 탐색을 통해 찾게 되는 단말 노드의 자식으로 추가한다.
제거(Delete)
- 자식이 1개일 경우 해당 노드를 삭제하고 자식과 스왑한다.
- 자식이 2개일 경우 해당 노드를 삭제하고 왼쪽 노드 중 가장 큰 / 오른쪽 노드 중 가장 작은 노드와 스왑한다.
AVL 균형 이진 트리 (AVL Blanced Binary Tree)
왼쪽 / 오른쪽 자식 노드의 높이 차이가 1 이하로 유지하는 균형잡힌 이진 트리.
균형이 잡혀서 탐색 속도를 보장하지만 자료의 삽입/삭제가 빈번하게 발생 시 균형 유지 비용이 많아짐.
AVL 트리의 균형이 깨지는 경우는 다음과 같다.
- LL : 왼쪽 자식 노드의 왼쪽에 삽입
- LR : 왼쪽 자식 노드의 오른쪽에 삽입
- RR : 오른쪽 자식 노드의 오른쪽에 삽입
- RL : 오른쪽 자식 노드의 왼쪽에 삽입
균형이 깨질 경우에는 다음과 같이 균형을 맞춘다.
LL : 노드를 오른쪽으로 회전시킨다.
![]()
LR : 왼쪽 자식 노드를 왼쪽으로 회전 후에 노드를 오른쪽으로 회전시킨다.
![]()
RR : 노드를 왼쪽으로 회전시킨다.
![]()
RL : 오른쪽 자식 노드를 오른쪽으로 회전 후에 노드를 왼쪽으로 회전시킨다.
![]()
비트리 (B-Tree)
- 왼쪽 서브트리는 작은 값/ 오른쪽 서브트리는 큰 값을 가진다. (BST)
- 모든 노드의 자식의 수는
2~N개 이다. - 노드의 자료수가
N-1개 일 경우N개의 자식을 가진다. - 내부 노드는
N/2~N개의 자식을 가진다. - 단말 노드는
N/2 -1~N-1개의 자료를 가지며 모두 같은 레벨이다.
레드 블랙 트리 (Red-Black Tree)
- 모든 노드는 레드/블랙 중 하나이다.
- 루트는 블랙이다.
- 레드 노드는 연달아 나올 수 없다.
삽입과 삭제시 회전 또는 색상 변경을 통해 트리의 균형을 유지한다.