二分探索木の定義を見つけようとしていますが、至る所でさまざまな定義を見つけ続けています。
特定のサブツリーについて、左側の子キーはルート以下であると言う人もいます。
特定のサブツリーの場合、正しい子キーはルート以上であると言う人もいます。
また、私の古い大学のデータ構造の本には、「すべての要素にはキーがあり、同じキーを持つ要素は 2 つとない」と書かれています。
bstの普遍的な定義はありますか? 特に、同じキーの複数のインスタンスを持つツリーをどうするかに関して。
EDIT：多分私は不明確でした、私が見ている定義は
1) 左 <= ルート < 右
2) 左 < ルート <= 右
3) 重複キーが存在しないように、左 < ルート < 右。
多くのアルゴリズムは、重複を除外するように指定します。たとえば、MIT Algorithms book のサンプル アルゴリズムは、通常、重複のない例を示しています。重複を実装するのはかなり簡単です (ノードのリストとして、または特定の方向に)。
ほとんどの (私が見た) 左の子を <= として指定し、右の子を > として指定します。実際には、右側または左側の子のいずれかがルート ノードと等しくなるようにする BST では、重複ノードが許可されている検索を完了するために、追加の計算ステップが必要になります。
ノードの一方の側に「=」値を挿入するには、その側のツリーを書き直してノードを子として配置する必要があるため、ノードでリストを使用して重複を保存するのが最善です。そうしないと、ノードがグランドとして配置されます。 -child は、下のある時点で、検索効率の一部を排除します。
クラスルームの例のほとんどは、概念を描写して伝えるために単純化されていることを覚えておく必要があります。現実世界の多くの状況では、しゃがむ価値はありません。しかし、「すべての要素にはキーがあり、同じキーを持つ要素は 2 つとない」というステートメントは、要素ノードでリストを使用しても違反されません。
だからあなたのデータ構造の本が言ったことに従ってください！
編集：
バイナリ検索ツリーの普遍的な定義には、データ構造を 2 つの方向のいずれかでトラバースすることに基づいてキーを格納および検索することが含まれます。実用的な意味では、値が <> の場合、2 つの「方向」のいずれかでデータ構造をトラバースすることを意味します。したがって、その意味では、値の重複はまったく意味がありません。
これは BSP、つまり二分探索パーティションとは異なりますが、それほど違いはありません。検索するアルゴリズムは、「旅行」の 2 つの方向のいずれかを持っているか、完了しています (成功したか失敗したか)。したがって、最初の回答が「普遍的な定義」の概念に対応していなかったことをお詫びします。トピック (バイナリ検索の一部としてではなく、検索が成功した後に処理するもの。)
二分探索木が赤黒木である場合、または何らかの「木の回転」操作を行う場合は、ノードが重複すると問題が発生します。あなたのツリールールがこれだと想像してみてください：
左<ルート<=右
ここで、ルートが5、左の子がnil、右の子が5の単純なツリーを想像してください。ルートで左回転を行うと、左の子が5になり、右の子がルートに5になります。ゼロであること。これで、左側のツリーの何かがルートと等しくなりますが、上記のルールは左<ルートと見なされます。
私は何時間もかけて、赤/黒の木がときどき順不同で横断する理由を理解しようとしました。問題は、上記で説明したことでした。うまくいけば、誰かがこれを読んで、将来のデバッグの時間を節約できます！
3 つの定義はすべて受け入れられ、正しいものです。これらは、BST のさまざまなバリエーションを定義します。
あなたの大学のデータ構造の本は、その定義が唯一可能なものではないことを明確にしていませんでした。
確かに、重複を許可すると複雑さが増します。「左 <= ルート < 右」という定義を使用し、次のようなツリーがある場合:
3
/ \
2 4
次に、このツリーに「3」の重複キーを追加すると、次のようになります。
3
/ \
2 4
\
3
重複は連続したレベルにないことに注意してください。
これは、上記のように BST 表現で重複を許可する場合に大きな問題になります。重複は任意の数のレベルで区切られている可能性があるため、重複の存在を確認することは、ノードの直接の子を確認するだけでは簡単ではありません。
この問題を回避するオプションは、重複を構造的に (個別のノードとして) 表現せず、代わりにキーの出現回数をカウントするカウンターを使用することです。前の例では、次のようなツリーになります。
3(1)
/ \
2(1) 4(1)
重複した「3」キーを挿入すると、次のようになります。
3(2)
/ \
2(1) 4(1)
これにより、ルックアップ、削除、および挿入操作が簡素化されますが、余分なバイトとカウンター操作が発生します。
BST では、ノードの左側で下降するすべての値は、ノード自体よりも小さい (または等しい、後述)。同様に、ノードの右側で下降するすべての値は、そのノード値(a)より大きい (または等しい) ことになります。
一部の BSTは、重複する値を許可することを選択する場合があるため、上記の「または等しい」修飾子です。次の例は、明確にすることができます。
14
/ \
13 22
/ / \
1 16 29
/ \
28 29
これは、重複を許可する BST を示しています(b) - 値を見つけるには、ルート ノードから開始し、検索値がノード値より小さいか大きいかに応じて、左または右のサブツリーを下っていくことがわかります。
これは、次のような方法で再帰的に実行できます。
def hasVal (node, srchval):
if node == NULL:
return false
if node.val == srchval:
return true
if node.val > srchval:
return hasVal (node.left, srchval)
return hasVal (node.right, srchval)
そしてそれを呼び出す：
foundIt = hasVal (rootNode, valToLookFor)
値が見つかったら、同じ値の他のノードを検索し続ける必要がある場合があるため、重複すると少し複雑になります。hasVal少なくとも1つ存在するかどうかだけで、いくつあるかは問題ではないため、明らかにそれは問題ではありません。ただしcountVal、いくつあるかを知る必要があるため、 のようなものには問題があります。
(a)特定のキーの検索方法を調整すれば、必要に応じて実際に逆方向に並べ替えることができます。BST は、昇順か降順かに関係なく、ソートされた順序を維持するだけで済みます (または、すべての奇数が昇順で、次にすべての偶数が降順のような奇妙な多層ソート方法でさえ) は関係ありません。
(b)興味深いことに、ソート キーがノードに保存されている値全体を使用する場合 (同じキーを含むノードがそれらを区別するための他の追加情報を持たないようにするため)、各ノードにカウントを追加することでパフォーマンスが向上する可能性があります。ノードの複製を許可します。
主な利点は、重複を追加または削除すると、新しいノードを挿入または削除するのではなく、単純にカウントが変更されることです (ツリーの再バランスが必要になるアクション)。
したがって、アイテムを追加するには、まずそれが既に存在するかどうかを確認します。その場合は、カウントを増やして終了します。そうでない場合は、カウントが 1 の新しいノードを挿入してから再調整する必要があります。
アイテムを削除するには、それを見つけてカウントを減らします。結果のカウントがゼロの場合にのみ、ツリーから実際のノードを削除してバランスを取り直します。
ノードが少ないため、検索も高速になりますが、大きな影響ではない可能性があります。
たとえば、次の 2 つのツリー (左側にカウントなし、右側にカウント) は同等です (カウント ツリーでは、 item のコピーをi.c意味します)。ci
__14__ ___22.2___
/ \ / \
14 22 7.1 29.1
/ \ / \ / \ / \
1 14 22 29 1.1 14.3 28.1 30.1
\ / \
7 28 30
22左側のツリーからリーフ ノードを削除するには、リバランスが必要です (高さの差が 2 になっているため)22-29-28-30以下のような結果のサブツリー (これは1 つのオプションであり、「高さの差は 0 または 1 でなければならない」を満たすものもあります) " ルール）：
\ \
22 29
\ / \
29 --> 28 30
/ \ /
28 30 22
右側のツリーで同じ操作を行うのは、ルート ノードを から22.2に変更する22.1だけです (リバランスは必要ありません)。
Cormen、Leiserson、Rivest、Stein による著書「アルゴリズムの紹介」第 3 版では、二分探索木 (BST) が重複を許容するものとして明示的に定義されています。これは、図 12.1 と次の図 (287 ページ) で確認できます。
「二分探索木のキーは常に、二分探索木のプロパティを満たすような方法で格納されます:
xを二分探索木のノードとします。yが の左部分木のノードである場合、 が であるx場合y:key <= x:key。yの右側のサブツリーにあるノードx、次にy:key >= x:key."
さらに、赤黒木は 308 ページで次のように定義されています。
「赤黒木は、ノードごとに 1 ビット余分なストレージ (色) を持つ二分探索木です。」
したがって、この本で定義されている赤黒木は重複をサポートしています。
どの定義も有効です。実装に一貫性がある限り (常に等しいノードを右側に配置するか、常に左側に配置するか、絶対に許可しない)、問題ありません。それらを許可しないのが最も一般的だと思いますが、許可されていて、左または右に配置されている場合でも、BST です。
赤黒ツリーの実装に取り組んでいると、複数のキーを使用してツリーを検証する際に問題が発生していましたが、赤黒の挿入ローテーションで制約を緩める必要があることに気付きました。
left <= root <= right
私が見ていたどのドキュメントも重複キーを許可しておらず、それを説明するために回転メソッドを書き直したくなかったので、ノードを変更してノード内で複数の値を許可し、重複キーを許可しないことにしました。木。
あなたが言った3つのことはすべて真実です。
ツリーを逆にして小さなキーを右側に配置できると思いますが、実際には「左」と「右」の概念はまさにそれです。実際には左を持たないデータ構造について考えるのに役立つ視覚的な概念です。または正しいので、実際には問題ではありません。
重複キー • 同じキーを持つデータ項目が複数ある場合はどうなりますか? – これは、赤黒木でわずかな問題を引き起こします。– 同じキーを持つノードが、同じキーを持つ他のノードの両側に分散されていることが重要です。– つまり、キーが 50、50、50 の順序で到着する場合、 • 2 番目の 50 は最初のキーの右側に移動し、3 番目の 50 は最初のキーの左側に移動します。• そうしないと、ツリーのバランスが崩れます。• これは、挿入アルゴリズムのある種のランダム化プロセスによって処理できます。– ただし、同じキーを持つすべてのアイテムを検索する必要がある場合、検索プロセスはより複雑になります。• 同じキーを持つアイテムを非合法化する方が簡単です。– この議論では、重複は許可されないと仮定します
重複キーを含むツリーのノードごとにリンクされたリストを作成し、リストにデータを格納できます。
1.) 左 <= ルート < 右
2.) 左 < ルート <= 右
3.) 重複キーが存在しないように、左 < ルート < 右。
アルゴリズムの本を探しに行く必要があるかもしれませんが、私の頭のてっぺん (3) は正規形です。
(1) または (2) は、重複ノードを許可し始め、(リストを含むノードではなく) ツリー自体に重複ノードを配置した場合にのみ発生します。
要素の順序関係 <= は全順序であるため、関係は再帰的でなければなりませんが、通常、二分探索木 (別名 BST) は重複のない木です。
それ以外の場合は、重複がある場合は、同じ削除機能を 2 回以上実行する必要があります。