JavaでのAVLツリーのガイド

投稿日: 2022-11-03 2022-11-03
タグ: Algorithms, Java

1. 序章

このチュートリアルでは、AVLツリーを紹介し、値を挿入、削除、および検索するためのアルゴリズムを確認します。

2. AVLツリーとは何ですか？

発明者のAdelson-VelskyとLandisにちなんで名付けられたAVLツリーは、自己平衡型二分探索木（BST）です。

自己平衡ツリーは、いくつかの平衡規則に従って挿入と削除後の高さの平衡をとる二分探索木です。

BSTの最悪の場合の時間計算量は、ツリーの高さの関数です。具体的には、ツリーのルートからノードまでの最長のパスです。 N個のノードを持つBSTの場合、すべてのノードに0個または1個の子しかないとします。したがって、その高さはNに等しく、最悪の場合の検索時間はO（N）です。したがって、BSTの主な目標は、最大の高さをlog（N）に近づけることです。

ノードNのバランス係数はheight（right（N））– height（left（N））です。 AVLツリーでは、ノードのバランス係数は1、0、または-1のいずれかの値になります。

ツリーのノードオブジェクトを定義しましょう。

public class Node {
    int key;
    int height;
    Node left;
    Node right;
    ...
}

次に、AVLTreeを定義しましょう。

public class AVLTree {

    private Node root;

    void updateHeight(Node n) {
        n.height = 1 + Math.max(height(n.left), height(n.right));
    }

    int height(Node n) {
        return n == null ? -1 : n.height;
    }

    int getBalance(Node n) {
        return (n == null) ? 0 : height(n.right) - height(n.left);
    }

    ...
}

3. AVLツリーのバランスをとる方法は？

AVLツリーは、ノードの挿入または削除後にノードのバランス係数をチェックします。ノードのバランス係数が1より大きいか、-1より小さい場合、ツリーはそれ自体をリバランスします。

ツリーのバランスを取り直すには、次の2つの操作があります。

右回転と
左回転。

3.1. 右回転

右回転から始めましょう。

T1と呼ばれるBSTがあり、Yがルートノード、XがYの左の子、ZがXの右の子であると仮定します。 BSTの特性を考えると、X

Yを右に回転させた後、Xをルート、YをXの右の子、ZをYの左の子として、T2というツリーが作成されます。 T2は、X

AVLTreeの正しい回転操作を見てみましょう。

Node rotateRight(Node y) {
    Node x = y.left;
    Node z = x.right;
    x.right = y;
    y.left = z;
    updateHeight(y);
    updateHeight(x);
    return x;
}

3.2. 左回転操作

左回転操作もあります。

T1と呼ばれるBSTを想定します。ここで、Yはルートノード、XはYの右の子、ZはXの左の子です。これを考えると、Y

Yを左に回転させた後、Xをルート、YをXの左の子、ZをYの右の子とするT2というツリーが作成されます。 T2は、Y

AVLTreeの左回転操作を見てみましょう。

Node rotateLeft(Node y) {
    Node x = y.right;
    Node z = x.left;
    x.left = y;
    y.right = z;
    updateHeight(y);
    updateHeight(x);
    return x;
}

3.3. リバランステクニック

より複雑な組み合わせで右回転と左回転の操作を使用して、ノードの変更後にAVLツリーのバランスを保つことができます。不均衡な構造では、少なくとも1つのノードのバランス係数が2または-2になります。このような状況でツリーのバランスをとる方法を見てみましょう。

ノードZのバランス係数が2の場合、Zをルートとするサブツリーは、YをZの右の子と見なして、これら2つの状態のいずれかになります。

最初のケースでは、Yの右の子の高さ（X）が、左の子の高さ（T2）よりも高くなっています。 Zを左に回転させることで、ツリーのバランスを簡単に取り戻すことができます。

2番目のケースでは、Yの右の子の高さ（T4）は、左の子の高さ（X）よりも低くなっています。この状況では、ローテーション操作の組み合わせが必要です。

この場合、最初にYを右に回転させるので、ツリーは前の場合と同じ形状になります。次に、Zを左に回転させることでツリーのバランスを取り直すことができます。

また、ノードZのバランス係数が-2の場合、そのサブツリーはこれら2つの状態のいずれかにあるため、Zをルート、Yを左の子と見なします。

Yの左の子の高さは、右の子の高さよりも高いため、Zの右回転とツリーのバランスを取ります。

