問題タブ [binary-search-tree]
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.
python - Python で二分探索木を表現する
Python で二分探索木を表現するにはどうすればよいですか?
algorithm - ツリー内のノードはそれ自体の祖先と見なされますか?
コンピュータサイエンスの文脈における「祖先」の定義についてのコンセンサスは何であるのか疑問に思います。
アルゴリズム入門、第2版、p。Tree-Successor(x)
259奇妙に思われるアルゴリズムの説明があります。ノードxの後継を見つける際に、
[...]ノードxの右側のサブツリーが空で、xに後続のyがある場合、yはxの最も低い祖先であり、その左側の子はxの祖先でもあります。
2
キーと子1
を持つルートを持つ二分探索木では3
、の後続1
はその親2
です。この場合、xはxの後継子yの左の子です。したがって、本の定義によれば、私が何かを見逃していない限り、xはそれ自体の祖先でなければなりません。
これについての正誤表には何も見つかりませんでした。
python - Pythonのバイナリ検索ツリーが機能しない
バイナリ検索ツリーを実装するために上記のコードを記述しましたが、insertメソッドが期待どおりに機能せず、ルート要素も追加できません。原因がわからない。
algorithm - 二分探索ツリーで削除しますか?
本Data Structures and Algorithms: Annotated Reference with Examples で使用されているバイナリ ツリー削除ノード アルゴリズムを読んでいます。
34 ページ、ケース 4 (右と左の両方のサブ ツリーを持つノードを削除)、本に記載されているアルゴリズムに従って動作しないように見えます。
次の行は、サブツリーから最大値をどのように削除しますかFindParent(largestValue).Right <- 0
algorithm - 特定の二分木について、最大の二分探索部分木を見つける
特定の二分木について、二分探索木でもある最大の部分木を見つけますか?
例:
入力:
出力:
algorithm - 二分探索木について質問がありますか?
今日、私の教授はクラスで、これまで聞いたことのないバランス二分探索木があると言いました。回転のないバランス二分探索木があるのか知りたいのですが?私の理解では、バランス二分探索木はAVL木です。それ以外に、「バランス二分探索木」を構築することは不可能だと思います。しかし、そのようなデータ構造がある場合、一連の乱数から「バランス二分探索木」を構築するにはどうすればよいでしょうか。
ありがとう、
python - 二分探索木
これは、BST に関するウィキペディアにあるコードです。
ここに二分木があります:
11 を探していて、そこまでのアルゴリズムに従っているとしたら、10 から始めて、右に 12 に行き、次に左に 9 に行きます。そして、11 を見つけることなく、ツリーの最後に到達します。しかし、11 は私のツリーに存在します。 、それはちょうど反対側にあります。
このアルゴリズムが私のツリーで機能するためのバイナリ ツリーの制限を説明していただけますか?
ありがとう。
java - スレッド「メイン」の例外 java.lang.ClassCastException:
データ構造 (バイナリ検索ツリー) の 1 つをテストするためにドライバーを使用していて、この問題に遭遇しました。-2つ以上のオブジェクトをbstに挿入すると発生します -私がやろうとしているのは、ツリーに4つのオブジェクトを挿入し、次に2つのオブジェクトを削除してから、findメソッドを出力して、私が要求したオブジェクトが見つかりませんでした。例えば:
実行すると、次のエラーが表示されます。
スレッド「メイン」の例外 java.lang.ClassCastException: TreeNode は Driver5.main(Driver5.java:36) の BinarySearchTree2.delete(BinarySearchTree2.java:83) で java.lang.Comparable にキャストできません
次に、私のbstクラスのdeleteメソッドを指します:
エラーは、削除メソッドの次の行を直接指しています。
java - NULL ポインター例外
データ構造 (バイナリ検索ツリー) の 1 つをテストするためにドライバーを使用していて、この問題に遭遇しました。-bstに2つ以上のオブジェクトを挿入すると発生します-私がやろうとしていること:ツリーに4つのオブジェクトを挿入し、次に2つのオブジェクトを削除してから、findメソッドを出力して、私が要求したオブジェクトが見つかりませんでした。例えば:
bst で次のエラーが発生します。
全体の削除は次のとおりです。
algorithm - 親ポインタを使用せずに後継者を見つける
BST内の要素のサクセサは、インオーダートラバーサルによって決定されたソートされた順序での要素のサクセサです。各ノードがその親ノードへのポインターを持っているときに後継者を見つけることは、CLRSのアルゴリズム教科書(MITプレスによるアルゴリズムの紹介)に示されています。
ここでサクセサを見つけるという考え方は、ノードの右側のサブツリーx
が空でない場合、のサクセサはx
右側のサブツリーの最小要素です。x
それ以外の場合、後継者は、左の子がの祖先でもある最下位の祖先ですx
(ノードがそれ自体の祖先であると想定)。
親ノードへのポインタを使用せずに後継者を見つけることはできますか?
ツリーノードにこのポインタがない場合があります。数時間苦労しましたが、正しいコードを書くことができません。