🥇二分木または二分探索木の準備方法

前奏曲

この記事は二分探索木について説明しています。最近こんな記事を書きましたハフマン方式によるデータ圧縮。そこでは、検索、挿入、削除の方法は関係なかったため、バイナリツリーにはあまり注意を払いませんでした。今回は樹木についての記事を書くことにしました。おそらく始めます。

ツリーは、エッジで接続されたノードで構成されるデータ構造です。ツリーはグラフの特殊なケースであると言えます。以下にツリーの例を示します。

これは二分探索木ではありません。すべてがカットの下にあります！

用語

ルート

木の根 最上位のノードです。この例では、これはノード A です。ツリーでは、ルートから他のノードにつながるパスは XNUMX つだけです。実際、どのノードも、このノードに対応するサブツリーのルートとみなすことができます。

親/子孫

ルートを除くすべてのノードには、別のノードにつながるエッジが XNUMX つだけあります。現在のノードの上のノードが呼び出されます。親このノード。現在のノードの下に位置し、それに接続されているノードはと呼ばれます。子孫このノード。例を挙げてみましょう。ノード B の場合、その親はノード A、子はノード D、E、および F になります。

Лист

子のないノードはツリーのリーフと呼ばれます。この例では、ノード D、E、F、G、I、J、K が葉になります。

これが基本的な用語です。他の概念については後で説明します。したがって、バイナリツリーは、各ノードが XNUMX つ以下の子を持つツリーです。ご想像のとおり、ノード B と H には XNUMX つ以上の子があるため、この例のツリーはバイナリではありません。バイナリツリーの例を次に示します。

ツリーのノードには任意の情報を含めることができます。二分探索木は、次の特性を持つ二分木です。

左右のサブツリーは両方とも二分探索ツリーです。
任意のノード X の左側のサブツリーのすべてのノードは、ノード X 自体のデータキー値よりも小さいデータキー値を持ちます。
任意のノード X の右側のサブツリーのすべてのノードは、ノード X 自体のデータキーの値以上のデータキー値を持ちます。

キー - ノードの何らかの特性 (数値など)。このキーは、このキーが対応するツリーの要素を見つけるために必要です。二分探索ツリーの例:

ツリー表示

理解を深めていただくために、作業を進めながら、いくつかの (おそらく不完全な) コードを含めます。完全なコードは記事の最後にあります。

ツリーはノードで構成されます。ノード構造:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }
    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }
//...остальные методы узла
}

各ノードには XNUMX つの子があります (leftChild および/または rightChild の子に null 値が含まれる可能性は十分にあります)。おそらく、この場合、数値データがノードに格納されているデータであることに気づいたでしょう。キー — ノードキー。

結び目はわかったので、今度は木に関する差し迫った問題について話しましょう。以下、「木」という言葉は二分探索木の概念を意味するものとする。二分木構造:

public class BinaryTree<T> {
     private Node<T> root;

    //методы дерева
}

クラスフィールドとして必要なのはツリーのルートのみです。ルートから getLeftChild() メソッドと getRightChild() メソッドを使用すると、ツリーの任意のノードにアクセスできるからです。

ツリーアルゴリズム

検索

構築されたツリーがあるとします。キー key を持つ要素を見つけるにはどうすればよいですか? ルートからツリーの下に順次移動し、キーの値を次のノードのキーと比較する必要があります。キーが次のノードのキーより小さい場合は、ノードの左の子孫に移動します。キーが大きい場合は、ノードの左の子孫に移動します。右側で、キーが等しい場合、目的のノードが見つかります。関連するコード:

public Node<T> find(int key) {
    Node<T> current = root;
    while (current.getKey() != key) {
        if (key < current.getKey())
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        if (current == null)
            return null;
    }
    return current;
}

current が null になった場合、反復はツリーの終わりに達しています (概念的なレベルでは、ツリー内の存在しない場所、つまりリーフの子にいます)。

バランスの取れたツリー (ノードがほぼ均等に分散されているツリー) での検索アルゴリズムの効率を考えてみましょう。その場合、検索効率は O(log(n)) となり、底 2 の対数になります。参照: バランスの取れたツリーに n 個の要素がある場合、ツリーには log(n) 底 2 のレベルがあることを意味します。そして検索では、サイクルの XNUMX ステップで XNUMX レベル下がります。

インサート

検索の本質を理解していれば、挿入を理解するのは難しくありません。 (検索で説明されている降下の規則に従って) 木の葉まで降りて、キーに応じて左または右の子孫になるだけです。実装：

   public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

この場合、カレントノードに加えて、カレントノードの親に関する情報を格納する必要がある。 current が null になると、親変数には必要なシートが含まれます。
挿入効率は明らかに検索の効率と同じになります - O(log(n))。

削除

削除は、ツリーに対して実行する必要がある最も複雑な操作です。まず、削除する要素を見つける必要があることは明らかです。しかし、それではどうでしょうか？単純にその参照を null に設定すると、このノードをルートとするサブツリーに関する情報が失われます。樹木の伐採方法はXNUMXつのケースに分けられます。

最初のケース。削除するノードには子がありません。

