AVLTree クラスのテスト

このセクションでは、AVLTree クラスの使用例を示します。以下のコードはテスト プログラムを提供します。プログラムは、整数 25、20、および 5 の配列で初期化された AVLTree を作成し (7 行目)、要素を11 ～ 20 行目を削除し、24 ～ 30 行目の要素を削除します。 AVLTree は BST のサブクラスであり、BST 内の要素は反復可能であるため、プログラムは foreach ループを使用して 35 ～ 37 行目のすべての要素を走査します。 .

package demo;

public class TestAVLTree {

    public static void main(String[] args) {
        // Create an AVL tree
        AVLTree<Integer> tree = new AVLTree<>(new Integer[]{25, 20, 5});
        System.out.print("After inserting 25, 20, 5:");
        printTree(tree);

        tree.insert(34);
        tree.insert(50);
        System.out.print("\nAfter inserting 34, 50:");
        printTree(tree);

        tree.insert(30);
        System.out.print("\nAfter inserting 30");
        printTree(tree);

        tree.insert(10);
        System.out.print("\nAfter inserting 10");
        printTree(tree);

        tree.delete(34);
        tree.delete(30);
        tree.delete(50);
        System.out.print("\nAfter removing 34, 30, 50:");
        printTree(tree);

        tree.delete(5);
        System.out.print("\nAfter removing 5:");
        printTree(tree);

        System.out.print("\nTraverse the elements in the tree: ");
        for (int e: tree) {
            System.out.print(e + " ");
        }
    }

    public static void printTree(BST tree) {
        // Traverse tree
        System.out.print("\nInorder (sorted): ");
        tree.inorder();
        System.out.print("\nPostorder: ");
        tree.postorder();
        System.out.print("\nPreorder: ");
        tree.preorder();
        System.out.print("\nThe number of nodes is " + tree.getSize());
        System.out.println();
    }
}

25、20、5 を挿入した後:
順序 (並べ替え): 5 20 25
事後注文: 5 25 20
予約注文: 20 5 25
ノード数は3です

34、50 を挿入した後:
順序 (並べ替え): 5 20 25 34 50
事後: 5 25 50 34 20
予約注文: 20 5 34 25 50
ノード数は5です

30本挿入後
順序 (並べ替え): 5 20 25 30 34 50
事後注文: 5 20 30 50 34 25
予約注文: 25 20 5 34 30 50
ノード数は6です

10個挿入後
順序 (並べ替え): 5 10 20 25 30 34 50
事後: 5 20 10 30 50 34 25
予約注文: 25 10 5 20 34 30 50
ノード数は7です

34、30、50 を削除した後:
順序 (並べ替え): 5 10 20 25
事後注文: 5 20 25 10
予約注文: 10 5 25 20
ノード数は4です

5 を削除した後:
順序 (並べ替え): 10 20 25
事後注文: 10 25 20
予約注文: 20 10 25
ノード数は3です

ツリー内の要素をトラバースします: 10 20 25

下の図は、要素がツリーに追加されるにつれてツリーがどのように進化するかを示しています。 25 と 20 を追加すると、ツリーは下図 (a) のようになります。以下の図 (b) に示すように、5 は 20 の左の子として挿入されます。木のバランスが取れていません。ノード 25 では左重みになります。下の図 (c) に示すように、LL 回転を実行して AVL ツリーを生成します。

34 を挿入すると、ツリーは下図 (d) のようになります。 50 を挿入すると、ツリーは下図 (e) のようになります。木のバランスが取れていません。ノード 25 では右ヘビーです。下の図 (f) に示すように、RR ローテーションを実行して AVL ツリーを生成します。

30を挿入すると、ツリーは下図(g)のようになります。木のバランスが取れていません。 RL ローテーションを実行すると、下の図 (h) に示すように、AVL ツリーが生成されます。

10を挿入すると、ツリーは下図(i)のようになります。木のバランスが取れていません。 LR 回転を実行すると、下の図 (j) に示すように、AVL ツリーが生成されます。

下の図は、要素が削除されるにつれてツリーがどのように進化するかを示しています。 34、30、50 を削除すると、ツリーは下図 (b) のようになります。木のバランスが取れていません。 LL ローテーションを実行すると、下の図 (c) に示すように、AVL ツリーが生成されます。

5を削除すると、ツリーは下図(d)のようになります。木のバランスが取れていません。以下の図 (e)

に示すように、RL ローテーションを実行して AVL ツリーを生成します。

以上がAVLTree クラスのテストの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。