이진트리2 자료구조(12) 이진 탐색 트리 이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 알 수 있다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다해도, 트리의 높이는 30을 넘지 않기 때문이다. 그렇다면 이것이 탐색에 있어서 어떤 의미를 지니겠는가? 예를 들어서 '연결 리스트'에 10억 개의 데이터가 저장되어 있다고 가정해보자. 그리고 찾는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정하자. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 한다. 반면 이진 트리의 경우에는 위치를 알고 있다면, 다시 말해 데이터에 이르는 길을 알고 있다면 루트노드에서 단말 노드에 이르기까지 총 30개의 노드를 지나는 과정에서 원하는 데이터를 찾을 수 .. 2022. 3. 17. 자료구조(8) 트리 "트리"는 고급 자료구조로 구분이 된다. 그만큼 학습에 있어서 집중을 요한다. 특히 비선형 자료구조이기때문에 많이 다르게 느껴질 수도 있다!" 트리는 계층적 관계를 표현하는 자료구조이다! 자료구조! 하면 보통은 무엇인가를 저장하고 꺼내는 것이 전부인 것으로 이해하는 경우가 많다. 앞서 보인 선형 자료구조들은 이에 초점이 맞춰져 있었으니 무리도 아니다. 하지만 자료구조는 근본적으로 무엇인가를 "표현" 하는 도구이다. 트리는 데이터의 저과 삭제가 아닌 "표현"에 초점이 맞춰져 있다. 때문에 트리의 ADT를 다음과 같이 바라보면 안된다. "데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있나요?" 대신 다음과 같이 바라봐야 한다. "트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있나요?" 노드(.. 2022. 3. 16. 이전 1 다음
