2

I'm looking for a data structure where each element in it has two keys. With one of them the structure is a BST and looking at the other one, data structure is a heap. With a little search, I found a structure called Treap. It uses the heap property with a random distribution on heap keys to make the BST balanced!

What I want is a Balanced BST, which can be also a heap. The BST in Treap could be unbalanced if I insert elements with heap Key in the order of my choice.

Is there such a data structure?

4

1 に答える 1

1

Priority Search Tree は、Balanced BST と Heap の両方である構造です。詳細については、この論文または本「Handbook of Data Structures and Applications」 (第 18.5 章) を参照してください。

この構造を使用して、指定された範囲内のすべての「ヒープ」キーと「BST」キーの最小値を持つ要素を効率的に検索できます。

于 2012-09-08T09:33:31.923 に答える