자가 균형 이진 탐색 트리

컴퓨터 과학에서 자가 균형 (높이 균형) 이진 탐색 트리는 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드 기반 이진 탐색 트리이다.^[1]

균형이 맞지 않는(unbalanced) 트리의 예; 루트에서 특정 노드로 갈 때, 평균 3.27회의 노드 접근이 필요하다.

같은 트리를 높이 균형을 맞춘 후의 상태; 평균 이동 비용이 3.00 노드 접근(node access)로 감소되었다.

이 자료 구조는 변경이 가능한 정렬된 리스트의 효율적인 구현이며, 연관 배열(associative array), 우선순위 큐, 집합과 같은 다른 추상 자료 구조로 쓰일 수 있다.

같이 보기

• 정렬