フロントエンド: JavaScript でのバイナリ ツリー アルゴリズムの実装

[[359197]]

次に、js データ構造のツリーを調べてみましょう。ここでのツリーは、幹と枝を持つ現実のツリーに似ています。プログラムでは、ツリーは、すばやく見つける必要のあるデータを格納するのに非常に便利なデータ構造です。これは、階層データの抽象モデルです。ツリー構造は、親子関係を持つ一連のノードで構成されます。各ノードには親ノードと 0 個以上の子ノードがあります。以下はツリー構造です。

• ツリーに関連する概念: 1. サブツリー: 上の図に示すように、ノードとその子孫で構成されます。 2. 深さ: ノードの深さは、その祖先ノードの数によって決まります。たとえば、ノード 5 には 2 つの祖先ノードがあり、その深さは 2 です。3. 高さ: ツリーの高さは、すべてのノードの深さの最大値によって決まります。

二分木と二分探索木の紹介

バイナリ ツリーのノードには、最大 2 つの子ノード (左側に 1 つ、右側に 1 つ) を含めることができます。この定義の利点は、ノードの挿入、検索、削除のためのより効率的なアルゴリズムを記述できることです。二分探索木は二分木の一種ですが、左の子ノードには親ノードより小さい値しか格納できず、右の子ノードには親ノードより大きい値を格納することができます。次に、このアイデアに従って二分探索木を実装します。

1. BinarySearchTreeクラスを作成する

ここではコンストラクターを使用してクラスを作成します。

関数BinarySearchTree(){
    // ノードを作成するためのクラス
    Node =関数(キー) {
        this.key =キー;
        this.left = null ;
        this.right = null ;
    }
    // ルートノード
    ルートをnullにします。
 }

ノード間の関係を表すために、リンク リストに似たポインター メソッドを使用します。リンク リストがわからない場合は、次の記事「単一方向および双方向のリンク リストを実装する方法」をお読みください。

2. キーを挿入する

// キーを挿入する
this.insert =関数(キー) {
    newNode = new Node(キー) とします。
    ルート === null ? (ルート = newNode) : (insertNode(ルート、newNode))
 }

ツリーに新しいノードを挿入する処理は、次の 3 つの部分から構成されます。1. 新しいノードの Node クラス インスタンスを作成する --> 2. 挿入操作がルート ノードであるかどうかを判断し、そうである場合はルート ノードを指定します --> 3. ノードをルート以外のノードの場所に追加します。

insertNode の具体的な実装は次のとおりです。

関数insertNode(ノード, newNode){
    （新しいノードのキーがノードのキーより小さい場合）
        node.left === null ? (node.left = newNode) : (insertNode(node.left , newNode))
    }それ以外{
        node.right === null ? (node.right = newNode) : (insertNode(node.right , newNode))
    }
 }

ここでは再帰を使います。この後実装する検索や削除などでも再帰を多用するので、わからない場合はまず自分で学んでみましょう。キーを挿入するためのバイナリ ツリー インスタンスを作成します。

ツリーを新しい BinarySearchTree() にします。
ツリーを挿入 (20);
ツリーを挿入 (21);
ツリーを挿入( 520 );
ツリーを挿入 ( 521 );

挿入された構造は二分探索木のルールに従って挿入され、その構造は上記の最初のツリー図に似ています。

ツリートラバーサル

ツリーをトラバースする方法には、インオーダー、プレオーダー、ポストオーダーの 3 つがあります。

• 順序通りのトラバーサル: 最小から最大の順にすべてのノードを訪問する
• 先行順序トラバーサル: 各ノードをその子孫ノードの前の順序で訪問する
• 後順トラバーサル: まずノードの子孫ノードを訪問し、次にノード自体を訪問する

上記の紹介に基づいて、次の実装コードを作成できます。

1 順序ソート

this.inOrderTraverse =関数(cb){
    inOrderTraverseNode(ルート、cb);
 } 
 
 // ヘルパー関数
関数inOrderTraverseNode(node, cb){
    if(ノード ​​!== null ){
        inOrderTraverseNode( node.left , cb);
        cb(ノード.キー);
        inOrderTraverseNode( node.right , cb);
    }
 }

順序付きトラバーサルを使用すると、ツリーを小さいものから大きいものへと並べ替えることができます。

2 予約注文の並べ替え

