3

BST を使用してキューを実装するにはどうすればよいですか。

これがその方法ですか、すべてのノードに関連付けられたカウント値を維持しながらツリーにノードを挿入し続けますが、削除中はBSTはキュー（FIFO）のように機能するはずなので、カウントが最も低いノードでBSTから削除を開始しますツリーの値。

質問と解決策を正しく理解できましたか? そうでない場合は、質問を説明してください。

4

3 に答える 3

3

BST は実際には、キューをバックアップするために使用するのに不適切なデータ構造です。代わりに、リンクされたリストを使用する必要があります.

ただし、BST の使用を主張する場合は...

BST をプライオリティ キューとして使用し、アイテムがソートされる「キュー インデックス」も保持するラッパー タイプを定義します。ただし、現在のキュー インデックスを考慮して比較を定義する必要があります。そうしないと、インデックス タイプの最高値と最低値の差と同じ数のアイテムしか追加できないためです。

于 2012-11-18T21:36:37.053 に答える
1

次のようなキューを持つことができます。

BST // to store data
pointer to head; // Points to the head of the Queue
pointer to tail  // Points to the tail of the Queue

BST のノード構造体に、挿入の順序を表す別のノードへのポインターも追加します。

struct Node{
  int x;
  //left pointer
  //right pointer
  struct Node *next_queune_element;
}

挿入中 要素を追加する場合は、最初にポインターの末尾が指すノードにアクセスし、挿入したばかりの新しい要素 (BST ノード) を指すようにします。次に、テール ポインターを更新して、新しい要素を指すようにします。

削除中 要素を削除するときは、最初にヘッド ポインタが指すノードにアクセスnext_queune_elementし、補助一時変数に格納してノードを削除します。最後に、ヘッド ポインターが補助一時変数を指すようにします。

于 2012-11-18T21:27:42.277 に答える
0

ここでは、バイナリ検索ツリーではなく、バイナリツリーが望ましいデータ構造になると思います。キューの実装にバイナリ ツリーを使用すると、関数型プログラミングを行うときに役立つ場合があります。プッシュ操作とポップ操作のたびに高さのバランスを保つ二分木を使用して実行できるため、常にO (log n ) になります。プッシュとポップは次のようになります。

  • ツリーの一番左に要素を挿入する関数 (プッシュ関数)。
  • ツリーの一番右から要素を削除する機能 (ポップ機能)。

どちらの場合も、リバランスは掲載順に違反しません。どちらも実装も簡単です。実際には、挿入機能が変更された AVL ツリーを使用しています。ボーナスは、要素が (完全に) 注文可能である必要がないことです。

于 2019-01-30T15:12:04.300 に答える