해시 테이블 (Hash Table)

해시 테이블은 키-값 쌍을 저장하는 데이터 구조로, 해시 함수를 사용하여 키를 해시 값으로 변환한 후, 이를 통해 저장 위치를 결정.

장점
검색 속도: 평균적으로 O(1)의 시간 복잡도로 검색이 가능함.
삽입 및 삭제 속도: 평균적으로 O(1)로 삽입 및 삭제가 빠름.
효율적인 메모리 사용: 적절한 해시 함수를 사용하면 메모리 사용이 효율적일 수 있음.

단점 충돌 문제: 서로 다른 키가 동일한 해시 값을 가질 경우 충돌이 발생함. 이를 해결하기 위한 추가적인 처리(체이닝, 오픈 주소법 등)가 필요함.
정렬 불가능: 해시 테이블은 데이터가 정렬되지 않으며, 순서가 보장되지 않음.
메모리 사용: 해시 테이블의 크기를 정해놓고 사용하는 경우, 사용하지 않는 공간이 발생할 수 있음.


이진 검색 트리 (Binary Search Tree)

이진 검색 트리는 이진 트리의 일종으로, 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값이, 오른쪽 서브트리에는 큰 값이 위치하는 구조임.

장점
정렬된 구조: 이진 검색 트리는 자동으로 정렬된 구조를 가지므로, 범위 검색이 용이함.
순회 가능: 중위 순회를 통해 데이터를 정렬된 순서로 쉽게 접근할 수 있음.
동적 크기: 노드가 추가되거나 삭제될 때 동적으로 크기가 조정됨.

단점
검색 속도: 최악의 경우 O(n)으로 검색 속도가 느려질 수 있음 (균형이 맞지 않을 경우).
균형 유지 필요: 균형 이진 검색 트리(예: 레드-블랙 트리, AVL 트리)를 사용하지 않으면 성능 저하가 발생할 수 있음.
삽입 및 삭제 속도: 최악의 경우 O(n)으로 삽입 및 삭제 속도가 느려질 수 있음.


요약

특징 해시 테이블 이진 검색 트리
검색 시간 복잡도 O(1) (평균) O(log n) (균형 상태일 때)
삽입 시간 복잡도 O(1) (평균) O(log n) (균형 상태일 때)
삭제 시간 복잡도 O(1) (평균) O(log n) (균형 상태일 때)
정렬 여부 정렬되지 않음 자동 정렬됨
메모리 사용 해시 충돌 시 추가 메모리 필요 동적으로 메모리 사용
순회 가능성 순회 불가능 중위 순회 가능

참고