Java で二分探索木の高さを決定する

1. 二分探索木
2. 二分探索木の応用
3. 二分探索木の高さを決定する

この詳細な記事では、Java プログラムでツリーの高さを決定する再帰的検索プログラムを実装する前に、二分探索ツリーの基本を学びます。 このチュートリアルを理解するには、ツリーのデータ構造の概念に関する基本的な知識があることをお勧めします。

二分探索木

シンプルにしましょう。 長い理論的概念であなたを退屈させることはありません。 ただし、理解しておく必要がある主要な概念は次のとおりです。

1. 階層データ構造のルート ノードへの単一参照。
2. 各ノードには、最大 2つの子ノード (左右の子) が存在します。
3. 二分探索機能は、ノードを編成します。
   • 各ノードはキー データ フィールドに従ってソートされます。
   • ツリー内の各ノードのキーは、左側の子のキーより大きく、右側の子のキーより小さい必要があります。
   • 図: 二分探索木:

二分探索木の応用

シンプルにしましょう。 長い理論的概念であなたを退屈させることはありません。

ただし、理解しておく必要がある主要な概念は次のとおりです。

1. Java を含むほとんどのプログラミング言語の map および set メソッドのように、データの流れと構造が常に出入りする BST を使用することもできます。

2. 3 次元ビデオ ゲームで BST を使用して、オブジェクトの位置とレンダリング プロセスを決定することもできます。 BST を使用したスペース パーティションの詳細については、バイナリ スペース パーティション を参照してください。

3. 主にネットワーキングについて話す場合、ほとんどすべての高帯域幅ルーターでこれらのツリーを使用して、ルーター テーブルを格納できます。 バイナリトライ。

4. トレントと画像署名の独自の生成に興味がある場合。 ハッシュの必要性を確認したいが、ファイル全体が利用できないとします。

   ここでも BST を利用できます。 続きを読む: ハッシュツリー

簡単に言えば、バイナリ サーチ ツリーは、必要なデータを整理するのに役立つため、さまざまなアプリケーションで使用できます。 二分探索木を使用して、マルチレベルのインデックス作成を行うことができます。

さらに、さまざまな検索アルゴリズムを実装するためにそれらを使用することもできます。 BST は、並べ替えられたデータ ストリームを保持するのに役立つためです。

二分探索木の高さを決定する

次の簡単な手順に従えば、二分探索木の高さを決定することは難しい作業ではありません。

1. ルートからリーフ ノードまでの最長パスの長さによって、バイナリ ツリーの高さが決まります。 二分木の深さとしても知られています。

   根の高さは木の高さと同じです。

2. ノードの深さは、そのルートへのパスの長さです。

3. 木の高さを計算するには、根と最も遠い葉の間のエッジの数を数えなければなりません。

上のグラフでわかるように、ルートと最も遠い葉の間のエッジの数は 3 です。したがって、ツリーの高さも 3 です。

二分探索ツリーで特定のキーを検索する

Binary Search Tree で特定のキーを再帰的または反復的に検索できます。 これらの方法は両方とも、さまざまなデータ構造操作で一般的な選択肢です。

再帰的検索方法について言えば、検索プロセスはルート ノードの検査から始まります。 この点で、ツリーが nil であると仮定すると、求められたキーはツリーに存在しません。

検索結果が成功した場合、キーがルートと一致する場合はノードが返されます。 ただし、キーがルートよりも小さい場合、プログラム検索は左側のサブツリーに移動します。

二分探索木の高さを見つけるための再帰的な手順

ツリーが空の場合、その高さは 0 であることに注意してください。逆に、最上位ノードから開始する必要があります。

左サブツリーの最大深さを再帰的に決定したいとします。 これら 2つの最大の深さは、バイナリ ツリー (左と右のサブツリー) の高さです。

次の疑似コードを確認してください。

BinarySearchTree(a, k)
   if a = NIL or k = a.key then
     return a
   if k < a.key then
     return Tree-Search(a.L, k)
   else
     return Tree-Search(a.R, k)
   end if

BST 内の高さを検索するために、プログラムを再帰的に実装してみましょう。

例：

package heightofbinarysearchBSTree.delftstack;
// Java program to find the height of BSTree
// A binary BSTree BSTreeNode
public class DetHeight {
  int BSTreedata;
  DetHeight BSTreeNodeLeft, BSTreeNoderight;
  DetHeight(int i) {
    BSTreedata = i;
    BSTreeNodeLeft = BSTreeNoderight = null;
  }
}
class BST {
  DetHeight BSTreeroot;
  /* Compute the "MaximumHeight" of a BSTree -- the number of
  BSTreeNodes along the longest path from the BSTreeroot BSTreeNode
  down to the farthest leaf BSTreeNode.*/
  int MaximumHeight(DetHeight BSTreeNode) {
    if (BSTreeNode == null)
      return -1;
    else {
      /* compute the depth of each subBSTree */
      int LeftHeight = MaximumHeight(BSTreeNode.BSTreeNodeLeft);
      int Rightheight = MaximumHeight(BSTreeNode.BSTreeNoderight);

      /* use the larger one */
      if (LeftHeight > Rightheight)
        return (LeftHeight + 1);
      else
        return (Rightheight + 1);
    }
  }
  /* Driver program to test above functions */
  public static void main(String[] args) {
    BST BSTree = new BST();
    BSTree.BSTreeroot = new DetHeight(12);
    BSTree.BSTreeroot.BSTreeNodeLeft = new DetHeight(25);
    BSTree.BSTreeroot.BSTreeNoderight = new DetHeight(35);
    BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNodeLeft = new DetHeight(47);
    BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(26);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft = new DetHeight(29);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNoderight = new DetHeight(53);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(31);
    System.out.println("Height of BSTree is : " + BSTree.MaximumHeight(BSTree.BSTreeroot));
  }
}

出力：

The height of this tree : 3

検索プログラムの複雑さ

この特定のケースでは、高さを維持しながらバイナリ ツリーのすべてのノードを再帰的にトラバースしているため、線形です。 したがって、時間計算量は O(N) です。ここで、N はツリー内のノードの数です。