CH12-1 균형잡힌 이진탐색트리: AVL트리의 이해(1)
12-1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 ①
12챕터에서는 AVL트리란걸 이론적으로 설명할 것임. 이 이론은 균형과 관련되어있다. 이론 이후에 실제 구현을 진행할 것. 그런데 이 구현에 약간 문제가 있다. 모든 상황에서 균형을 잡아주는 사례가 아니다.
그래서 이상적인 교육은.. 우선 구현까지 무작정 따라와라. 그 이후 추가적인 교육이 필요하다. 이 추가적인 교육은 오렌지 미디어 오탈자 게시판에 가면 추가적인 교육에 대한 문서를 등록해놨다. 이 문서를 꼭 읽기를 바란다. 그래야 12챕터가 완성이 된다. 이 추가적인 부분은 서적에 없으니.. 꼭 보충하길 바란다. 강의통해서도 설명은 하긴 할 것이다.
자 이제 탐색에 대한 두번째 이야기를 진행해보자. 우선 이론적인 측면을 이해하는게 중요하다. 이론을 이해하지 못하면 절대 구현못한다.
지금까지 배운 트리에 대한 계보를 살펴보면… 트리를 배우고, 이진트리를 배우고, 몇가지 표현을 해본 다음에 이진탐색트리를 배웠다. 일반적인 자료구조 학습에서 이 트리학습의 끝은 균형잡힌 이진탐색트리를 배우는 것이다.
이진탐색트리에 종류가 많다. 우리는 이 중에서 하나를 선택해서 이론적 공부와 구현까지 해보자.(하나를 정확히 안다는 느낌으로) 이후 다른 균형잡힌 이진탐색트리를 각자 학습하는 방식으로 진행할 것이다.
참고로 실무에서는 직접 구현할 일은 없을 것이다… 라이브러리 갖다 쓰는일이 많음.
강의의 본론으로 들어가보자. 앞서 우리가 배운 이진탐색트리에는 한가지 문제가 있다.
이진탐색트리는 미리 정렬된 데이터가 순서대로 삽입될경우 빅오가 $O(n)$에 가까워진다! 그냥 선형자료구조가 되어버림… 심지어 참조까지 일어나는 선형자료구조이다. $O(log_2n)$을 기대할 수 없다.
위의 문제는 저장순서를 약간만 바꿔도 균형을 잡아줄 수 있다.
