균형이 맞지 않은 tree 구조는 성능을 저하 시킬 수 있습니다. O(log n) → O(n)
그래서 자체 균형 이진 검색 트리 인 AVL 트리를 만들었습니다.
AVL 트리(AVL tree)는 가장 초기에 나온 균형 잡힌(balanced) 이진 탐색 트리이다. 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 논문 "An algorithm for the organization of information"[1] 을 통해 발표했고 그들의 이름을 따서 지어졌다. AVL 트리는 각각의 노드(node, 분기점)마다 왼쪽과 오른쪽 부분 트리(sub-tree)의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다. 균형 잡힌 AVL 트리는 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다. 그러나 삽입과 삭제를 할 때에는 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 레드-블랙 트리 만큼 효율이 좋지 않아 자주 쓰이지는 않는다.
이진 검색 트리의 성능을 최적화 하려면 균형 트리가 중요합니다. 이 섹션에서는 세 가지 주요 균형 상태에 대해 설명합니다.
이진 검색 트리의 이상적인 형태는 모든 레벨의 트리가 위에서 아래의 노드로 채워져 있는 상태가 완벽하게 균형 잡힌 상태입니다.
트리가 완벽하게 대칭 일 뿐 아니라 최하위 레벨의 노드가 완전히 채워져 있습니다. 이것이 완벽하게 균형을 유지하기 위한 요구 사항입니다.
완벽한 균형을 달성하는 것이 이상적이지만 거의 불가능합니다. 완벽하게 균형 잡힌 트리는 모든 레벨을 맨 아래까지 채울 수 있는 정확한 수의 노드를 포함해야 하므로 특정 수의 요소로만 완벽 할 수 있습니다.
예를 들어, 1, 3 또는 7 노드가 있는 트리는 완벽하게 균형을 맞출 수 있지만 2, 4, 5 또는 6이 있는 트리는 마지막 레벨이 채워지지 않기 때문에 완벽하게 균형을 잡을 수 없습니다.
균형 트리의 정의는 맨 아래 레벨을 제외한 모든 레벨의 트리를 채워야 한다는 것입니다. 대부분의 이진 트리에서는 이것이 최선입니다.
