초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
단어를 가나다순으로 지키며 새 단어를 계속 넣고 찾는 사전 프로그램이 있다고 합시다. 정렬된 배열은 이진 탐색으로 빨리 찾지만, 중간에 넣으려면 뒤의 값을 밀어야 합니다. 연결 리스트는 넣기는 쉽지만 가운데로 건너뛸 수 없고, 해시 테이블은 순서를 잊습니다. 순서를 지키면서 찾기와 넣기를 둘 다 빠르게 할 수는 없을까요?
이진 트리에 규칙 하나를 더합니다. 어느 노드에서 보든 왼쪽 아래에는 그보다 작은 값만, 오른쪽 아래에는 그보다 큰 값만 둡니다. 이 규칙을 지키는 이진 트리가 이진 탐색 트리(binary search tree)입니다.
찾을 때는 루트에서 시작해, 찾는 값이 지금 노드보다 작으면 왼쪽, 크면 오른쪽으로 내려갑니다. 내려갈 자식이 없으면 없는 값입니다. 비교마다 반대쪽 갈래를 통째로 버리니 이진 탐색과 같은 원리입니다.
출력 없음target을 65로 바꿔 봅시다.
넣을 때도 똑같이 내려가다 빈 자리에 새 노드를 매답니다. 부모의 포인터 하나만 고치면 됩니다.
어느 노드든 왼쪽 아래는 작고 오른쪽 아래는 크니, 중위 순회하면 언제나 정렬된 순서가 나옵니다. 가장 작은 값은 루트에서 왼쪽으로 끝까지 내려가면 나옵니다.
비교 횟수는 몇 층을 내려가느냐로 정해집니다. 그런데 트리 모양은 넣는 순서에 따라 달라집니다. 1부터 15까지를 다른 순서로 넣어 봅시다.
층 수 5 · 맨 아래 값을 찾으려면 비교 5번
정렬된 순서로 넣으면 트리는 한 줄로 늘어선 연결 리스트가 되어 선형 탐색과 다를 게 없습니다. 고르게 퍼진 트리는 층마다 자리가 두 배로 늘어 노드 100만 개도 20층이면 담기지만, 한 줄이면 100만 층입니다.
1부터 15까지 열다섯 값을 어떤 순서로 빈 이진 탐색 트리에 한 번씩 넣습니다. 넣는 순서에 따라 8을 찾을 때 비교하는 횟수가 달라집니다. 8 자신과의 비교까지 세면, 가장 많을 때 몇 번일까요? 숫자로 답하세요.