// 事前順序ソート--- 子孫ノードの優先順位に従って各ノードを訪問します 
   this.preOrderTraverse =関数(cb) {
     preOrderTraverseNode(ルート、cb);
   } 
 
   // 事前順序ソートヘルパーメソッド
関数preOrderTraverseNode(ノード、cb) {
     if(ノード ​​!== null ) {
       cb(ノード.キー);
       preOrderTraverseNode( node.left , cb);
       preOrderTraverseNode( node.right , cb);
     }
   }

事前順序ソートを使用すると、構造化された出力の機能を実現できます。

3 事後順序ソート

// 後続のトラバーサル--- まず子孫ノードを訪問し、次にノード自体を訪問します 
   this.postOrderTraverse =関数(cb) {
     postOrderTraverseNode(ルート、cb);
   } 
 
   // 後続のトラバーサル補助メソッド
関数postOrderTraverseNode(ノード、cb) {
     if(ノード ​​!== null ){
       postOrderTraverseNode( node.left , cb);
       postOrderTraverseNode( node.right , cb);
       cb(ノード.キー);
     }
   }

後順序トラバーサルを使用すると、階層関係内のすべての要素のサイズを計算できます。

ツリー内の値の検索

ツリーで一般的に実行される検索には、最大値、最小値、特定の値の 3 つの種類があります。

1 最小

最小値は、左のツリーの最下層のノードとして定義されます。具体的な実装コードは次のとおりです。

 // 最小値
   this.min =関数(){
 minNode(ルート)を返す
   } 
 
関数minNode(ノード) {
     if(ノード) {
       while(node ​​&& node.left !== null ){
         ノード = node.left ;
       }
 node.key​を返す 
     }
戻る ヌル 
   }

同様に、最大値は次のように達成されます。

 // 最大値
   this.max =関数（）{
 maxNode(ルート)を返す
   } 
 
関数maxNode(ノード) {
     if(ノード){
       while(node ​​&& node.right !== null ){
         ノード = node.right ;
       }
 node.key​を返す 
     }
戻る ヌル 
   }

2. 特定の値を検索する

// ツリー内の値を検索する
this.search =関数(キー) {
 searchNode(ルート、キー)を返します
} 
 
 // 検索ヘルパーメソッド
関数searchNode(ノード、キー){
    if(ノード === null ) {
戻る 間違い 
    }
    if(キー< ノード.キー) {
 searchNode ( node.left 、 key )を返します
    }そうでない場合(キー> ノード.キー) {
 searchNode ( node.right 、 key )を返します
    }それ以外{
戻る 真実 
    }
 }

3 ノードを削除する

this.remove =関数(キー) {
    ルート = removeNode(ルート、キー);
 } 
 
 // 最小のノードを見つける
関数findMinNode(ノード) {
    if(ノード) {
    while(node ​​&& node.left !== null ){
        ノード = node.left ;
    }
戻りノード
    }
戻る ヌル 
 } 
 
 // ノードヘルパーメソッドを削除する
関数removeNode(ノード、キー) {
    if(ノード === null ) {
戻る ヌル 
    } 
 
    if(キー< ノード.キー) {
    node.left = removeNode(node.left ,キー) ;
戻りノード
    }そうでない場合(キー> ノード.キー) {
    node.right = removeNode(node.right 、キー) ;
戻りノード
    }それ以外{
    // ページノード
    if( node.left === null && node.right === null ) {
        ノード = null ;
戻りノード
    } 
 
    // 子ノードが 1 つだけあるノード
    if(ノード.left === null ) {
        ノード = node.right ;
戻りノード
    }そうでない場合(node.right === null ) {
        ノード = node.left ;
戻りノード
    } 
 
    // 2つの子ノードを持つノード
    aux = findMinNode( node.right );とします。
    ノードキー= aux.key ;
    ノードを削除します。
戻りノード
    }
 }

ノードを削除するときに考慮する必要がある状況は多数あります。ここでは、min に似た実装を使用して、最小のノードを見つける関数を記述します。削除するノードに 2 つの子ノードがある場合、削除する現在のノードを子ノードの中で最大のノードの値に置き換えてから、この子ノードを削除する必要があります。

この時点で、バイナリ検索ツリーは実装されましたが、まだ問題があります。ツリーの片側が非常に深い場合、特定のパフォーマンス問題が発生します。この問題を解決するには、任意のノードの左サブツリーと右サブツリーの高さの差が最大 1 である自己バランスバイナリツリーである AVL ツリーを使用できます。