랜덤 바이너리 검색 트리

Question

트랩과 같은 무작위 바이너리 검색 트리는 AVL과 같은 결정 성있는 균형 잡힌 트리에 필요한 복잡한 (비용이 많이 드는) 재조정 작업을 피하면서 높은 확률로 좋은 성능 (O (log n)의 순서로) red-blackm, AA 등.

무작위 키를 간단한 BST에 추가하면 합리적으로 균형이 잡힐 것으로 예상됩니다. 간단한 이유는 n 개의 노드에 대한 균형이 잘 맞지 않는 트리의 수가 "거의 균형 잡힌"트리의 수보다 훨씬 적기 때문에 키를 삽입하기위한 임의의 순서가 허용되는 트리로 끝날 가능성이 높습니다.

"컴퓨터 프로그래밍의 기술"에서 크 누스는 경로의 평균 길이로 1.3 * lg2 (n)보다 조금 더 낫습니다. 그는 또한 임의의 트리에서 임의의 키를 삭제하면 임의성이 유지된다는 것을 알 수 있습니다 (따라서 평균 밸런싱도 양호합니다).

키가 임의 순서로 삽입되고 삭제되는 이진 검색 트리는 검색, 삽입 및 삭제의 세 가지 작업 모두에서 O (log n)의 순서로 성능을 제공 할 가능성이 높습니다. (x)는 "좋은"것으로 알려져있다 (예를 들어, 그것은 더의 확산 보장

• 은 해시 함수 h을
  :
  다음과 같은 접근 방식은 같은 좋은 특성을 줄 것인지 궁금했다 그
• k에 대한 순서 지정 대신 키에 h (x)로 설정된 순서를 사용하십시오.
• 충돌의 경우에는 키에 따라 주문하십시오. 해시 키가 충분하고 해시 함수의 범위가 키 집합보다 훨씬 큰 경우 이는 드문 것입니다.

예를 키위한 BST 수득 {4, 3, 5, 1, 2}의 순서로 삽입 될 것이다 : 해시 함수를 가정

가

    4 
       /\ 
       3 5 
       /\ 
       1 2 

(에 매핑 할) {221,142,12,380,18} 우리가 얻을 것이다.

    221(4) 
       / \ 
       142(3) 380(1) 
      / \ 
      12(5) 18(2) 

중요한 점은 키 (트리에서 자신의 "자연"순서를 저장하는 데 사용되는 같은 순서 관계에 따라 삽입되기 때문에 "일반"BST 예를 알파벳 순서에 대해, 퇴화 수 있다는 것이다)하지만 해시 함수는 "자연"키와 완전히 관련이없는 키의 순서를 유도하므로 키가 임의의 순서로 삽입 된 것과 같은 결과를 제공해야합니다.

해시 함수가 "양호"하다고 가정하는 것은 무리이지만, 불합리한 것은 아닙니다.

나는 완전히 틀릴 수도 있으므로 비슷한 접근법에 대한 언급을 찾지 못했지만 그 이유를 알 수 없습니다!

제 추론에 어떤 단점이 있습니까? 누구나 이미 그것을 시도한 적이 있습니까?

Answer 1

균형 잡힌 트리의 해시 값 분산에 의존하여 해시 값을 사용하여 간단히 주문하는 것이 좋습니다. 이것은 잘 작동하고, 좋은 해시 함수를 사용하여 실제로 적절하게 균형 잡힌 나무를 제공해야합니다.

다른 사람들이 IMO와 같은 것을 사용하지 않는 이유는 해시 함수로 주문하면 데이터 구조가 더 이상 정렬되지 않기 때문입니다. 예, 여전히 해시 함수로 정렬되지만 해시 함수가 가장 작은 요소는 일반적으로 검색해야하는 요소가 아니지만 가장 작은/가장 큰/k 번째 요소와 같은 검색은 종종 유용합니다. 데이터 구조에는 더 이상이 속성이 없으므로 해시 함수를 사용하여 O (log n) 대신 O (1) 성능을 얻기 위해 배열에 저장하는 해시 테이블을 갖는 것이 훨씬 더 합리적입니다.

Answer 2

해시 테이블을 저장하는 한 가지 방법이 아닙니까?

Answer 3

나에게 맞는 소리. 이것이 이미 공식화되었거나 적어도 언급되었는지 여부를 검색 했습니까?

단점에 대해서

: 나는 하나 명의 가능한 반대가 될 것이다 가정 : 단지 해시 테이블을 사용하는 이유 이미 해시 함수를 실행하는 가격을 지불 한 경우 "

이와 관련된 이의 당신이 가지고있다?. 이미 시간 복잡성을 해시 함수의 배포 속성에 묶었습니다.이 경우 트리는 해시 테이블을 훨씬 추가하지 않습니다. 나무는 좋아하지만 해시 테이블은 일반적으로 빠릅니다. 즉, 해시 트리의 주요 이점 해시 테이블은 해시 함수의 전체 범위를 사용하지만 해시 테이블은 모듈러스 연산에서 많은 부분을 버립니다.

Answer 4

일반적으로 저장소에 B- 트리와 같은 것을 사용합니다. 이는 일반적으로 확장 가능한 해싱이 작동하는 방식과 매우 유사합니다. 그리고 네, 일반적으로 잘 작동합니다.