트리(Tree)는 계층적인 구조를 나타내는 자료 구조입니다. 이는 노드(Node)들의 집합으로 구성되어 있습니다. 각 노드는 부모(parent)와 자식(children) 노드들로 연결되어 있습니다. 트리에서 가장 위에 있는 노드는 루트(root) 노드라고 불립니다. 그리고 자식 노드가 없는 노드를 단말(Leaf) 노드라고 합니다.

트리에는 다양한 종류가 있고, 여러 목적으로 활용됩니다. 이러한 트리들은 그래프의 한 부분입니다.



  1. 이진 트리
  2. 이진 탐색 트리
  3. AVL트리
  4. 힙 트리
  5. m원 트리
  6. R-B 트리




이진 트리

각 노드가 최대 두 개의 자식 노드를 가지는 일반적인 트리입니다. 마지막 레벨를 제외하고 모든 노드가 채워져 있는 트리를 완전 이진 트리라고 하고, 마지막 레벨에도 노드들이 채워져 있는 트리를 포화 이진 트리라고 합니다.



이진 탐색 트리

이진 트리의 한 종류로, 각 노드가 특정한 순서로 정렬되어 있습니다. 왼쪽 서브트리의 모든 노드는 현재 노드보다 작고, 오른쪽 서브트리의 모든 노드는 현재 노드보다 큽니다. 주로 데이터를 검색할 때 O(logN)를 가져 효과적입니다. 하지만 정렬된 데이터가 삽입될 때, 한 쪽으로 치우쳐진 사향 트리가 형성되어 검색 시 O(N)이 된다는 단점이 있습니다.



AVL트리

AVL트리는 이진 탐색 트리의 단점을 보완된 균형 트리로, 높이 균형을 유지합니다. AVL 트리는 자동으로 균형을 유지하여 검색, 삽입, 삭제 등의 연산이 빠르게 수행됩니다. BF(Balance Factor, 현재 노드에서 왼쪽 서브노드와 오른쪽 서브노드의 높이 차를 나타내는 수치)를 사용해서 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 1로 유지합니다. 서브 트리의 ‘회전(LL,RR,LR,RL)’ 방법을 통해 모든 노드에서 BF을 1 이하로 유지합니다.



힙 트리

힙(Heap)은 각 노드의 값이 해당 노드의 자식 노드들의 값보다 작은(또는 큰) 완전 이진 트리로 반정렬 트리입니다. 힙은 최소힙(각 노드의 값이 자식 노드들의 값보다 작음)과 최대힙(각 노드의 값이 자식 노드들의 값보다 큼)이 있습니다.

삽입은 항상 마지막 레벨의 가장 오른쪽 노드에 새로운 원소를 추가하고, 삭제는 루트 노드를 제거한 후, 마지막 노드를 루트로 옮긴 뒤 필요한 조정을 수행합니다. 힙은 주로 우선순위 큐를 구현하는데 사용되거나 다익스트라 알고리즘, 힙 정렬 등의 알고리즘에서 활용됩니다.



m원 트리

m-원 트리는 각 노드가 최대 m개의 자식을 가질 수 있는 트리입니다. 이는 각 노드가 m개 이하의 자식을 가지는 트리를 말합니다.

여기서 m은 자연수이며, m이 2일 때 이는 이진 트리를 나타냅니다. 즉, 각 노드가 최대 2개의 자식을 가지는 트리가 이진 트리입니다. 이러한 m원 트리는 n레벨에서는 m^(n-1)개의 노드를 가질 수 있으며, 총 (m^n-1)/(m-1)개의 노드들을 가질 수 있습니다.

그리고 노드당 여러 개의 키를 가집니다. 키의 수가 m/2(오름차순) - 1보다 작을시 underflow가 됩니다. 따라서 m이 5이상부터 노드당 2개 이상의 키를 가져야합니다. 추가적으로, 노드에 overflow가 생겼을 시 m/2(오름차순)번째의 키를 부모 노드로 만들고 나머지 키들을 자식 노드로 보냅니다.

B-트리도 m-원 트리의 한 종류로 대용량 데이터를 효율적으로 저장하고 검색하기에 효과적입니다. 데이터베이스 시스템이나 파일 시스템에서 널리 사용됩니다.



R-B 트리

AVL과 같은 이진 탐색 트리의 단점을 보완한 균형 트리 중 하나입니다. BF을 사용하는 AVL과 달리 R-B 트리는 특별한 규칙을 따릅니다. 규칙은 다음과 같습니다. * 노드의 색상은 레드 또는 블랙 중 하나를 가집니다. * 루트 노드는 블랙입니다. * 단말 노드는 레드입니다. * 레드 노드는 연속해서 사용할 수 없습니다.ex) 부모 레드 - 자식 레드는 안됨. * 루트에서 단말까지 블랙 노드의 수가 같습니다.

위와 같은 규칙을 사용해서 ‘회전’과 ‘상향 색변환’ 방법을 통해 트리의 높이 차를 일정하게 유지합니다.