이진 탐색 트리가 다른 자료 구조들에 비해서 실제로 얼마나 효율적인지 보자.

비교

이진 탐색 트리와 용도가 비슷한 자료 구조가 뭐가 있었는지 생각해보자.

일단 이진 탐색 트리를 사용하는 가장 대표적인 예시는 추상 자료형, 세트(set)와 딕셔너리(dictionary)를 구현하는 것이다.

해시 테이블을 사용해도 두 추상 자료형을 구현할 수 있었던 것, 기억하나?

기본 자료 구조 토픽에서 배웠던 해시 테이블의 시간 복잡도를 가지고 와서 이진 탐색 트리와 나란히 놓고 비교하자.

삼입, 탐색, 삭제... 세 연산 모두 이진 탐색 트리보다 해시 테이블을 사용하는 게 더 효율적이다.

그럼 이진 탐색 트리는 언제 사용하는걸까?

이진 탐색 트리에서 할 수 있고, 해시 테이블에서 할 수 없는 게 뭐가 있을지 생각하자.

이진 탐색 트리는 데이터 사이에 순서를 저장해주는 자료 구조다.

우리는 이전에 in-order 순회를 단순히 트리 안에 있는 데이터를 출력하는 용도로 이용했다.

반면 해시 테이블은 데이터 사이에 순서 관계를 저장할 수 없는 자료 구조이다.

데이터를 정렬하고 싶으면 순서를 저장하는 다른 자료 구조에 똑같은 데이터를 저장한 뒤에 정렬시켜야한다.

세트와 딕셔너리는 데이터 사이에 순서 관계를 약속하지 않는 추상 자료형이다.

하지만 이 두 가지를 사용하면서도 데이터 사이의 순서 관계를 저장해야 하는 경우들이 생길 수 있다. 이런 경우에는 해시 테이블을 사용하기 힘들다.

이럴 때 바로 이진 탐색 트리를 사용해야 한다.

정리

정리를 하면 추상 자료형, 세트나 딕셔너리를 코드로 구현할 때, 일반적인 경우에는 해시 테이블을 사용하는 게 이진 탐색 트리를 사용하는 것보다 더 효율적이다.

하지만 세트의 데이터나 딕셔너리의 key 를 정렬된 상태로 사용하고 싶을 때는 이진 탐색 트리를 사용해야 하고, 물론 이때는 해시 테이블 때보다는 연산의 효율성은 조금 포기해야한다.