バイナリツリー2Binary Treeを使用すると、効率的にナビゲーションできると述べたことがあります.これをどのようにするか、管理方法について説明します.

バイナリナビゲーションツリー

これは、バイナリナビゲーションbinary searchと接続リストlinked listとを組み合わせた資料構造である.
ツリーには、2つのサブノード(1つはleft、1つはright)があり、現在のノードの値は現在のノードよりも小さく、leftノードの値は現在のノードよりも大きい.

挿入

挿入する値をノード内の値と比較し、左ノードから右ノードまでの下向きの配置方法を展開します.

したがって、ツリーrightは親ツリーより小さくなければならず、leftは親ツリーより大きくなければならない.

コード#コード#

public void add(int value){
    if(rootNode == null){
        rootNode = new DoubleLinkedList();
        rootNode.setValue(value);
        return;
    }

    if(rootNode.getValue() >= value){
        if(null != rootNode.getLeftNode()) {
            add(rootNode.getLeftNode(), value);
        }
        else{
            rootNode.setLeftNode(new DoubleLinkedList());
            rootNode.getLeftNode().setParentNode(rootNode);
            rootNode.getLeftNode().setValue(value);
        }
    }else{
        if(null != rootNode.getRightNode()) {
            add(rootNode.getRightNode(), value);
        }
        else{
            rootNode.setRightNode(new DoubleLinkedList());
            rootNode.getRightNode().setParentNode(rootNode);
            rootNode.getRightNode().setValue(value);
        }
    }
}

private void add(DoubleLinkedList node, int value){
    if(null == node)
        return;

    if(node.getValue() >= value){
        if(null != node.getLeftNode()) {
            add(node.getLeftNode(), value);
        }
        else{
            node.setLeftNode(new DoubleLinkedList());
            node.getLeftNode().setParentNode(node);
            node.getLeftNode().setValue(value);
        }
    }else{
        if(null != node.getRightNode()) {
            add(node.getRightNode(), value);
        }
        else{
            node.setRightNode(new DoubleLinkedList());
            node.getRightNode().setParentNode(node);
            node.getRightNode().setValue(value);
        }
    }
}

検索

最後に構成されたツリーでrightを検索したとき.

初めて木に入ると4が見えます.さらに、3は4より大きいので、3ノードを表示する必要はありません.また、leftのノードのうち5は4よりも小さいので、5のノードを検索すると、leftのノードの5を表示する必要がなくなります.
これにより,探索(O(n)O(n)O(n)O(n))に比べて,探索ごとに探索範囲が半分に縮小する.ノード数が2 k(木の高さ)2^{k(木の高さ)}2 k(木の高さ)であると仮定すると、挿入するたびに高さが減算・低減されるため、高さ数246142のノードのみが探索されるので、k=log 2 n𕚴O(logn)k=log 2}n聡O(logn)k=log 2 n)k=log 2 n𕚲O(logn)の速度が期待できる.もっと速くなった

コード#コード#

private DoubleLinkedList findNode(int value){
    if(rootNode.getValue() == value)
        return rootNode;

    DoubleLinkedList node = null;
    if(rootNode.getValue() > value){
        node = findNode(rootNode.getLeftNode(), value);
    }
    else if(rootNode.getValue() < value){
        node = findNode(rootNode.getRightNode(), value);
    }

    return node;
}
private DoubleLinkedList findNode(DoubleLinkedList node, int value){
    if(null == node)
        return null;

    DoubleLinkedList node2 = null;
    if(node.getValue() > value){
        node2 = findNode(node.getLeftNode(), value);
    }
    else if(node.getValue() < value){
        node2 = findNode(node.getRightNode(), value);
    }
    else{
        node2 = node;
    }
    return node2;
}

削除

rightを削除するには、3つの前提条件を満たす必要があります.

削除するノード(以下削除ノードと略す)のサブノード数0

削除ノードのサブノード数

削除ノードの2つのサブノード数

すべての例を処理するには、次のツリーを構成します.

削除ノードのサブノード数は0

この状況は簡単だ.削除ノードの接続を解除するだけです.

削除ノードのサブノード数1

kが削除されたとします.サブノードはDeleteに1つあります.

この場合、親ノード15は、削除ノードrightの子ノード12を参照する.例では、rightがあるが、18のみであれば、そのサブノードを参照することができる.

削除ノードのサブノード数

この状況は少し複雑だ.まず、削除ノードに配置するノードを決定する必要があります.
配置するノード(データムノードと呼ばれる)
1.ノードrightの中で最大のノードを削除する
2.ノードleftの最小ノードを削除
一般にleft番を基準ノードとする.right号を基準にお伝えします
2ノードを削除するには、そのノードのデータムノードは2ノードです.削除ノードの値を18に変更した場合は、バイナリ検索ツリー規則を保持したまま削除できます.
データムノード19に15ノードが存在する場合、削除ノードの19ノードrightをデータムノードの一番右側に配置することができる.

