자가 균형 이진 탐색 트리

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

컴퓨터 과학에서 자가 균형 (높이 균형) 이진 탐색 트리는 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드 기반 이진 탐색 트리이다.  Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. . Section 6.2.3: Balanced Trees, pp.458–481.

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

 같이 보기 
 정렬
 참고 문헌 

분류:이진 트리
분류:소련의 발명품
분류:트리 구조