이진트리 탐색1 자료구조(12) 이진 탐색 트리 이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 알 수 있다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다해도, 트리의 높이는 30을 넘지 않기 때문이다. 그렇다면 이것이 탐색에 있어서 어떤 의미를 지니겠는가? 예를 들어서 '연결 리스트'에 10억 개의 데이터가 저장되어 있다고 가정해보자. 그리고 찾는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정하자. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 한다. 반면 이진 트리의 경우에는 위치를 알고 있다면, 다시 말해 데이터에 이르는 길을 알고 있다면 루트노드에서 단말 노드에 이르기까지 총 30개의 노드를 지나는 과정에서 원하는 데이터를 찾을 수 .. 2022. 3. 17. 이전 1 다음