このようにして、基準ノードの位置に基準ノードのrightノードを置くことができる.
削除ロジックをクリアします.
バイナリナビゲーションツリー要素の削除
1.削除ノードの場所を決定する
1-1. 削除ノードに基づく21ノードのうち最大のノード
1-2. 削除ノードに基づくrightノードのうち最大のノード->通常2番使用
2.対応するデータムノードを削除ノードに配置します.
2-1. (2つのデータムノードを指定)削除ノードのleftノードがデータムノードの末尾にあるrightノード

コード#コード#

public void delete(int value){
    DoubleLinkedList deleteNode = findNode(value);
    if(null == deleteNode)
        return;

    // 1. 자식이 없음
    if(deleteNode.getLeftNode() == null && deleteNode.getRightNode() == null){
        if(deleteNode == rootNode){
            rootNode = null;
            return;
        }

        var parentNode = deleteNode.getParentNode();
        if(deleteNode == parentNode.getLeftNode())
            parentNode.setLeftNode(null);
        else if(deleteNode == parentNode.getRightNode())
            parentNode.setRightNode(null);
        deleteNode.setParentNode(null);
    }
    // 2-1. 좌측에만 존재
    else if(deleteNode.getLeftNode() != null && deleteNode.getRightNode() == null){
        var leftNode= deleteNode.getLeftNode();
        if(deleteNode == rootNode){
            rootNode = leftNode;
        }else{
            var parentNode = deleteNode.getParentNode();
            if(deleteNode == parentNode.getLeftNode()){
                parentNode.setLeftNode(leftNode);

            }
            else if(deleteNode == parentNode.getRightNode()){
                parentNode.setRightNode(leftNode);
            }

            deleteNode.setParentNode(null);
            deleteNode.setLeftNode(null);
            deleteNode.setRightNode(null);
        }
    }
    // 2-2. 우측에만 존재
    else if(deleteNode.getLeftNode() == null && deleteNode.getRightNode() != null){
        var rightNode= deleteNode.getRightNode();
        if(deleteNode == rootNode){
            rootNode = deleteNode.getRightNode();
        }else{
            var parentNode = deleteNode.getParentNode();
            if(deleteNode == parentNode.getLeftNode()){
                parentNode.setLeftNode(rightNode);

            }
            else if(deleteNode == parentNode.getRightNode()){
                parentNode.setRightNode(rightNode);
            }

            deleteNode.setParentNode(null);
            deleteNode.setLeftNode(null);
            deleteNode.setRightNode(null);
        }
    }
    // 3. 자식이 두개 존재
    else{
        // 1. 기준 노드 -> 삭제 노드의 우측 자식 중 가장 작은 노드
        var minNode = deleteNode.getRightNode();
        while(null != minNode.getLeftNode())
            minNode = minNode.getLeftNode();

        if(null == minNode)
            return;

        // 2-1. 기준 노드 좌측에 삭제 노드의 좌측 노드 배치
        if(deleteNode.getLeftNode() != minNode){
            minNode.setLeftNode(deleteNode.getLeftNode());
        }
        // 2-2. 기준 노드 우측에 삭제 노드의 '최'우측 노드 배치
        if(deleteNode.getRightNode() != minNode){
            var minestNode = minNode;
            while(null != minestNode.getRightNode())
                minestNode = minestNode.getRightNode();
            minestNode.setRightNode(deleteNode.getRightNode());
            // 삭제 노드 좌측 노드 삭제
            deleteNode.getRightNode().setLeftNode(null);
        }
        // 2-3. 기준 노드를 삭제 노드 위치에 배치(삭제 노드의 부모 위치)
        if(null != deleteNode.getParentNode()){
            var parentNode = deleteNode.getParentNode();
            if(deleteNode == parentNode.getLeftNode()){
                parentNode.setLeftNode(minNode);
            }
            else if(deleteNode == parentNode.getRightNode()){
                parentNode.setRightNode(minNode);
            }
        }

        deleteNode.setParentNode(null);
        deleteNode.setLeftNode(null);
        deleteNode.setRightNode(null);
    }

}

private DoubleLinkedList findNode(int value){
    if(rootNode.getValue() == value)
        return rootNode;

    DoubleLinkedList node = null;
    if(rootNode.getValue() > value){
        node = findNode(rootNode.getLeftNode(), value);
    }
    else if(rootNode.getValue() < value){
        node = findNode(rootNode.getRightNode(), value);
    }

    return node;
}
private DoubleLinkedList findNode(DoubleLinkedList node, int value){
    if(null == node)
        return null;

    DoubleLinkedList node2 = null;
    if(node.getValue() > value){
        node2 = findNode(node.getLeftNode(), value);
    }
    else if(node.getValue() < value){
        node2 = findNode(node.getRightNode(), value);
    }
    else{
        node2 = node;
    }
    return node2;
}

バイナリナビゲーションツリーについての説明はここまでです.次に、バイナリ・ナビゲーション・ツリーで発生する可能性のある問題と、これらの問題をどのように解決するかについて説明します.

Reference

バイナリナビゲーションツリー実装