問題タブ [intrusive-containers]

質問する

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

46 問題
Newest
Active
Bountied
318
Unanswered
0 投票する
0 に答える
106 参照

c++ - ブースト AVL ツリーのマージと分割がありませんか?

Boost はboost::container::set/map/multiset/multimap、基礎となる二分探索ツリー (BST)を構成できる場所を提供し、AVL ツリーとして選択できます。

Red-Black ツリーよりも AVL ツリーを好む理由の 1 つ (おそらく最も重要な理由) は、複雑さの操作mergeと操作です。しかし、驚いたことに、これらの操作は提供されていないようです。ドキュメントでは、要素単位の複雑な操作として説明されています (これは、基になる BST 実装に関係なく!?)、ドキュメントでは!についても言及されていません。splitO(logN)boost::containermergeO(NlogN)split

については言えませんがmerge、についてsplitは、一定時間の問題によってその欠如が正当化される可能性があると推測できます。しかし、これは、侵入型のコンテナーを持ち、各ノードでサブツリー ノードの数を保持することで修正できます。sizesplitO(logN)

もありますが、ドキュメントに AVLとアルゴリズムがboost::intrusive::avl_set見つかりませんでした。mergesplit

質問は次のとおりです。

  1. の複雑さをset/map/multiset/multimap提供しmerge、操作する、完全に機能する、すぐに使用できる AVL ベースの実装はありますか?splitO(logN)
  2. そうでない場合、どのように使用してビルドできboost::intrusive::avl_setますか?

12345678910