データ構造のツリー学習ノート

データ構造のツリー学習ノート-java
目次

データ構造のツリー学習ノート-java

一級目次

二次ディレクトリ

三級ディレクトリ

ツリー

とは

ツリーの実装

二叉木とその実現

ツリーの遍歴-深さ優先探索

広さ優先探索(BFS)

二叉ルックアップツリー

ベースメソッド実装-

挿入

ベースメソッド実装-検索

ベースメソッド実装-削除

AVLツリー-バランスツリー

平衡方法-単回転

平衡方法-二重回転

いつ単回転するか、いつ双回転バランス

を使用するか

二叉ルックアップツリー-平均時間複雑度分析

一級目次
二次ディレクトリ
三級目次
木とは
参考博文
ツリー(tree)は、ノード(node)と呼ばれるエンティティの集合である.ノードは、エッジ(edge)を介して接続される.各ノードは値またはデータ(value/date)を含み、各ノードにはサブノードがない場合もある.
木の最初のノードをルートノード(rootノード)と言います.このルートノードが他のノードに接続されている場合、ルートノードは親ノード(parent node、ルートノードに接続されているのは子ノード(child node)である.
すべてのノードはエッジ(edge)で接続されています.ノード間の関係を管理するため、ツリーで重要な概念です.
葉の結点(leaves)は、木の末端であり、子の結点はない.
ツリーの高さ(height)と深さ(depth)

木の高さは、葉の結点(木の末端)までの長さ

である.

ノードの深さは、ルートノードまでの長さ

である.
ツリーの実装

class TreeNode{
    object element;
    TreeNode firstChild;
    TreeNode nextchild；
}

すべてのサブノードを親ノードに向けるわけではありません.各ノードのサブノードが多く未知である可能性があるため、実現が難しく、スペースが浪費されます.
上記の方法では、親ノードは最初のサブノードのみを記録します.サブノード間でチェーンテーブルを作成して記録します.
木の構造はあまり使われていませんが、私たちがよく使うのは二叉木です.
二叉木とその実現とは
コンピュータ科学の分野では、二叉木は木のデータ構造で、ノードごとに最大2人の子供がいて、左の子供と右の子供と呼ばれています.

class BinaryTree {
    public BinaryTree left; //   
    public BinaryTree right; //   
    public String data;  //    
    }

ツリーの遍歴-深さ優先検索
略称DFS(Depth-First Search)
DFSはまた、前系列、中系列、後系列に分けられる
前の順序:

出力ノードの値

は、左ノードに入り、出力する.左ノードがある場合のみ.

は右ノードに入り、出力する.右ノード

がある場合のみ、

/**
     *     
     *
     * @param node
     */
    public static void preOrder(BinaryTree node) {
        if (node != null) {

            System.out.println(node.data);

            if (node.left != null) {
                node.left.preOrder(node.left);
            }

            if (node.right != null) {
                node.right.preOrder(node.right);
            }
        }
    }

中順:

左接点に入り出力する.左接点がある場合のみ.

ルートノードの値を出力します.

は、ノードに入り、出力する.ノードがある場合のみ.

コード実装:

/**
     *     
     *
     * @param node
     */
    public static void inOrder(BinaryTree node) {
        if (node != null) {
            if (node.left != null) {
                node.left.inOrder(node.left);
            }

            System.out.println(node.data);

            if (node.right != null) {
                node.right.inOrder(node.right);
            }
        }
    }

後の順序:

左接点出力、

に入る

右ノード出力

に入る.

出力ルートノード

/**
     *     
     *
     * @param node
     */
    public static void postOrder(BinaryTree node) {
        if (node != null) {
            if (node.left != null) {
                node.left.postOrder(node.left);
            }

            if (node.right != null) {
                node.right.postOrder(node.right);
            }

            System.out.println(node.data);
        }
    }

広さ優先探索(BFS)

まずaddメソッドでルートノードをキューに追加します.

キューが空でない場合に反復します.

キュー内の最初のノードを取得し、その値

を出力する.

左ノードと右ノードをキュー

に追加

キューの助けを得て、各ノード値を

に出力します.

/**
     *     
     *
     * @param node
     */
    public static void bfsOrder(BinaryTree node) {
        if (node != null) {
            Queue queue = new ArrayDeque();
            queue.add(node);

            while (!queue.isEmpty()) {
                BinaryTree current_node = queue.poll();

                System.out.println(current_node.data);

                if (current_node.left != null) {
                    queue.add(current_node.left);
                }
                if (current_node.right != null) {
                    queue.add(current_node.right);
                }
            }
        }
    }

ツリー
二叉検索ツリーは二叉順序ツリーまたは二叉順序ツリーと呼ばれる場合があり、二叉検索ツリーの値は順序の順序に格納されるため、検索テーブルや他の操作では半減検索原理を使用することができる.--Wikipedia
ツリー内のノードの値が左サブツリーのすべてのノードより大きく、右サブツリーのすべてのノードより大きい
ベースメソッド実装-挿入

新しいノードの値は現在のノードより大きいですか、それとも現在のノードより小さいですか.

新しいノードの値が現在のノードより大きい場合は、右ノードに移動します.現在のノードに右ノードがない場合は、そこに新しいノードを挿入します.そうでない場合は、ステップ1に戻ります.

新しいノードの値が現在のノードより小さい場合は、左ノードに移動します.現在のノードに左ノードがない場合は、そこに新しいノードを挿入します.そうでない場合は、ステップ1に戻ります.

ここでは、特別な状況を処理していません.新しいノードの値がノードの現在の値に等しい場合、ルール3を使用します.サブノードの左側に等しい値を挿入することを考慮します.

コード実装:

/**
     *    
     *
     * @param node
     * @param value
     */
    public void insertNode(BinaryTree node, Integer value) {
        if (node != null) {
            if (value <= Integer.valueOf(node.data) && node.left != null) {
                node.left.insertNode(node.left, value);
            } else if (value <= Integer.valueOf(node.data)) {
                node.left = new BinaryTree(String.valueOf(value));
            } else if (value > Integer.valueOf(node.data) && node.right != null) {
                node.right.insertNode(node.right, value);
            } else {
                node.right = new BinaryTree(String.valueOf(value));
            }
        }
    }

簡単そうに見えます.
このアルゴリズムの強みは、その再帰部分である9行目と13行目です.この2行のコードはいずれもinsertNodeメソッドを呼び出し、それぞれ左ノードと右ノードに使用します.11行目と15行目は、サブノードに新しいノードを挿入します.
ベースメソッド実装-検索

現在のノードとしてルートノードで開始します.現在のノード値よりも小さい値を指定しますか?もしそうであれば、左サブツリーで検索します.

現在のノード値より大きい値を指定しますか?もしそうであれば、右のサブツリーで検索します.

ルール＃1および＃2が偽である場合、現在のノード値と所与の値が等しいかどうかを比較することができ、一般にtrueに直接戻ることもできる.

コード実装:

 public boolean findNode(BinaryTree node, Integer value) {
        if (node != null) {
            if (value < Integer.valueOf(node.data) && node.left != null) {
                return node.left.findNode(node.left, value);
            }
            if (value > Integer.valueOf(node.data) && node.right != null) {
                return node.right.findNode(node.right, value);
            }
            return value == Integer.valueOf(node.data);
            //returen true;
        }
        return false;
    }

ベースメソッド実装-削除

は、いくつかのサブノードがあると判断する.

サブノードがない場合は、直接削除します.

サブノードが1つしかない場合、ノードの親ノードがサブノードを指す.

子供が2人いるノードは、そのノードの右サブノードから最小値を持つノードを見つける必要があります.最小値を持つこのノードを削除されたノードの位置に配置します.

コード実装:

    /**
     *     
     * @param node
     * @param value
     * @param parent
     * @return
     */
    public boolean removeNode(BinaryTree node, Integer value, BinaryTree parent) {
        if (node != null) {
            if (value < Integer.valueOf(node.data) && node.left != null) {
                return node.left.removeNode(node.left, value, node);
            } else if (value < Integer.valueOf(node.data)) {
                return false;
            } else if (value > Integer.valueOf(node.data) && node.right != null) {
                return node.right.removeNode(node.right, value, node);
            } else if (value > Integer.valueOf(node.data)) {
                return false;
            } else {
                if (node.left == null && node.right == null && node == parent.left) {
                    parent.left = null;
                    node.clearNode(node);
                } else if (node.left == null && node.right == null && node == parent.right) {
                    parent.right = null;
                    node.clearNode(node);
                } else if (node.left != null && node.right == null && node == parent.left) {
                    parent.left = node.left;
                    node.clearNode(node);
                } else if (node.left != null && node.right == null && node == parent.right) {
                    parent.right = node.left;
                    node.clearNode(node);
                } else if (node.right != null && node.left == null && node == parent.left) {
                    parent.left = node.right;
                    node.clearNode(node);
                } else if (node.right != null && node.left == null && node == parent.right) {
                    parent.right = node.right;
                    node.clearNode(node);
                } else {
                    node.data=String.valueOf(node.right.findMinValue(node.right));
                    node.right.removeNode(node.right,Integer.valueOf(node.right.data),node);
                }
                return true;
            }
        }
        return false;
    }

AVLツリー-バランスツリー
定義:各ノードの左サブツリーと右サブツリーの高さが最大1差のツリーを検索します.
定義が満たされていない場合は、バランスメソッドを使用して満たす必要があります.つまり、ツリーをバランスさせる必要があります.挿入または削除するバランスだけです.
コード実装

    private static class AvlNode{
        AvlNode(AnyType theElement)
        {this(theElement,null,null);}
        AvlNode(AnyType theElement,AvlNode lt,AvlNode rt)
        {element =theElement;left = lt;right=rt;height=0;}
        AnyType element;
        AvlNode left;
        AvlNode right;
        int height;
    }
    private  int height(AvlNode t){
        return t=null?-1:t.height;
    }

バランス方法-単一回転
単回転の本質は,老子ノードを新しいルートノードとし,それから老跟ノードを新しい跟ノードのサブノードとすることである.
単回転はまた左回転と右回転に分けられます.これは孫ノードと根ノードの大きさによって区別されます.孫ノードが根ノードより小さい場合、アンバランスな点は必ずノードの左ノードについています.この場合、左サブノードをヒールノードとして、古いノードを彼の右ノードとして、古い左ノードの右サブツリーを新しい右ノードの左サブツリーとして、このようにして左サブノードを軸にして、ルートノードを時計回りに左に回転させ、右に回転させるのも同じ理屈です.
上の話は「データ構造とアルゴリズム分析」(java)第4章第4小節の理解で、本には図があります.ここは面倒なので描きません.
左回転コード実装

    private AvlNode rotateLeft(AvlNode root){
        AvlNode newRoot=root.left;
        root.left=newRoot.right;
        newRoot.right=root;
        root.height=Math.max(height(root.left),height(root.right))+1;
        newRoot.height=Math.max(height(newRoot.left),root.height)+1;
        return newRoot;
    }

右旋同理
バランス方法-二重回転
2回転は実は2回の単回転です.1回の単回転では問題が解決できない場合がありますが、2回使用する必要があります.使用状況は以下の通りです.
二重回転はまた左右回転と右左回転に分けられ、二回の単回転の方向によって決まる.
右左回転コード実装

private AvlNode doubleRotateRightleft(AvlNode root){
    root.left=rotateRight(root.left);
    return rotateLeft(root);
}

いつ単回転するか、いつ二回転バランスを使うか
ルートノードの左サブツリーの高さが右サブツリーの高さより1より大きく、ルートノードの左ノードの高さが右ノードの高さより大きい場合
左回転を使用
または、ルートノードの右サブツリーの高さが左サブツリーの高さより1より大きく、ルートノードの右ノードが左ノードの高さより大きい場合、
右回転を使用します.
ルートノードの左サブツリーの高さが右サブツリーの高さより1より大きく、ルートノードの左ノードの高さが右ノードの高さより小さい場合
右左回転を使用
または、ルートノードの右サブツリーの高さが左サブツリーの高さより1より大きく、ルートノードの右ノードが左ノードの高さより小さい場合、
左右の回転を使います.
具体的な原因は《データ構造とアルゴリズム分析》(java)第4章第4小節を見ることができる
二叉ルックアップツリー-平均時間複雑度分析
以上の探索により実現されることが分かる.探索の時間複雑度はO(d),dはデータノード深さである.
一連の計算dの平均値=logn,nはデータ整数である.
具体的な計算は「データ構造とアルゴリズム分析」(java)第4章第3小節を見ることができる.