이것 저것 뚝딱거리는 사람 이것 저것 뚝딱거리는 사람

이진 탐색 트리 앞으로 글을 쓰겠지만 선형 자료 구조에서는 원하는 값을 탖는 방법이 여러가지가 있다. 가장 먼저 생각할 수 있는 것은 앞 혹은 뒤에서부터 하나씩 살펴보는 선형탐색이다. 그렇다면 트리형 자료구조에서는 원하는 값을 어떻게 찾을 수 있을까? 가장 기초적인 방법이 바로 이진탐색 트리이다. (물론 모두 살펴볼 수도 있을 것이다.) 먼저 그림부터 보자. 루트 노드에 값 K가 담겨있다고 생각하자. 그렇다면 이 루트 노드의 왼쪽에 있는 서브 트리에는 K보다 작은 값이, 오른쪽에는 K보다 큰 값만이 들어있는 트리를 생각할 수 있고, 이 모든 서브트리에도 같은 생각이 적용된다면 원하는 값을 찾기가 쉬울 것이다. 이를 이진 탐색 트리라 한다. 실제 값을 넣어서 확인해보자 위 트리에서 13을 찾고 싶다고 생각..