1篇の文章は二叉木と二叉木をマスターして木を探します

ツリーはコンピュータ科学でよく使われるデータ構造です.ツリーは、データを階層的に格納する非線形のデータ構造です.
ツリーは、ファイルシステム内のファイルなどの階層関係を持つデータを格納するために使用されます.
ツリーは、シーケンステーブルを格納するためにも使用できます.

ツリーの定義

ツリーは、エッジで接続されたノードのセットで構成されます.会社の組織構造図はツリーの例です.
組織構造図は、木の一番上のノードがルートノードになることです.1つのノードの下に複数のノードが接続されている場合、そのノードは親ノードと呼ばれ、その下のノードは子ノードと呼ばれます.1つのノードは、0個、1個または複数のサブノードを有することができる.サブノードがないノードをリーフノードと呼びます.次の図は、いくつかのツリーの用語を示しています.
特定のエッジのセットに沿って、1つのノードから直接接続されていない別のノードに移動できます.1つのノードから別のノードへのエッジのセットをパスと呼びます.ツリー内のすべてのノードに特定の順序でアクセスすることをツリーのループと呼びます.ツリーは、ルートノードが0番目のレイヤで、サブノードが1番目のレイヤで、サブノードのサブノードが2番目のレイヤである階層に分けられます.ツリー内の任意のレイヤのノードは、ルートノードのサブノード、サブノードのサブノードなどを含むサブツリーのルートと見なすことができます.ツリーのレイヤ数がツリーの深さであることを定義します.ノードの高さ:ノードからリーフノードへの最長パス(エッジツリー).ノードの深さ:ルートノードからこのノードまでのエッジの数.ノードのレイヤ数:ノードの深さ+1.ノードの高さ:ルートノードの高さ.次に例を挙げると、各ノードにはキーと呼ばれる場合がある関連する値があります.二叉木は特殊な木です.サブノードは2つを超えません.二叉木はいくつかの特殊な計算特性を有し、それ以上のいくつかの操作が異常に効率的である.

ツリーとツリーの検索

1つの親ノードの2つのサブノードは、それぞれ左ノードと右ノードと呼ばれます.左ノードには特定の値のセットが含まれ、右ノードには特定の値のセットが含まれます.
次の図は、ツリーを検索するなどの特殊なツリーを考慮すると、サブノードを決定することが重要であるツリーを示しています.ツリーは特殊なツリーで、比較的小さな値は左ノードに保存され、大きな値は右ノードに保存されます.この特性により、単語や文字列などの数値や非数値のデータに対しても、検索の効率が向上します.下の図の木を見てみましょう.番号2の二叉木の中で、葉ノードはすべて最下層にあり、葉ノード以外の各ノードには左右の2つのサブノードがあり、この二叉木を満二叉木と言います.番号3の二叉木では、葉ノードが一番下の二層にあり、最後の層の葉ノードが左に並び、最後の層を除いて他の層のノード数が最大に達し、この二叉木を完全二叉木と呼ぶ.

二叉ルックアップツリーの実装(BST)

ノードオブジェクトを定義します.

function node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;

    function show() {
        return this.data;
    }
}

二叉ルックアップツリーを表すBSTクラスを作成できるようになりました.クラスには、ツリーのルートノードを検索する2つのフォークを表すノードを表すノードオブジェクトだけが含まれます.クラスのコンストラクション関数は、ルートノードをnullに初期化し、空のノードを作成します.
BSTには、まず、ツリーに新しいノードを挿入するためのinsert()メソッドが必要です.まず、ノードオブジェクトを作成し、そのオブジェクトにデータを転送して保存します.次に、BSTにルートノードがあるかどうかをチェックし、なければ、これは新しい木で、そのノードがルートノードであり、この方法はこれで終わります.そうでなければ、次のステップに進みます.
挿入されるノードがルートノードでない場合、BSTを巡回して挿入の適切な位置を見つける準備をします.このプロシージャはチェーンテーブルを巡回するのと似ています.現在のノードを1つのノードで保存し、BSTを1つずつ巡回します.
BSTに入ると、次にノードをどこに置くかを決定する必要があります.正しい挿入点が見つかった場合、ループが飛び出します.
正しい挿入点を検索するアルゴリズムは次のとおりです.

ルートノードを現在のノードとする.

挿入されるノードが現在のノードより小さい場合、新しい現在のノードを元のノードの左ノードとする.逆に、第4ステップを実行します.

現在のノードの左ノードがnullである場合、新しいノードをこの位置に挿入し、ループを終了する.逆に、次のループを実行し続けます.

新しい現在のノードを元のノードの右ノードとする.

現在のノードの右ノードがnullである場合、新しいノードをその位置に挿入し、ループを終了する.逆に、次のループを実行し続けます.

function BST() {
    this.root = null;
    this.insert = insert;
  
    function insert(data) {
        var n = new Node(data, null, null);
        if(this.root == null) {
            this.root = n;
        }else {
            var currentNode = this.root;
            var parent;
            while(true) {
                parent = currentNode;
                if(data < currentNode.data) {
                    currentNode = currentNode.left;
                    if(currentNode == null) {
                        parent.left = n;
                        break;
                    }
                }else {
                    currentNode = currentNode.right;
                    if(currentNode.data == null) {
                        parent.right = n;
                        break;
                    }
                }
            }
        }
    }
  
}

もう一つの書き方は、実は考え方は同じですが、上のほうは少し簡潔です.(コード構想は王争先生の『データ構造とアルゴリズムの美』)

function insert(data) {
        var node = new Node(data, null, null);
        if(this.root == null) {
            this.root = node;
        }else {
            p = this.root;
            while(p !== null) {
                if(data < p.data) {
                    if(p.left == null) {
                        p.left = node;
                        return;
                    }
                    p = p.left;
                }else {
                    if(p.right == null) {
                        p.right = node;
                        return;
                    }
                    p = p.right;
                }
            }
        }
    }

