소개

이진 탐색 트리(binary search tree)는 값을 정렬된 상태로 유지합니다. 모든 노드의 왼쪽 서브트리는 더 작은 값을, 오른쪽 서브트리는 더 큰 값을 가집니다. 이러한 정렬 덕분에 검색이 빨라지지만, 이는 트리가 대략적으로 균형을 유지할 때만 해당됩니다. 일반적인 이진 탐색 트리에 정렬된 순서대로 값을 삽입하면 트리가 직선 형태로 변질되어, 모든 검색이 느린 선형 탐색이 됩니다.

AVL 트리는 자동으로 균형을 유지함으로써 이 문제를 해결합니다. 삽입이나 삭제가 일어날 때마다 노드가 한쪽으로 치우쳤는지 확인하고, 만약 그렇다면 회전(rotation)이라고 불리는 작은 국소적 수정을 수행하여 균형을 복구합니다. 어떤 방식으로 구축하든 AVL 트리는 결코 직선 형태로 변질되지 않습니다.

이 코스에서는 선호하는 언어로 AVL 트리를 처음부터 직접 구현해 봅니다. 높이가 추적되는 노드, 균형 확인, 네 가지 회전 케이스, 그리고 자가 균형 삽입 및 삭제를 다룹니다. 그런 다음 완성된 클래스를 사용하여 일련의 연습 과제를 해결하게 됩니다.