問題タブ [2-3-tree]

2〜3ツリーを使用するよりもAVLを使用する方が好ましいのか、またはその逆であるのか、誰かに教えてもらえますか？その理由は何ですか？

どうも

クラスの先生から、2-3 ツリーに挿入するようにという質問がありました。

私が行ったのは上の方法です。そして、彼が欲しかったのは以下の方法です。どちらが正しい方法であるか教えてください。ウェブを調べたところ、両方の方法が表示されています。しかし、なぜ10点を失ったのかはまだわかりません! 助けてくれてありがとう。

次のノード構造を持つ 2-3 ツリーがあります。

問題は、ツリー全体を解析する方法がわからないことです。あなたは単に正しい道に行くので、私たちはそれをどのように検索するかを知っています. しかし、ツリー内のすべてのノードを確認するにはどうすればよいですか?

私は、割り当てのさまざまな段階に分割されたいくつかの異なる操作をサポートすることになっている 2 ～ 3 個の検索ツリーを作成する割り当てを受けました。ステージ 1 では、操作 get、put、および size をサポートすることになっています。私は現在 get 操作を実装しようとしていますが、行き詰まっており、続行する方法に頭を悩ませることができないため、自分が書いたすべてのコードに疑問を呈しており、他の誰かの入力が必要だと感じています.

2 ～ 3 個の検索ツリーを作成する方法を調べてみましたが、意味をなさない、または必要な機能を実行していないコードが大量に見つかりました。ゼロからの自己、そして今ここにいます。

私のノードクラス

マイツリー作成教室

私が自分で言えることは、values[]各キーにバインドする方法を見つける必要があるということですが、その方法がわかりません。寝不足か、この考え方にとらわれているのかもしれません。

そのため、2-3 ツリーで正しい先祖を見つけるのに苦労しています。任意の高さの 2 ～ 3 ツリーでは、いくつかのケースを探す必要があります。

私のノードは次のように設計されています。

ノードの適切な祖先を見つけるためのアルゴリズムまたは類似のものはありますか?

たとえば、H の祖先 (提供されたツリーの最下部) を探していたとします。H の祖先がツリーのルートにある H であることは視覚的に明らかです。ただし、それには 4 つの親リンクをジャンプアップする必要があります。ツリーは任意のサイズになる可能性があり、これが問題です。

私の最終的な目標は、2-3 ツリーを順番に走査する反復子を作成することです。祖先ノードを見つける目的は、祖先ノードが、その親ノードの正しい子であるリーフ ノードの順序どおりの後継ノードになることです。繰り返しますが、上記の例のように。

アルゴリズムへのアプローチ方法がわかりません。私はそのようなことを考えていました：

誰かがより良いアイデアを持っていますか？