[자료구조] 12. 탐색 2
콰이엇
윤성우 저자님의 "윤성우의 열혈 자료구조" 책을 학습하고 정리한 글입니다. 1. 균형 잡힌 이진 탐색 트리1-1. 이진 탐색 트리의 문제점이진 탐색 트리의 탐색 연산은 O(logN)의 시간 복잡도를 가진다.트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하므로 쉽게 판단이 가능하다.이러한 이진 탐색 트리는 균형이 맞지 않을수록 O(N)에 가까운 시간 복잡도를 보인다.위 그림과 같이 이진 탐색 트리의 조건을 만족하지만, 노드 수에 가까운 높이를 형성하게 되었다.위 그림과 같이 저장 순서만 조금 바꿨더니 루트 노드를 기준으로 어느 정도 균형이 잡혔고, 트리의 높이도 반으로 줄었다. 이렇듯 앞서 구현한 이진 탐색 트리는 저장 순서에 따라 탐색의 성능에 큰 차이를 보이는데, 이것이 이진..
