해시 테이블에 비해 이진 검색 트리의 장점

해시 테이블에 비해 이진 검색 트리의 장점

---

해시 테이블에 비해 이진 검색 트리의 장점은 무엇입니까?

해시 테이블은 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 의 지속성 인수).

---

해시 테이블에 비해 이진 트리의 주요 장점은 이진 트리가 해시 테이블로 (쉽고 빠르게) 수행 할 수없는 두 가지 추가 작업을 제공한다는 것입니다.

• 임의의 키 값 (또는 가장 가까운 위 / 아래)에 가장 가까운 (반드시 같지는 않음) 요소 찾기

• 정렬 된 순서로 트리의 내용을 반복합니다.

둘은 연결되어 있습니다. 이진 트리는 내용을 정렬 된 순서로 유지하므로 정렬 된 순서가 필요한 작업을 쉽게 수행 할 수 있습니다.

---

(균형) 이진 검색 트리는 점근 적 복잡성이 실제로 상한이라는 장점이 있지만 해시 테이블의 "상수"시간은 상각 된 시간입니다. 부적합한 해시 함수가 있으면 결국 선형 시간으로 저하 될 수 있습니다. , 일정하지 않습니다.

---

해시 테이블은 처음 생성 될 때 더 많은 공간을 차지합니다.-아직 삽입되지 않은 요소 (삽입 여부에 관계없이)에 대해 사용 가능한 슬롯이 있으며 이진 검색 트리는 필요한만큼만 커집니다. 있다. 해시 테이블이 더 많은 공간을 필요로 할 때 또 다른 구조로 확장하는 것은 수 많은 시간이 소요될 수 있지만 그 구현에 달려 있습니다.

---

이진 검색 트리는 새 트리가 반환되지만 이전 트리는 계속 존재 하는 영구 인터페이스 로 구현 될 수 있습니다 . 신중하게 구현 된 이전 트리와 새 트리는 대부분의 노드를 공유합니다. 표준 해시 테이블로는이를 ​​수행 할 수 없습니다.

---

이진 트리는 검색 및 삽입 속도가 더 느리지 만 중위 순회의 매우 멋진 기능이 있습니다. 이는 기본적으로 트리의 노드를 정렬 된 순서로 반복 할 수 있음을 의미합니다.

해시 테이블의 항목을 반복하는 것은 모두 메모리에 흩어져 있기 때문에 별 의미가 없습니다.

---

BST는 또한 O (logn) 시간에 "findPredecessor"및 "findSuccessor"작업 (다음으로 가장 작은 요소와 다음으로 가장 큰 요소를 찾기 위해)을 제공하며 이는 매우 편리한 작업 일 수도 있습니다. Hash Table은 그 시간 효율성을 제공 할 수 없습니다.

---

에서 코딩 인터뷰를 크래킹, 6 판

BST (균형 이진 검색 트리)를 사용하여 해시 테이블을 구현할 수 있습니다. 이것은 우리에게 O (log n) 조회 시간을 제공합니다. 이것의 장점은 더 이상 큰 배열을 할당하지 않기 때문에 잠재적으로 더 적은 공간을 사용한다는 것입니다. 때때로 유용 할 수있는 순서대로 키를 반복 할 수도 있습니다.

---

정렬 된 방식으로 데이터에 액세스하려면 정렬 된 목록이 해시 테이블과 병렬로 유지되어야합니다. 좋은 예는 .Net의 사전입니다. ( http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx 참조 ).

이것은 삽입 속도가 느려지는 부작용이있을뿐만 아니라 b- 트리보다 더 많은 양의 메모리를 소비합니다.

또한 b- 트리가 정렬되어 있기 때문에 결과 범위를 찾거나 통합 또는 병합을 수행하는 것이 간단합니다.

---

또한 용도에 따라 다르며 Hash는 정확한 일치를 찾을 수 있습니다. 범위를 쿼리하려면 BST가 선택입니다. 많은 데이터 e1, e2, e3 ..... en이 있다고 가정합니다.

해시 테이블을 사용하면 일정한 시간에 모든 요소를 ​​찾을 수 있습니다.

e41보다 크고 e8보다 작은 범위 값을 찾으려면 BST가 신속하게 찾을 수 있습니다.

The key thing is the hash function used to avoid a collision. Of course, we cannot totally avoid a collision, in which case we resort to chaining or other methods. This makes retrieval no longer constant time in worst cases.

Once full, hash table has to increase its bucket size and copy over all the elements again. This is an additional cost not present over BST.

---

A hashmap is a set associative array. So, your array of input values gets pooled into buckets. In an open addressing scheme, you have a pointer to a bucket, and each time you add a new value into a bucket, you find out where in the bucket there are free spaces. There are a few ways to do this- you start at the beginning of the bucket and increment the pointer each time and test whether its occupied. This is called linear probing. Then, you can do a binary search like add, where you double the difference between the beginning of the bucket and where you double up or back down each time you are searching for a free space. This is called quadratic probing. OK. Now the problems in both these methods is that if the bucket overflows into the next buckets address, then you need to-

1. Double each buckets size- malloc(N buckets)/change the hash function- Time required: depends on malloc implementation
2. Transfer/Copy each of the earlier buckets data into the new buckets data. This is an O(N) operation where N represents the whole data

OK. but if you use a linkedlist there shouldn't be such a problem right? Yes, In linked lists you don't have this problem. Considering each bucket to begin with a linked list, and if you have 100 elements in a bucket it requires you to traverse those 100 elements to reach the end of the linkedlist hence the List.add(Element E) will take time to-

1. Hash the element to a bucket- Normal as in all implementations
2. Take time to find the last element in said bucket- O(N) operation.

The advantage of the linkedlist implementation is that you don't need the memory allocation operation and O(N) transfer/copy of all buckets as in the case of the open addressing implementation.

So, the way to minimize the O(N) operation is to convert the implementation to that of a Binary Search Tree where find operations are O(log(N)) and you add the element in its position based on it's value. The added feature of a BST is that it comes sorted!

---

Hash Tables are not good for indexing. When you are searching for a range, BSTs are better. That's the reason why most database indexes use B+ trees instead of Hash Tables

---

Binary search trees are good choice to implement dictionary if the keys have some total order (keys are comparable) defined on them and you want to preserve the order information.

As BST preserves the order information, it provides you with four additional dynamic set operations that cannot be performed (efficiently) using hash tables. These operations are:

1. Maximum
2. Minimum
3. Successor
4. Predecessor

All these operations like every BST operation have time complexity of O(H). Additionally all the stored keys remain sorted in the BST thus enabling you to get the sorted sequence of keys just by traversing the tree in in-order.

In summary if all you want is operations insert, delete and remove then hash table is unbeatable (most of the time) in performance. But if you want any or all the operations listed above you should use a BST, preferably a self-balancing BST.

---

Binary search trees can be faster when used with string keys. Especially when strings are long.

Binary search trees using comparisons for less/greater which are fast for strings (when they are not equal). So a BST can quickly answer when a string is not found. When it's found it will need to do only one full comparison.

In a hash table. You need to calculate the hash of the string and this means you need to go through all bytes at least once to compute the hash. Then again, when a matching entry is found.

---

main advantage of hash table is that it does almost all ops in ~=O(1). And its very easy to understand and implement. It does solve many "interview problems" efficiently. So if u want to crack a coding interview, make best friends with hash table ;-)

참고URL : https://stackoverflow.com/questions/4128546/advantages-of-binary-search-trees-over-hash-tables