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에서 left-heavy입니다. 아래 그림 (c)와 같이 LL 회전을 수행하여 AVL 트리를 만듭니다.

34를 입력하면 아래 그림(d)와 같은 트리가 표시됩니다. 50을 입력하면 아래 그림(e)와 같은 트리가 된다. 나무의 균형이 맞지 않습니다. 노드 25에서 right-heavy입니다. 아래 그림(f)과 같이 RR 회전을 수행하여 AVL 트리를 만듭니다.

30을 입력하면 아래 그림(g)과 같은 트리가 됩니다. 나무의 균형이 맞지 않습니다. 아래 그림 (h)와 같이 RL 회전을 수행하여 AVL 트리를 만듭니다.

10을 입력하면 아래 그림(i)과 같은 트리가 됩니다. 나무의 균형이 맞지 않습니다. 아래 그림 (j)와 같이 LR 회전을 수행하여 AVL 트리를 만듭니다.

아래 그림은 요소가 삭제됨에 따라 트리가 어떻게 진화하는지 보여줍니다. 34, 30, 50을 삭제하면 아래 그림(b)와 같은 트리가 된다. 나무의 균형이 맞지 않습니다. 아래 그림 (c)와 같이 LL 회전을 수행하여 AVL 트리를 만듭니다.

5번을 삭제하면 아래 그림(d)와 같은 트리가 됩니다. 나무의 균형이 맞지 않습니다. 아래 그림 (e)와 같이 RL 회전을 수행하여 AVL 트리를 만듭니다

위 내용은 AVLTree 클래스 테스트의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!