자가 균형 이진 탐색 트리

값을 넣거나 뺄 때마다 스스로 모양을 고쳐 트리 높이(루트에서 가장 깊은 노드까지의 층 수)를 낮게 유지하는 이진 탐색 트리다. 높이가 O(log n)으로 묶이므로 찾기 · 넣기 · 빼기가 최악의 경우에도 O(log n)이다. AVL 트리와 레드-블랙 트리가 대표적이고, 자바의 TreeMap 은 레드-블랙 트리로 만들어져 있다.