binary search tree java implementation code examples
このチュートリアルでは、Javaのバイナリ検索ツリーについて説明します。 BSTの作成、要素の挿入、削除、検索、JavaでのBSTのトラバースと実装について学習します。
二分探索木（以下、BSTと呼びます）は、二分木の一種です。また、ノードベースのバイナリツリーとして定義することもできます。 BSTは、「順序付き二分木」とも呼ばれます。 BSTでは、左側のサブツリーのすべてのノードの値がルートノードの値よりも小さくなっています。
同様に、BSTの右側のサブツリーのすべてのノードには、ルートノードの値よりも大きい値があります。このノードの順序は、それぞれのサブツリーにも当てはまる必要があります。
=> 独占的なJavaトレーニングチュートリアルシリーズについては、こちらをご覧ください。
学習内容：
Javaの二分探索木
BSTは重複ノードを許可しません。
次の図は、BST表現を示しています。
上に示したのはサンプルBSTです。 20がこのツリーのルートノードであることがわかります。左側のサブツリーには、20未満のすべてのノード値があります。右側のサブツリーには、20より大きいすべてのノードがあります。上記のツリーは、BSTプロパティを満たしていると言えます。
BSTデータ構造は、アイテムの挿入/削除および検索に関して、配列およびリンクリストと比較して非常に効率的であると見なされます。
BSTは、要素の検索にO（log n）時間を要します。要素が順序付けられると、要素の検索中のすべてのステップでサブツリーの半分が破棄されます。これは、検索する要素の大まかな位置を簡単に特定できるために可能になります。
同様に、挿入および削除操作はBSTでより効率的です。新しい要素を挿入する場合、要素を挿入するサブツリー（左または右）は大まかにわかります。
二分探索木（BST）の作成
要素の配列が与えられた場合、BSTを構築する必要があります。
以下に示すようにこれを実行しましょう。
与えられた配列： 45、10、7、90、12、50、13、39、57
まず、最上位の要素、つまり45をルートノードとして考えてみましょう。ここから、すでに説明したプロパティを考慮してBSTを作成します。
ツリーを作成するために、配列内の各要素をルートと比較します。次に、要素をツリーの適切な位置に配置します。
BSTの作成プロセス全体を以下に示します。
二分探索木操作
BSTはさまざまな操作をサポートしています。次の表は、JavaのBSTでサポートされているメソッドを示しています。これらの各方法について個別に説明します。
| 方法/操作 | 説明 |
|---|---|
| インサート | BSTプロパティに違反しないようにして、要素をBSTに追加します。 |
| 削除 | 特定のノードをBSTから削除します。ノードは、ルートノード、非リーフノード、またはリーフノードにすることができます。 |
| 探す | BSTで指定された要素の場所を検索します。この操作は、ツリーに指定されたキーが含まれているかどうかを確認します。 |
BSTに要素を挿入する
要素は常にリーフノードとしてBSTに挿入されます。
以下に、要素を挿入する手順を示します。
- ルートから開始します。
- 挿入する要素をルートノードと比較します。ルートよりも小さい場合は、左側のサブツリーをトラバースするか、右側のサブツリーをトラバースします。
- 目的のサブツリーの終わりまでサブツリーをトラバースします。ノードをリーフノードとして適切なサブツリーに挿入します。
BSTの挿入操作の図を見てみましょう。
次のBSTを検討し、要素2をツリーに挿入しましょう。
BSTの挿入操作は上に示されています。図（1）に、要素2をBSTに挿入するためにトラバースするパスを示します。また、各ノードでチェックされる条件も示しました。再帰的な比較の結果、図（2）に示すように、要素2が1の右の子として挿入されます。
BSTでの検索操作
要素がBSTに存在するかどうかを検索するには、ルートから開始し、検索する要素がルートよりも小さいか大きいかに応じて、左または右のサブツリーをトラバースします。
以下に、私たちが従わなければならないステップを示します。
- 検索する要素をルートノードと比較します。
- キー（検索する要素）= rootの場合、rootノードを返します。
- それ以外の場合はキー
- それ以外の場合は、右のサブツリーをトラバースします。
- キーが見つかるか、ツリーの終わりに達するまで、サブツリー要素を繰り返し比較します。
例を挙げて検索操作を説明しましょう。キー= 12を検索する必要があると考えてください。
次の図では、この要素を検索するためにたどるパスをトレースします。
上の図に示すように、最初にキーとルートを比較します。キーが大きいので、右側のサブツリーをトラバースします。右側のサブツリーで、キーを右側のサブツリーの最初のノードと再度比較します。
キーが15未満であることがわかります。そこで、ノード15の左側のサブツリーに移動します。15のすぐ左側のノードは、キーと一致する12です。この時点で、検索を停止して結果を返します。
BSTから要素を削除する
BSTからノードを削除する場合、以下で説明するように3つの可能性があります。
ノードはリーフノードです
削除するノードがリーフノードの場合、子ノードがないため、このノードを直接削除できます。これを下の画像に示します。
上に示したように、ノード１２はリーフノードであり、すぐに削除することができる。
ノードには子が1つしかありません
子が1つあるノードを削除する必要がある場合は、ノード内の子の値をコピーしてから、子を削除します。
上の図では、子50が1つあるノード90を削除します。したがって、値50を90と交換してから、子ノードであるノード90を削除します。
ノードには2つの子があります
削除するノードに2つの子がある場合、ノードを順序のない（left-root-right）後続ノードに置き換えるか、ノードの右側のサブツリーが空でない場合は、右側のサブツリーの最小ノードと単純に言います。ノードをこの最小ノードに置き換え、ノードを削除します。
上の図では、BSTのルートノードであるノード45を削除します。このノードの右側のサブツリーは空ではないことがわかります。次に、右側のサブツリーをトラバースして、ノード50がここで最小のノードであることを確認します。したがって、45の代わりにこの値を置き換えてから、45を削除します。
ツリーをチェックすると、BSTのプロパティを満たしていることがわかります。したがって、ノードの置き換えは正しかった。
Javaでの二分探索木（BST）の実装
次のJavaのプログラムは、例として図で使用されているのと同じツリーを使用して、上記のすべてのBST操作のデモンストレーションを提供します。
class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String[] args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 / 10 90 / / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }出力：
Javaでの二分探索木（BST）トラバーサル
ツリーは階層構造であるため、配列などの他のデータ構造のように直線的にトラバースすることはできません。すべてのサブツリーとノードが少なくとも1回アクセスされるように、任意のタイプのツリーを特別な方法でトラバースする必要があります。
ルートノード、左サブツリー、および右サブツリーがツリー内でトラバースされる順序に応じて、以下に示すように特定のトラバースがあります。
- インオーダートラバーサル
- プレオーダートラバーサル
- 注文後のトラバーサル
上記のすべてのトラバーサルは、深さ優先手法を使用します。つまり、ツリーは深さ方向にトラバースされます。
木はまた、横断のために幅優先技術を使用します。この手法を使用したアプローチは、 「レベルオーダー」 トラバーサル。
このセクションでは、次のBSTを例として使用して、各トラバーサルを示します。
上の図に示されているBSTを使用すると、上のツリーのレベル順トラバーサルは次のようになります。
レベルオーダートラバーサル：10 6 12 4 8
インオーダートラバーサル
インオーダートラバーサルアプローチは、BSTを順番にトラバースしました。 左のサブツリー=> RootNode =>右のサブツリー 。インオーダートラバーサルは、BSTのノードの減少するシーケンスを提供します。
InOrderトラバーサルのアルゴリズムInOrder（bstTree）を以下に示します。
- InOrder（left_subtree）を使用して左側のサブツリーをトラバースします
- ルートノードにアクセスします。
- InOrder（right_subtree）を使用して右側のサブツリーをトラバースします
上記のツリーの順序どおりの走査は次のとおりです。
4 6 8 10 12
見られるように、順序のないトラバーサルの結果としてのノードのシーケンスは降順です。
プレオーダートラバーサル
プレオーダートラバーサルでは、最初にルートにアクセスし、次に左側のサブツリーと右側のサブツリーにアクセスします。プレオーダートラバーサルは、ツリーのコピーを作成します。また、式ツリーでプレフィックス式を取得するために使用することもできます。
PreOrder（bst_tree）トラバーサルのアルゴリズムを以下に示します。
- ルートノードにアクセスします
- PreOrder（left_subtree）を使用して左側のサブツリーをトラバースします。
- PreOrder（right_subtree）を使用して右側のサブツリーをトラバースします。
上記のBSTのプレオーダートラバーサルは次のとおりです。
10 6 4 8 12
注文後のトラバーサル
postOrderトラバーサルは、次の順序でBSTをトラバースします。 左のサブツリー->右のサブツリー->ルートノード 。 PostOrderトラバーサルは、ツリーを削除するか、式ツリーの場合は後置式を取得するために使用されます。
postOrder（bst_tree）トラバーサルのアルゴリズムは次のとおりです。
- postOrder（left_subtree）を使用して左側のサブツリーをトラバースします。
- postOrder（right_subtree）を使用して右側のサブツリーをトラバースします。
- ルートノードにアクセスします
上記の例のBSTのpostOrderトラバーサルは次のとおりです。
4 8 6 12 10
次に、Java実装で深さ優先手法を使用してこれらのトラバーサルを実装します。
//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String[] args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } } 出力：
よくある質問
Q＃1）なぜ二分探索木が必要なのですか？
回答 ：バイナリ検索手法を使用して配列のような線形データ構造内の要素を検索する方法。ツリーは階層構造であるため、ツリー内の要素を見つけるために使用できる構造が必要です。
ここで、画像内の要素を効率的に検索するのに役立つバイナリ検索ツリーが登場します。
Q＃2）二分探索木の特性は何ですか？
どのウェブサイトでアニメを見ることができますか
回答 ： 二分木カテゴリに属する二分探索木には、次のプロパティがあります。
- 二分探索木に保存されているデータは一意です。重複する値は許可されません。
- 左側のサブツリーのノードは、ルートノードよりも小さくなっています。
- 右側のサブツリーのノードは、ルートノードよりも大きくなっています。
Q＃3）二分探索木のアプリケーションは何ですか？
回答 ：二分探索木を使用して、数学のいくつかの連続関数を解くことができます。階層構造のデータの検索は、バイナリ検索ツリーを使用するとより効率的になります。すべてのステップで、検索をサブツリーの半分に減らします。
Q＃4）バイナリツリーとバイナリ検索ツリーの違いは何ですか？
回答： 二分木は、親と呼ばれる各ノードが最大で2つの子を持つことができる階層ツリー構造です。二分探索木は、二分木のすべての特性を満たし、独自の特性も備えています。
二分探索木では、左側のサブツリーにはルートノード以下のノードが含まれ、右側のサブツリーにはルートノードより大きいノードが含まれます。
Q＃5）二分探索木はユニークですか？
回答 ：二分探索木は二分木カテゴリに属します。重複する値を許可しないという意味でユニークであり、そのすべての要素は特定の順序に従って順序付けられます。
結論
二分探索木は二分木カテゴリの一部であり、主に階層データの検索に使用されます。また、いくつかの数学的問題を解くためにも使用されます。
このチュートリアルでは、二分探索木の実装を見てきました。また、BSTで実行されるさまざまな操作をその図とともに見て、BSTのトラバーサルについても調査しました。
=> ここで簡単なJavaトレーニングシリーズに注意してください。