2

私はたくさんの木のデータ構造を見ていましたが、本当に混乱しています。基本的なバイナリ ツリー (BST Red black trees などの多数の実装も) を理解しているようですが、N'ary ツリーに関する情報が本当に必要です。さまざまな種類の N 進ツリーと、それらのパフォーマンスの比較を研究する必要があります。私が今までに見た唯一の N アリ ツリーは B+ ツリーです。N'Ary ツリーで最も速いのはどれかを知る必要があります。つまり、最も最適化された時間の複雑さに関しては、空間の複雑さは問題になりません。

4

1 に答える 1

7

一般に、何かをK-aryツリーにすることは、バイナリツリー（ ）に対$ k> 2 $​​して漸近的な利点を与えません。たとえば、平衡二分木を検索することは時間内に行うことができます。バランスの取れたk-aryツリーを検索すると、が得られます。が定数であると仮定すると、他のベースの場合、漸近的に同等になります（成長率は大規模でも同じになります）。つまり、anyおよび。と同等です。したがって、。$ k = 2 $$ \ mathcal O \ left（log_2 \ n \ right）$$ \ mathcal O \ left（k \ cdot log_k \ n \ right）$$ k $$ log_k n $$ log n $$ n $$ \ mathcal O \ left（log_i \ n \ right）$$ \ mathcal O \ left（log_j \ n \ right）$$ i $$ j $$ \ mathcal O \ left（k \ cdot log_k \ n \ right）= \ $ \ mathcal O \ left（log \ n \ right）$

ただし、実際には、各ノードにはノードが隣接しているため、k-aryツリーの方がメモリアクセスパターンが向上する可能性があります$ k $。つまり、ツリーの高さは短くなります（wikipediaでは$ h $、完全なk-aryツリーの高さを次のように示しています。 $ h = \ left \ lceil \ log_k（k-1）+ \ log_k（n）-1 \ right \ rceil $、これはどの定数でも漸近的に同じです$ k $）、リーフノードには複数の順序どおりのキーを含めることができるため、トラバーサルのジャンプも少なくなる可能性があります。

于 2012-09-09T09:19:13.153 に答える