자가 균형 이진 탐색 트리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
균형이 맞지 않는(unbalanced) 트리의 예; 루트에서 특정 노드로 갈 때, 평균 3.27회의 노드 접근이 필요하다.
같은 트리를 높이 균형을 맞춘 후의 상태; 평균 이동 비용이 3.00 노드 접근(node access)로 감소되었다.

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

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

참고 문헌[편집]

  1. Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.