균형 트리 (Balanced Tree)

개념

균형 트리는 트리의 높이(레벨)을 최소화하여 삽입/삭제/탐색 연산의 효율성을 높인 트리 자료구조이다. 삽입/삭제 연산을 실행할 때마다 트리의 균형을 자동으로 유지하며, 최악의 경우에도 O(log n)의 시간 복잡도를 가지도록 설계되어있다.

특징

• 높이 균형 유지 각 노드의 좌우 서브트리의 높이 차이가 일정 범위를 넘지 않도록 유지한다.
• 자동 균형 조정 삽입/삭제 시 트리의 균형이 깨지면 회전이나 분할/병합 등의 추가적인 연산을 통해 자동으로 균형을 맞춘다.
• 탐색/삽입/삭제 효율성 트리의 높이가 O(log n)으로 제한되어, 탐색/삽입/삭제 연산이 모두 O(log n)의 시간 복잡도를 가진다.
• 안정적인 성능 삽입/삭제가 반복되어도 트리 구조가 급격하게 변하지 않아 데이터가 많더라도 일관된 성능을 보장한다.
• 다양한 응용 데이터베이스 인덱스, 파일 시스템, 우선순위 큐, 연관 배열 등 다양한 분야에서 사용할 수 있다.

AVL 트리

개념

AVL 트리는 스스로 균형을 유지하는 이진 탐색 트리이다. 모든 노드에서 좌우 서브트리의 높이 차이(균형 계수)가 1을 넘지 않도록 유지하며, 트리의 균형이 깨질 경우 회전 연산을 통해 자동으로 균형을 맞춘다.

장점

• 최악의 경우에도 O(log n) 성능 보장
• 트리 편향 현상 방지
• 검색 성능이 우수 균형 유지가 엄격하여 다른 트리보다 검색 연산이 빠르다.