CH11-2 이진탐색 트리(1)
앞서 이진트리는 공부했다. 이번에 공부할 이진탐색 트리는, 단순 이진트리가 아니라 탐색에 특화된 이진트리를 말한다.
자료구조를 공부할떄 탐색을 공부한다는 것은 이진탐색트리를 공부한다는 것과 유사하다.
이진탐색트리는 ‘삭제’와 관련된 부분이 까다롭게 여겨질 수 있다. 트리의 구조를 변경하는 내용이 있기 때문임.
이진탐색트리는 이진트리+데이터의 저장 규칙이다.
이진탐색 트리의 탐색은 데이터의 저장규칙을 근거로 이루어진다. 그리고 데이터의 저장규칙은, 삭제의 규칙에도 영향을 준다.
앞서 배운 이진트리에서는 저장과 삭제는 할 수 있었지만 저장 규칙이 있었던건 아니다.
이진탐색트리는 탐색에 특화된 자료구조로, 탐색에 별도의 알고리즘을 필요로 하지 않을 정도이다.
연결리스트는 우리가 찾는 데이터의 위치정보를 알아도, 거치는 노드의 수가 어마어마하다. 이런걸 보면 탐색을 고려한 자료구조가 어떤 것인지 알 수 있다.
이진탐색 트리에서 위치정보가 있다는것은 해당 데이터를 찾아가기 위한 경로가 결정이 된다는 의미이다.
이진탐색트리의 저장규칙을 소개하겠다.
