균형 이진 탐색 트리

균형 이진 탐색 트리

맵은 이진 탐색 트리로도 구현할 수 있다. 이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조로 탐색에 걸리는 시간도 로 동일하다. 그렇다면 이들의 차이는 무엇일까? 답은 자료의 삽입과 삭제의 용이성에 있다.

이진 탐색에서 자료는 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉, 맵에 자료를 삽입하거나 삭제할 때 불필요한 항목들의 많은 이동이 필요하다. 반면에 맵을 이진 탐색 트리로 구현하면 시간에 삽입과 삭제가 가능하다. 따라서 삽입과 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용하여야 한다. 

이진 탐색 트리는 만약 균형 트리이면 의 탐색 연산 시간 복잡도를 갖는다. 그러나 삽입과 삭제 연산이 이진 탐색 트리를 유지시키기는 하지만 균형 트리를 보장하지는 않는다. 만약 경사 트리인 경우에는 탐색의 시간 복잡도가 으로 높아지게 된다.

따라서 이진 탐색 트리에서는 균형을 유지하는 것이 무엇보다 중요하다. 이진 탐색 트리가 스스로 균형을 유지하도록 하는 방법에 대해 살펴보자. 이들은

상당히 복잡하기 때문에 모든 주제를 다루지는 않고 AVL 트리에 대해서만 알아본다. 트리의 노드에는 정수가 저장된다고 가정하자.