[Today I Learned 02] 2. logN

이진탐색트리를 공부하다가 O(longn)에 대한 궁금증이 생겨서 구글링을 했다. 알아본 내용을 적어본다.

예를 들어 2개의 자식 노드를 가진 이진트리를 이용해서 M개의 노드 중 원하는 값의 노드를 찾는다고 가정한다. 처음에는 M개의 노드 모두 탐색 해야하지만 루트 노드에서 첫 번째 자식 노드로 가게 되면 탐색 해야할 개수가 M/2가 된다.
M/2 -> M/4 -> M/8 -> ...
만약에 탐색 해야하는 자료의 수가 2^n개라면, 이진 트리를 사용할 경우 n번의 탐색을 통해서 원하는 값을 찾을 수 있게 된다.