ツリーを検索するには

二叉木を巡る方法は3つあります.中序、先序、後序です.
中間シーケンスは、ノード上のキー値に従ってBST上のすべてのノードに昇順にアクセスする.まず、ルートノードにアクセスし、左サブツリーと右サブツリーにも同じ方法でアクセスします.後順は、まずリーフノードにアクセスし、左サブツリーから右サブツリー、さらにルートノードに移動します.
シーケンスループとは、ツリー内の任意のノードに対して、このノードを先に印刷し、左サブツリーを印刷し、最後に右サブツリーを印刷することです.中順遍歴とは、ツリー内の任意のノードに対して、左サブツリーを印刷してから、それ自体を印刷し、最後に右サブツリーを印刷することです.後順ループとは、ツリー内の任意のノードに対して、左サブツリーを印刷し、右サブツリーを印刷し、最後に自分自身を印刷することです.
中間パスのコードは次のとおりです.

function inOrder(node) {
        if(!(node == null)) {
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    }

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)
bst.inOrder(bst.root); // 16 17 19 34 35 36

次の図は、中間パスを示しています.
先に巡回するコードは次のとおりです.

function perOrder(node) {
        if(!(node == null)) {
            console.log(node.show());
            this.perOrder(node.left);
            this.perOrder(node.right);
        }
}

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)
console.log('    ');
bst.perOrder(bst.root); // 17 16 19 34 35 36

次の図は、先行するパスを示しています.
後に続くコード:

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)

console.log('    ');
bst.postOrder(bst.root); // 16 36 35 34 19 17

次の図は、後続のパスを示しています.

ツリーで検索

BSTには、通常、次の3つのタイプの検索があります.

所与の値を検索

最大値

を検索

最小値

を検索

最小値と最大値の検索

小さい値は常に左ノードにあるので、BSTで最小値を検索するには、左サブツリーを巡って、最後のノードを見つけることを知るだけです.

function getMin() {
        let currentNode = this.root;
        while(currentNode.left != null) {
            currentNode = currentNode.left;
        }
        return currentNode.data;
    }

BST上で最大値を検索するには,右サブツリーを巡回し,最後のノードを見つけることを知るだけでよい.

function getMax() {
        let currentNode = this.root;
        while(currentNode.right != null) {
            currentNode = currentNode.right;
        }
        return currentNode.data;
    }

指定した値の検索

BSTで指定された値を検索するには、その値と現在のノード値のサイズを比較する必要があります.比較することにより、指定された値が現在のノードにない場合、左にループするか右にループするかを決定できます.

function find(data) {
        var currentNode = this.root;
        while(currentNode != null) {
            if(currentNode.data == data) {
                return currentNode;
            }else if(currentNode.data < data) {
                currentNode = currentNode.right;
            }else {
                currentNode = currentNode.left;
            }
        }
        return null;
    }

指定された値が見つかった場合、メソッドは値を保存するメソッドを返します.見つからない場合はnullを返します.

ツリーからノードを削除

BSTからノードを削除する操作は最も複雑であり,その複雑さはどのノードを削除するかに依存する.サブノードのないノードを削除すると、非常に簡単です.ノードにサブノードが1つしかないと、少し複雑になります.ノードにサブノードが2つある場合は、最も複雑です.
3つの状況に分けて処理します.

削除するノードにサブノードがない場合は、削除するノードへのポインタをnullに設定するだけです.例えば、図中のノード55を削除する.

削除するノードが1つのサブノード(左サブノードまたは右サブノード)しかない場合は、親ノードを更新し、削除するノードを指すポインタを、削除するノードを指すサブノードに向けるだけでよい.例えば、図中のノード13を削除する.

削除するノードに2つのサブノードがある場合は、このノードの右サブツリーの最小ノードを見つけて、削除するノードに置き換えてから、この最小ノードを削除する必要があります.最小ノードには左サブノードがないに違いありません.この2つのルールを使用して、図のノード18の削除などの削除操作を行うことができます.

function deleteNode(data) {
        var p = this.root; // p       ，       
        var pp = null; // pp  P    
        while(p != null && p.data != data) {
            pp = p;
            if(data > p.data) {
                p = p.right;
            }else {
                p = p.left;
            }
        }
        if(p == null) return; //     

        if(p.left != null && p.right != null) { //             
            //            
            var minP = p.right;
            var minPP = p; // minPP  minP    
            while(minP.left != null) {
                pnode = minP;
                minP = p.left;
            }
            p.data = minP.data; //  minP      p 
            p = minP; //       minP 
            pp = minP;

        }
        //                   
        var childNode = null;
        if(p.left != null) {
            childNode = p.left;
        }else if(p.right != null) {
            childNode = p.right;
        }else {
            chiildNode = null;
        }
        if(pp == null) {
            p = chiildNode; //        
        }else if(pp.left == p) {
            pp.left = childNode;
        }else {
            pp.right = childNode;
        }
    }

実際,ツリーの削除操作については,単純に削除したノードを「削除済み」とマークするが,真の削除ではない非常に簡単で巧みな方法がある.これにより、削除する要素がメモリに格納され、メモリスペースが浪費されますが、削除操作は簡単で、挿入や検索のコード実装の難しさも増しません.

その他

二叉ルックアップツリーにはもう一つの重要な特性があり、中序が二叉ルックアップツリーを遍歴し、秩序あるデータシーケンスを入力することができ、時間複雑度はO(n)であり、非常に効率的である.したがって,二叉ルックアップツリーは二叉ソートツリーとも呼ばれる.