問題タブ [binary-search-tree]

Python で二分探索木を表現するにはどうすればよいですか?

コンピュータサイエンスの文脈における「祖先」の定義についてのコンセンサスは何であるのか疑問に思います。

アルゴリズム入門、第2版、p。Tree-Successor(x)259奇妙に思われるアルゴリズムの説明があります。ノードxの後継を見つける際に、

[...]ノードxの右側のサブツリーが空で、xに後続のyがある場合、yはxの最も低い祖先であり、その左側の子はxの祖先でもあります。

2キーと子1を持つルートを持つ二分探索木では3、の後続1はその親2です。この場合、xはxの後継子yの左の子です。したがって、本の定義によれば、私が何かを見逃していない限り、xはそれ自体の祖先でなければなりません。

これについての正誤表には何も見つかりませんでした。

バイナリ検索ツリーを実装するために上記のコードを記述しましたが、insertメソッドが期待どおりに機能せず、ルート要素も追加できません。原因がわからない。

本Data Structures and Algorithms: Annotated Reference with Examples で使用されているバイナリ ツリー削除ノード アルゴリズムを読んでいます。

34 ページ、ケース 4 (右と左の両方のサブ ツリーを持つノードを削除)、本に記載されているアルゴリズムに従って動作しないように見えます。

次の行は、サブツリーから最大値をどのように削除しますかFindParent(largestValue).Right <- 0

特定の二分木について、二分探索木でもある最大の部分木を見つけますか?

例：

入力：

出力：

今日、私の教授はクラスで、これまで聞いたことのないバランス二分探索木があると言いました。回転のないバランス二分探索木があるのか​​知りたいのですが？私の理解では、バランス二分探索木はAVL木です。それ以外に、「バランス二分探索木」を構築することは不可能だと思います。しかし、そのようなデータ構造がある場合、一連の乱数から「バランス二分探索木」を構築するにはどうすればよいでしょうか。

ありがとう、

これは、BST に関するウィキペディアにあるコードです。

ここに二分木があります：

11 を探していて、そこまでのアルゴリズムに従っているとしたら、10 から始めて、右に 12 に行き、次に左に 9 に行きます。そして、11 を見つけることなく、ツリーの最後に到達します。しかし、11 は私のツリーに存在します。 、それはちょうど反対側にあります。

このアルゴリズムが私のツリーで機能するためのバイナリ ツリーの制限を説明していただけますか?

ありがとう。

データ構造 (バイナリ検索ツリー) の 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メソッドを指します：

エラーは、削除メソッドの次の行を直接指しています。

データ構造 (バイナリ検索ツリー) の 1 つをテストするためにドライバーを使用していて、この問題に遭遇しました。-bstに2つ以上のオブジェクトを挿入すると発生します-私がやろうとしていること:ツリーに4つのオブジェクトを挿入し、次に2つのオブジェクトを削除してから、findメソッドを出力して、私が要求したオブジェクトが見つかりませんでした。例えば：

bst で次のエラーが発生します。

全体の削除は次のとおりです。

BST内の要素のサクセサは、インオーダートラバーサルによって決定されたソートされた順序での要素のサクセサです。各ノードがその親ノードへのポインターを持っているときに後継者を見つけることは、CLRSのアルゴリズム教科書（MITプレスによるアルゴリズムの紹介）に示されています。

ここでサクセサを見つけるという考え方は、ノードの右側のサブツリーxが空でない場合、のサクセサはx右側のサブツリーの最小要素です。xそれ以外の場合、後継者は、左の子がの祖先でもある最下位の祖先ですx（ノードがそれ自体の祖先であると想定）。

親ノードへのポインタを使用せずに後継者を見つけることはできますか？

ツリーノードにこのポインタがない場合があります。数時間苦労しましたが、正しいコードを書くことができません。