15장 : 이진트리 검색 (Binary Tree Search)

가족계획처럼 자식을 둘 이하만 가질 수 있는 이진트리(Binary Tree)는 단촐한 구성 때문에 컴퓨터 알고리즘에서 단골로 등장합니다.  단순화된 이진트리로 알고리즘을 정립한 뒤에 더 복잡한 트리에 적용하는 전략도 많이 쓰입니다.

이번 장에서는 이진트리를 효율적인 검색 구조로 사용하는 방법에 대해서 알아봅니다.  이상적이라면 이진트리의 좌우 균형이 맞아 검색의 효율이 매우 좋습니다.  하지만 이진트리를 구축하는 방법에 따라 균형이 맞지 않을 수 있는데 이때는 검색의 효율이 매우 떨어집니다.

이렇게 까탈스러운 이진트리 검색에 대해 알아보고,  문제는 무엇이고, 그 문제를 어떻게 해결할 수 있는지 알아보기로 합니다.  이번 장에서 이진트리 검색에 대한 모든 문제를 해결하지는 못하는데,  그 해결책은 이어지는 내용에서 계속 등장합니다.

이후 내용의 전개를 이해하기 위해서도 이번 장은 확실히 이해하는 것이 좋습니다.

강의 자료 



강의 동영상

15.0 이진트리 검색 - 시작 : 이진트리는 다양한 응용이 가능하지만, 검색에서의 활용은 많은 흥미를 불러 일으킵니다.  이진트리로 어떻게 검색을 할 수 있는지, 그리고 어떤 이슈가 있는지 알아봅니다.



15.1 이진트리 검색 개요 : 이진트리의 특성과 구성 요건을 알아봅니다.  그리고 이진트리 검색을 위한 소스 구조를 잡습니다.



15.2 이진검색 트리의 삽입과 검색 : 이진검색 트리에서 검색하는 법을 알아보고 그 구현을 알아봅니다.  그리고 새로운 데이터를 규칙에 맞게 이진트리에 추가하는 방법도 알아봅니다.



15.3 이진검색 트리의 삭제 : 이진검색 트리에서 노드 하나를 삭제하는 건 의외로 까다롭습니다.  모든 경우를 다 고려해보면 결국 세가지 케이스로 정리됩니다.  이 세가지 케이스의 판별과 삭제법에 대해 알아보고 구현해 봅니다.



15.4 이진트리 검색의 분석 : 이진트리 검색의 성능을 좌우하는 요소는 트리의 높이입니다.  좌우로 균형이 맞아 트리의 높이가 최소로 될 때 최고의 성능을 보여줍니다.  반대로 균형이 맞지 않으면 단순한 검색법보다 오히려 성능이 나쁠 수 있습니다.  여기서 균형의 중요성을 깨닫습니다.



15.5 이진트리 정렬 : 이진트리 검색을 위한 트리구조는 정렬법으로도 활용할 수 있습니다.  잠시 곁가지로 빠져서 이진트리 정렬법에 대해서 알아봅니다.



15.6 이진트리의 균형 맞추기 : 앞서 알아 보았듯이 이진트리 검색의 성능은 트리의 균형에 좌우됩니다.  현재 상태에서 한번에 트리의 균형을 맞추는 방법을 알아봅니다.  테이터 집합의 변화가 적을때 활용할 수 있습니다.



15.7 이진트리 검색의 중복키 문제 : 이진트리 검색은 중복된 키를 가지는 데이터 집합에 대해 취약합니다.  중복된 키를 허용하는 이진트리를 만드는 방법에 대해 알아봅니다.



15.9 이진트리 검색 - 결론 : 이진트리 검색은 단순한 규칙으로 구성된 이진트리를 통해 효율적인 검색/삽입/삭제 성능을 보여줍니다.  하지만 이는 트리의 균형이 맞을 때의 얘기입니다.  이번 장에서 배운 내용을 정리해 봅니다.

---

관련글 |
  - C++로 배우는 알고리즘
  - 14장 : 기본 검색 알고리즘
  - 16장 : 해쉬 (Hash)