[면접 준비] 해시 테이블과 이진 검색트리 비교하기

학습 키워드: hash table, binary search tree

2024-08-13 면접 카타 질문

해시테이블과 이진 검색트리를 비교하고 장단점을 이야기해주세요:

 해시 테이블(Hash Table)은 key-value 쌍으로 데이터를 저장하는 자료 구조로, 해시 함수(Hash Function)을 통해 key값을 해시로 변환하여 고유한 index를 얻어낸 뒤 value를 bucket이라고 불리는 내부 배열에 저장합니다. O(1)의 시간 복잡도로 데이터 접근이 매우 빠르다는 장점이 있지만, 해시 함수의 설계 상태에 따라 발생할 수 있는 문제(성능 저하, 키 값 충돌 등)들을 해결해야 한다는 단점이 있습니다. 또한, 데이터가 정렬되어있지 않기 때문에 순차 접근(Sequential Access)이 어렵습니다.

 

 이진 검색트리는 이진 트리의 두 자식 노드에서 왼쪽 노드가 더 작은 값을, 오른쪽 노드가 더 큰 값을 가지게되는 구조입니다. 데이터의 추가, 삭제 및 접근에서 균등하게 O(log n)의 시간 복잡도를 가지며, 앞선 특징으로 인해 최댓값이나 최솟값을 찾기가 쉽다는 장점이 있습니다. 반면에 노드가 한 쪽으로만 채워진 비대칭 트리의 경우 O(n)의 시간 복잡도를 가지게 되므로 이를 방지하기 위해 트리의 균형을 맞춰주는 추가적인 관리 작업이 필요합니다. 데이터가 정렬되어 있어 범위 검색이 용이합니다.

 

 

--