해시 테이블에 비해 BST의 장점

난이도 쉽게
자주 묻는 질문 아마존 GE 헬스 케어 퀄컴
이진 검색 이진 트리 해시 이론 나무조회수 41

모든 데이터 구조에서 가장 일반적으로 사용되는 작업은 삽입, 삭제 및 검색입니다. 해시 테이블은 O (1)의 평균 시간 복잡성으로이 세 가지 작업을 수행 할 수 있으며 이진 검색 자체 균형을 유지합니다. 나무 O (log n) 시간 복잡도를 사용합니다.

처음에는 Hash Table의 작업 시간 복잡성이 BST보다 적기 때문에 Hash Tables가 모든 형식에서 자체 균형 BST보다 나은 것처럼 보입니다. 그러나 해시 테이블보다 BST를 선호하는 몇 가지 조건이나 요구 사항이 있습니다.

해시 테이블에 비해 BST의 장점

해시 테이블에 비해 BST의 장점

  1. 자체 균형 이진 검색 트리는 데이터를 정렬 된 형식으로 저장합니다. 즉, 순서대로 수행하여 정렬 된 데이터를 얻을 수 있습니다. 순회 BST에서. 하지만 해시에서는 테이블, 우리는 모든 요소를 ​​순회하고 정렬 기술을 사용하여 정렬해야 합니다.
    시간 복잡성 (해시 테이블) = O (n 로그 (n))
    시간 복잡성 (BST) = O (N)
  2. 최대 노드, 최소 노드, 주어진 값에 가장 가까운 노드 또는 주어진 값보다 약간 큰 노드 등을 찾습니다. 모든 작업은 자체 균형 이진 검색 트리에서 O (log n) 시간 내에 수행 될 수 있습니다. 그러나 해시 테이블의 경우 언급 된 쿼리에 대한 답을 얻으려면 모든 요소를 ​​탐색해야합니다.
    시간 복잡성 (해시 테이블) = O (N)
    시간 복잡성 (BST) = O (로그 n)
  3. 사용자 정의 된 이진 검색 트리 구현은 사용자 정의 된 해시 테이블 구현보다 훨씬 간단합니다. 다른 언어는 사용자 정의 된 해시 테이블 구현을위한 빌드 내 라이브러리를 제공합니다.
  4. 자체 균형 이진 검색 트리에서 삽입, 삭제, 업데이트 및 검색과 같은 모든 작업의 ​​상한은 O (log n)입니다. 그러나 해시 테이블의 경우 상한이 없습니다. 작업은 O (1)의 평균 복잡성으로 발생하지만 경우에 따라 복잡성이 증가 할 수 있습니다. 라이브러리가 해시 테이블을 구현하는 방식으로 인해 증가가 발생할 수 있습니다. 특히 해시 테이블 크기 조정이 완료되면 비용이 많이 드는 작업입니다.

따라서 이진 검색 트리와 해시 테이블은 서로 다른 상황에서 고유 한 장점이 있습니다. 요구 사항에 따라 이진 검색 트리와 해시 테이블 중에서 선택해야합니다.

레퍼런스 1    참조 2

Translate »