또한 힙인 균형 이진 검색 트리

각 요소에 두 개의 키가있는 데이터 구조를 찾고 있습니다. 그 중 하나는 구조가 BST이고 다른 하나는 데이터 구조가 힙입니다. 약간의 검색으로 Treap이라는 구조를 발견했습니다. BST를 균형있게 만들기 위해 힙 키에 무작위로 분포 된 힙 속성을 사용합니다!또한 힙인 균형 이진 검색 트리

내가 원하는 것은 균형 잡힌 BST이며 힙이 될 수도 있습니다. 내가 선택한 순서대로 힙 키를 사용하여 요소를 삽입하면 Treap의 BST가 불균형해질 수 있습니다.

이러한 데이터 구조가 있습니까?

출처

2012-09-08 saeedn

우선 순위 검색 트리는 균형 잡힌 BST 및 힙인 구조입니다. 자세한 내용은 this paper 또는이 설명서 : "Handbook of Data Structures and Applications" (18.5 장)을 참조하십시오.

이 구조는 주어진 범위 내에서 "힙"키와 "BST"키가 최소한 인 요소를 효율적으로 검색하는 데 사용할 수 있습니다.

출처

2012-09-08 09:33:31

그것은 내가 원하는 것보다 조금 더 복잡했지만 도움이되었습니다. 감사! – saeedn

FWIW,이 답변은 두 참조가 모두 인증 (종이)이거나 유료 텍스트 (핸드북)이므로 다소 가려져 있습니다. –

또한 힙인 균형 이진 검색 트리

답변

관련 문제