tose33

이진 탐색 트리의 단점 앞서 공부했던 이진 탐색 트리는 (https://tose33.tistory.com/654) 단점이 있다. 이진 탐색 트리의 데이터 탐색의 시간복잡도는 트리의 높이에 해당하기 때문에 데이터가 N개일때 O(logN)인데, 트리의 균형이 맞지 않을수록 O(N)에 가까워 진다. 다음과 같이 1부터 5까지의 숫자를 순서대로 삽입한 이진 탐색 트리를 생각해보자 1 \ 2 \ 3 \ 4 \ 5 위 이진 탐색 트리의 높이는 5로 탐색 시간은 O(N)이 되버린다. 하지만 아래와 같이 3을 먼저 삽입한 후에 순서대로 숫자를 삽입하면 높이는 3이 된다. 3 / \ 1 3 \ \ 2 5 이런 이진 탐색 트리의 단점을 개선한 트리를 균형 잡힌 이진 트리라고 하고 여러 종류가 있는데 다음과 같다 AVL, ..