二分探索木は、ソートされた数値リストを短時間で保持できるデータ構造です。各ツリー ノードは 2 つの兄弟のみを持つことができるため、バイナリ ツリーとも呼ばれます。二分探索ツリーは、数値の存在を検索するために使用できます。これは検索ツリーと呼ばれます。実行時間の複雑さは O(log(n)) 時間です。二分探索木と基本二分木を区別する特徴は次のとおりです –
無料ソフトウェア開発コースを始めましょう
Web 開発、プログラミング言語、ソフトウェア テスト、その他
1.左側のサブツリーのノードはすべてルート ノードよりも小さいです。
2.右側のサブツリーのノードはすべてルート ノードより大きくなります。
3.サブツリーの各ノードも同様に BST であり、ノード自体と同じ 2 つの性質を持っています。
1.指定された配列を次のようにします:
指定された配列: [8, 6, 2, 7, 9, 12, 4, 10]
2.最上位の要素 43 から始めましょう。ツリーのルートとして 43 を挿入します。
3.次の要素がルート ノード要素より小さい場合は、左側のサブツリーのルートとして挿入する必要があります。
4.そうでない場合は、右のサブツリーのルートとして挿入する必要があります。
下の画像は、提供された要素を使用して二分探索ツリーを構築するプロセスを示しています。
二分探索ツリー操作:
Java の二分探索木でサポートされている操作を以下のリストに示します –
1. BST での検索 – 二分探索木で、特定の要素の位置を見つけます。
2. BST への挿入 – 新しい要素をバイナリ検索ツリーの適切な場所に追加することで、バイナリ検索ツリーのプロパティが壊れないようにします。
3. BST での削除 – 二分探索ツリー内の特定のノードを削除します。ただし、ノードに含まれる子の数に応じて、さまざまな削除シナリオが考えられます。
二分探索木に対して操作を実行する Java の二分探索木の例 –
// プログラムは Eclipse IDE、JAVA 11 でテストできます
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
|
出力:
上記のプログラムと同様に、別の内部クラス Node とコンストラクターとメソッドを含む binarySearchTree クラスが作成されます。クラスで定義されているメソッドは、特定の操作を実行するための deleteKey()、delete()、minKey()、insertKey()、insert()、inorder()、searchKey()、および search() です。上記の出力に示すように、main 関数では、binarySearchTree クラス オブジェクトが作成され、そのオブジェクトにいくつかの要素が挿入され、次にそのオブジェクトに対してバイナリ Search Tree クラスのメソッドが呼び出されます。
二分探索ツリーは、各ツリー ノードが 2 つの兄弟のみを持つことができるため、バイナリ ツリーとも呼ばれます。二分探索ツリーは、ソートされた数値リストを短時間で保持できるデータ構造です。二分探索木に対して実行できる操作: 走査、挿入、削除、検索。
以上がJavaの二分探索木の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。