알고리즘 공부 -트리편

알고리즘 공부 -트리편

 

1. 서브트리 (Subtree)

서브트리는 트리의 일부분으로, 하나의 노드와 그 노드의 자손들로 구성됩니다. 서브트리는 원래 트리에서 해당 노드를 루트로 하는 독립적인 트리로 생각할 수 있습니다. 이를 통해 문제를 작은 단위로 나누어 해결하는 분할 정복 기법을 적용할 수 있습니다.

2. 이진 트리의 구조 (Binary Tree Structure)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다. 이진 트리에는 완전 이진 트리, 포화 이진 트리, 균형 이진 트리 등 다양한 종류가 있으며, 각각의 성질에 따라 적절한 알고리즘을 적용하여 문제를 해결할 수 있습니다.

 

3. AVL 트리 = 불균형 이진 트리 (AVL Tree = Imbalanced Binary Tree)

AVL 트리는 균형 인수(Balance Factor)가 -1, 0, 1인 이진 탐색 트리입니다. AVL 트리는 노드 삽입 및 삭제 시 균형을 유지하기 위해 회전 연산을 수행합니다. 이로 인해 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(log N)으로 유지됩니다.

 

 

4. 균형 이진 트리 (Balanced Binary Tree)

균형 이진 트리는 높이 차이가 일정한 범위 내에 있는 이진 트리를 말합니다. 균형 이진 트리는 탐색, 삽입, 삭제 연산의 시간 복잡도를 O(log N)으로 유지할 수 있어 성능이 좋습니다. 균형 이진 트리의 종류로는 AVL 트리와 RB 트리가 대표적입니다.

 

5. RB 트리 (Red-Black Tree)

RB 트리는 노드에 색깔을 부여하여 균형을 유지하는 자료구조로, 삽입과 삭제 연산 시에도 O(log N)의 시간 복잡도를 보장합니다. RB 트리는 다음의 5가지 속성을 만족해야 합니다.

1) 모든 노드는 빨강 혹은 검정 색 중 하나를 가집니다.

2) 루트 노드는 검정색입니다.

3) 모든 리프 노드(NIL)은 검정색입니다.

4) 빨강색 노드의 자식 노드는 검정색입니다.

5) 모든 노드에 대해 해당 노드부터 리프 노드까지 경로에 있는 검정색 노드의 개수는 동일합니다.

RB 트리는 균형 이진 트리 중 하나로, 탐색, 삽입, 삭제 연산의 성능이 좋아 다양한 애플리케이션에서 사용됩니다.