削除するノードに子がない場合、それはリーフであることを意味します。したがって、その親の leftChild フィールドまたは rightChild フィールドを null に設定するだけで済みます。

XNUMX番目のケース。削除するノードには XNUMX つの子があります

このケースもそれほど難しいものではありません。例に戻りましょう。キー 14 の要素を削除する必要があるとします。これはキー 10 のノードの右側の子であるため、その子孫 (この場合は右側) のいずれも 10 より大きいキーを持つことに同意します。ツリーからそれを簡単に「切り取り」、削除されるノードの子に親を直接接続できます。キー 10 を持つノードをノード 13 に接続します。親の左の子であるノードを削除する必要がある場合も、状況は同様になります。自分で考えてみてください - まさに例えです。

XNUMX番目のケース。ノードには XNUMX つの子があります

最も困難なケース。新しい例を見てみましょう。

後継者を探す

キー 25 を持つノードを削除する必要があるとします。代わりに誰を配置しますか? 彼の信者（子孫または子孫の子孫）の XNUMX 人は、次の者にならなければなりません。後継(削除されたノードの代わりとなるノード)。

誰が後継者になるべきかをどうやって知ることができますか？直感的には、これは、削除されるノードの次にキーが大きいツリー内のノードです。アルゴリズムは次のとおりです。その右の子に移動し（後続ノードのキーが削除されるノードのキーよりも大きいことがすでに述べられているため、常に右に移動します）、次にこの右の左の子のチェーンを通過する必要があります。子供。この例では、キー 35 のノードに移動し、その左側の子のチェーンをリーフまで下る必要があります。この場合、このチェーンはキー 30 のノードのみで構成されます。厳密に言えば、探しているのは目的のノードより大きいノードのセット内の最小のノード。

後続検索メソッドのコード:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;//родитель преемника
        Node<T> successor = deleteNode;//преемник
        Node<T> current = successor.getRightChild();//просто "пробегающий" узел
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        //на выходе из цикла имеем преемника и родителя преемника
        if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
            parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
            successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
        }
        return successor;
    }

delete メソッドの完全なコード:

public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;//В зависимости от того, является ли  удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {//второй случай
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {//третий случай
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

複雑さは O(log(n)) に近似できます。

ツリー内の最大値/最小値を見つける

明らかに、ツリー内の最小値/最大値を見つける方法は、ツリーの左/右要素のチェーンをそれぞれ順番に調べる必要があります。葉に到達すると、それが最小/最大要素になります。

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

複雑さ - O(log(n))

対称バイパス

トラバーサルとは、ツリーに対して何かを行うためにツリーの各ノードを訪問することです。

再帰的対称走査アルゴリズム:

左側の子に対してアクションを実行します
自分自身で行動を起こす
適切な子に対してアクションを実行します

コード：

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
            inOrder(current.getRightChild());
        }
    }

まとめ

ついに！何か説明していないことやコメントがある場合は、コメントをお待ちしています。約束どおり、完全なコードは次のとおりです。

ノード.java:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }

    public void setLeftChild(Node<T> newNode) {
        leftChild = newNode;
    }

    public void setRightChild(Node<T> newNode) {
        rightChild = newNode;
    }

    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }

    public T getData() {
        return data;
    }

    public int getKey() {
        return key;
    }
}

バイナリツリー.java:

public class BinaryTree<T> {
    private Node<T> root;

    public Node<T> find(int key) {
        Node<T> current = root;
        while (current.getKey() != key) {
            if (key < current.getKey())
                current = current.getLeftChild();
            else
                current = current.getRightChild();
            if (current == null)
                return null;
        }
        return current;
    }

    public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;
        Node<T> successor = deleteNode;
        Node<T> current = successor.getRightChild();
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }

        if (successor != deleteNode.getRightChild()) {
            parentSuccessor.setLeftChild(successor.getRightChild());
            successor.setRightChild(deleteNode.getRightChild());
        }
        return successor;
    }

    public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");
            inOrder(current.getRightChild());
        }
    }
}

PS

O(n) への縮退

気づいた方も多いかもしれませんが、木のバランスを崩してしまったらどうなるでしょうか？たとえば、キーが 1,2,3,4,5,6、XNUMX、XNUMX、XNUMX、XNUMX、XNUMX と増加するノードをツリーに配置すると、ツリーはリンクリストを彷彿とさせるものになります。そして、はい、ツリーはツリー構造を失い、したがってデータアクセスの効率が失われます。検索、挿入、および削除の操作の複雑さは、リンクリストの複雑さと同じになります: O(n)。これは、私の意見では、バイナリツリーの最も重要な欠点の XNUMX つです。

登録ユーザーのみがアンケートに参加できます。ログインお願いします。

私は長い間 Habré を利用していないのですが、どのようなトピックに関するどの記事をもっと見たいと思いますか?

データ構造
アルゴリズム (DP、再帰、データ圧縮など)
データ構造とアルゴリズムの実生活への応用
Java で Android アプリケーションをプログラミングする
Java Web アプリケーションプログラミング

2人のユーザーが投票しました。 1 ユーザーが棄権しました。

出典: www.habr.com

二分木または二分探索木の準備方法

前奏曲

用語

ルート