CS/자료구조
[자료구조 및 프로그래밍] 10. BST 탐색 시간과 Height 사이 관계
지난 글에서는 이진 탐색트리의 개념과 Search, Add, Delete 의 구현에 대해 정리하였다. 이번 글에서는 BST의 핵심인 '탐색' 과 탐색 시간에 대해 좀 더 깊게 정리해보자. BST의 탐색 시간 모든 BST의 기능 중에서 제일 중요한 것은 BST 의 이름에도 들어있는 '탐색' 기능이다. 탐색 시간이 얼마나 걸리는지 ( 탐색을 위해 비교를 몇 번이나 하는지) 는 어떻게 측정할까? 답은 정확하게 BST 의 노드 중 찾으려는 노드의 depth + 1 (level + 1) 이다. 더보기 [트리에서 Depth, Height, Level ] Depth = 루트 노드의 depth를 0 으로 정의할 때, 자식 노드의 depth는 부모 노드의 depth + 1 이다. Level = Depth 와 같다. de..