または、2番目のケースでは、Yの右の子の高さが左の子よりも高くなっています。

そこで、まず、Yを左に回転させて前の形状に変換し、次にZを右に回転させてツリーのバランスを取ります。

AVLTreeのリバランス操作を見てみましょう。

Node rebalance(Node z) {
    updateHeight(z);
    int balance = getBalance(z);
    if (balance > 1) {
        if (height(z.right.right) > height(z.right.left)) {
            z = rotateLeft(z);
        } else {
            z.right = rotateRight(z.right);
            z = rotateLeft(z);
        }
    } else if (balance < -1) {
        if (height(z.left.left) > height(z.left.right))
            z = rotateRight(z);
        else {
            z.left = rotateLeft(z.left);
            z = rotateRight(z);
        }
    }
    return z;
}

変更されたノードからルートへのパスにあるすべてのノードのノードを挿入または削除した後、rebalanceを使用します。

4. ノードを挿入します

ツリーにキーを挿入するときは、BSTルールに合格するために適切な位置を見つける必要があります。したがって、ルートから開始して、その値を新しいキーと比較します。キーが大きい場合は右に進み、そうでない場合は左の子に移動します。

適切な親ノードが見つかったら、値に応じて、新しいキーをノードとして左または右に追加します。

ノードを挿入した後、BSTがありますが、AVLツリーではない可能性があります。したがって、バランス係数を確認し、新しいノードからルートへのパス内のすべてのノードのBSTを再バランスします。

挿入操作を見てみましょう。

Node insert(Node node, int key) {
    if (node == null) {
        return new Node(key);
    } else if (node.key > key) {
        node.left = insert(node.left, key);
    } else if (node.key < key) {
        node.right = insert(node.right, key);
    } else {
        throw new RuntimeException("duplicate Key!");
    }
    return rebalance(node);
}

キーはツリー内で一意であることを覚えておくことが重要です。2つのノードが同じキーを共有することはありません。

挿入アルゴリズムの時間計算量は、高さの関数です。ツリーはバランスが取れているため、最悪の場合の時間計算量はO（log（N））であると想定できます。

5. ノードを削除する

ツリーからキーを削除するには、最初にBSTでキーを見つける必要があります。

ノード（Zと呼ばれる）を見つけたら、ツリー内でそのノードの代わりとなる新しい候補を導入する必要があります。 Zが葉の場合、候補は空です。 Zに子が1つしかない場合は、この子が候補になりますが、Zに子が2つある場合、プロセスは少し複雑になります。

Yと呼ばれるZの右の子を想定します。まず、Yの左端のノードを見つけて、それをXと呼びます。次に、Zの新しい値をXの値と等しく設定し、YからXを削除し続けます。

最後に、最後にリバランスメソッドを呼び出して、BSTをAVLツリーに保ちます。

削除方法は次のとおりです。

Node delete(Node node, int key) {
    if (node == null) {
        return node;
    } else if (node.key > key) {
        node.left = delete(node.left, key);
    } else if (node.key < key) {
        node.right = delete(node.right, key);
    } else {
        if (node.left == null || node.right == null) {
            node = (node.left == null) ? node.right : node.left;
        } else {
            Node mostLeftChild = mostLeftChild(node.right);
            node.key = mostLeftChild.key;
            node.right = delete(node.right, node.key);
        }
    }
    if (node != null) {
        node = rebalance(node);
    }
    return node;
}

削除アルゴリズムの時間計算量は、ツリーの高さの関数です。挿入方法と同様に、最悪の場合の時間計算量はO（log（N））であると想定できます。

6. ノードを検索する

AVLツリーでノードを検索するのはで、他のBSTと同じです。

ツリーのルートから開始し、キーをノードの値と比較します。キーが値と等しい場合は、ノードを返します。キーが大きい場合は右の子から検索し、そうでない場合は左の子から検索を続けます。

検索の時間計算量は、高さの関数です。最悪の場合の時間計算量はO（log（N））であると想定できます。

サンプルコードを見てみましょう。

Node find(int key) {
    Node current = root;
    while (current != null) {
        if (current.key == key) {
            break;
        }
        current = current.key < key ? current.right : current.left;
    }
    return current;
}

7. 結論

このチュートリアルでは、挿入、削除、および検索操作を備えたAVLツリーを実装しました。

いつものように、コードはGithubにあります。

getdocs

13036