해시 테이블에 비해 이진 검색 트리의 장점은 무엇입니까?
해시 테이블은 Theta (1) 시간의 모든 요소를 조회 할 수 있으며 요소를 추가하는 것만 큼 쉽습니다 ….하지만 그 반대 방향으로가는 이점이 확실하지 않습니다.
답변
이진 검색 트리 (참조 기반)는 메모리 효율적입니다. 필요한 것보다 더 많은 메모리를 예약하지 않습니다.
예를 들어 해시 함수에 범위가있는 R(h) = 0...100경우 요소 20 개를 해싱하는 경우에도 100 (포인터) 요소의 배열을 할당해야합니다. 이진 검색 트리를 사용하여 동일한 정보를 저장하는 경우 필요한만큼의 공간과 링크에 대한 일부 메타 데이터 만 할당합니다.
답변
다른 누구도 지적하지 않은 한 가지 장점은 이진 검색 트리를 사용하여 범위 검색을 효율적으로 수행 할 수 있다는 것입니다.
내 생각을 설명하기 위해 극단적 인 사례를 만들고 싶습니다. 키가 0에서 5000 사이 인 모든 요소를 가져오고 싶다고 가정 해 보겠습니다. 실제로 그러한 요소는 하나만 있고 키가 범위에없는 10000 개의 다른 요소가 있습니다. BST는 답을 얻을 수없는 하위 트리를 검색하지 않기 때문에 범위 검색을 매우 효율적으로 수행 할 수 있습니다.
그러나 해시 테이블에서 범위 검색을 어떻게 수행 할 수 있습니까? O (n) 인 모든 버킷 공간을 반복해야하거나 1,2,3,4 … 개가 최대 5000 개까지 존재하는지 찾아야합니다. (0에서 5000 사이의 키는 무한 세트 인 것은 어떻습니까? 예를 들어 키는 십진수 일 수 있습니다)
답변
이진 트리의 한 가지 “장점”은 모든 요소를 순서대로 나열하기 위해 순회 할 수 있다는 것입니다. 이것은 해시 테이블로는 불가능하지 않지만 해시 구조로 설계하는 정상적인 작업은 아닙니다.
답변
다른 모든 좋은 댓글 외에도 :
일반적으로 해시 테이블은 이진 트리에 비해 적은 메모리 읽기가 필요한 캐시 동작이 더 좋습니다. 해시 테이블의 경우 일반적으로 데이터를 보유하는 참조에 액세스하기 전에 단일 읽기만 발생합니다. 이진 트리가 균형 잡힌 변형이라면 어떤 상수 k에 대해 k * lg (n) 메모리 읽기 순서의 무언가가 필요합니다 .
반면에 적이 당신의 해시 함수를 알고 있다면 적이 당신의 해시 테이블을 강제로 충돌을 일으키고 성능을 크게 저하시킬 수 있습니다. 해결 방법은 패밀리에서 임의로 해시 함수를 선택하는 것이지만 BST에는 이러한 단점이 없습니다. 또한 해시 테이블 압력이 너무 커지면 비용이 많이 드는 작업이 될 수있는 해시 테이블을 확대하고 재 할당하는 경향이 있습니다. BST는 여기에서 더 간단한 동작을 가지며 갑자기 많은 데이터를 할당하고 재해 싱 작업을 수행하지 않는 경향이 있습니다.
트리는 궁극적 인 평균 데이터 구조 인 경향이 있습니다. 목록 역할을 할 수 있고 병렬 작업을 위해 쉽게 분할 할 수 있으며 O (lg n) 순서로 빠른 제거, 삽입 및 조회가 가능합니다 . 그들은 특별히 잘하지 않지만 지나치게 나쁜 행동도 없습니다.
마지막으로, BST는 해시 테이블에 비해 (순수한) 기능적 언어로 구현하기가 훨씬 쉽고 파괴적인 업데이트를 구현할 필요가 없습니다 ( 위의 Pascal 의 지속성 인수).
답변
해시 테이블에 비해 이진 트리의 주요 장점은 이진 트리가 해시 테이블로 (쉽고 빠르게) 수행 할 수없는 두 가지 추가 작업을 제공한다는 것입니다.
-
임의의 키 값 (또는 가장 가까운 위 / 아래)에 가장 가까운 (반드시 같지는 않음) 요소 찾기
-
정렬 된 순서로 트리의 내용을 반복합니다.
둘은 연결되어 있습니다. 이진 트리는 내용을 정렬 된 순서로 유지하므로 정렬 된 순서가 필요한 작업을 쉽게 수행 할 수 있습니다.
답변
(균형) 이진 검색 트리는 점근 적 복잡성이 실제로 상한이라는 장점이 있지만 해시 테이블의 “상수”시간은 상각 된 시간입니다. 부적합한 해시 함수가 있으면 결국 선형 시간으로 저하 될 수 있습니다. , 일정하지 않습니다.
답변
해시 테이블은 처음 생성 될 때 더 많은 공간을 차지합니다.-아직 삽입되지 않은 요소 (삽입 여부에 관계없이)에 대해 사용 가능한 슬롯이 있으며 이진 검색 트리는 필요한만큼만 커집니다. 있다. 해시 테이블이 더 많은 공간을 필요로 할 때 또 다른 구조로 확장하는 것은 수 많은 시간이 소요될 수 있지만 그 구현에 달려 있습니다.
