Java를 사용하여 AVL 트리 알고리즘을 구현하는 방법

Java를 사용하여 AVL 트리 알고리즘을 구현하는 방법

소개:
AVL 트리는 삽입 및 삭제 작업 중에 자동으로 균형을 유지하여 트리 높이가 항상 유지되도록 할 수 있는 자체 균형 이진 검색 트리입니다. . 이번 글에서는 자바를 이용하여 AVL 트리 알고리즘을 구현하는 방법을 알아보고 구체적인 코드 예시를 제공하겠습니다.

1. AVL 트리의 기본 설명 및 특성:
AVL 트리는 1962년 G. M. Adelson-Velsky와 Evgenii Landis에 의해 제안되었습니다. AVL 트리에서는 각 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 1을 초과할 수 없습니다. 1을 초과하면 자동 밸런싱을 위해 회전 동작이 필요합니다. 일반 이진 검색 트리와 비교하여 AVL 트리는 검색, 삽입 및 삭제 성능이 더 좋습니다.

2. AVL 트리의 노드 구현:
Java에서는 사용자 정의 노드 클래스를 사용하여 AVL 트리를 구현할 수 있습니다. 각 노드에는 왼쪽 및 오른쪽 하위 트리에 대한 값과 참조뿐만 아니라 노드의 높이를 기록하는 변수도 포함되어 있습니다.

class AVLNode {
    int val;
    AVLNode left, right;
    int height;

    AVLNode(int val) {
        this.val = val;
        this.height = 1;
    }
}

3. 노드 높이 계산:
AVL 트리 알고리즘을 구현하기 전에 노드 높이를 계산하는 함수가 필요합니다. 이 함수는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이를 재귀적으로 계산한 후 둘 중 더 큰 값에 1을 더하여 현재 노드의 높이를 구합니다.

int getHeight(AVLNode node) {
    if (node == null) {
        return 0;
    }
    return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

4. AVL 트리의 회전 작업 구현:
작업을 삽입하고 삭제할 때 트리의 균형을 유지하려면 AVL 트리를 회전해야 합니다. 왼손 및 오른손 작업을 모두 구현하겠습니다.

1. 왼쪽 회전 작업:
   왼쪽 회전은 현재 노드의 오른쪽 하위 트리를 새 루트 노드로 승격시키는 것입니다. 원래 루트 노드는 새 루트 노드의 왼쪽 하위 트리가 되고 원래 새 루트 노드의 왼쪽 하위 트리가 됩니다. 원래 루트 노드의 오른쪽 하위 트리가 됩니다.

AVLNode leftRotate(AVLNode node) {
    AVLNode newRoot = node.right;
    AVLNode temp = newRoot.left;

    newRoot.left = node;
    node.right = temp;

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;

    return newRoot;
}

2. 오른쪽 회전 작업:
   오른쪽 회전은 현재 노드의 왼쪽 하위 트리를 새 루트 노드로 승격시키는 것이며, 원래 루트 노드는 새 루트 노드의 오른쪽 하위 트리가 되고, 원래 새 노드의 오른쪽 하위 트리가 됩니다. 루트 노드는 원래 루트 노드의 왼쪽 하위 트리가 됩니다.

AVLNode rightRotate(AVLNode node) {
    AVLNode newRoot = node.left;
    AVLNode temp = newRoot.right;

    newRoot.right = node;
    node.left = temp;

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;

    return newRoot;
}

5. 삽입 작업 구현:
새 노드를 삽입할 때 먼저 이진 검색 트리의 규칙에 따라 삽입된 다음 삽입 경로에서 노드의 균형 요소에 따라 조정됩니다. 회전 작업 및 노드 업데이트가 포함됩니다.

AVLNode insert(AVLNode node, int val) {
    if (node == null) {
        return new AVLNode(val);
    }

    if (val < node.val) {
        node.left = insert(node.left, val);
    } else if (val > node.val) {
        node.right = insert(node.right, val);
    } else {
        // 如果节点已经存在，不进行插入
        return node;
    }

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    int balanceFactor = getBalanceFactor(node);

    // 左左情况，需要进行右旋
    if (balanceFactor > 1 && val < node.left.val) {
        return rightRotate(node);
    }

    // 左右情况，需要进行左旋后再进行右旋
    if (balanceFactor > 1 && val > node.left.val) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 右右情况，需要进行左旋
    if (balanceFactor < -1 && val > node.right.val) {
        return leftRotate(node);
    }

    // 右左情况，需要进行右旋后再进行左旋
    if (balanceFactor < -1 && val < node.right.val) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

6. 삭제 작업 구현:
노드를 삭제할 때 먼저 이진 검색 트리의 규칙에 따라 삭제된 다음 삭제 경로에서 노드의 균형 요소에 따라 조정됩니다. 작업 및 노드 높이 업데이트.

AVLNode delete(AVLNode node, int val) {
    if (node == null) {
        return node;
    }

    if (val < node.val) {
        node.left = delete(node.left, val);
    } else if (val > node.val) {
        node.right = delete(node.right, val);
    } else {
        if (node.left == null || node.right == null) {
            node = (node.left != null) ? node.left : node.right;
        } else {
            AVLNode successor = findMin(node.right);
            node.val = successor.val;
            node.right = delete(node.right, node.val);
        }
    }

    if (node == null) {
        return node;
    }

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    int balanceFactor = getBalanceFactor(node);

    // 左左情况，需要进行右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
        return rightRotate(node);
    }

    // 左右情况，需要进行左旋后再进行右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 右右情况，需要进行左旋
    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
        return leftRotate(node);
    }

    // 右左情况，需要进行右旋后再进行左旋
    if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

AVLNode findMin(AVLNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

7. 테스트 예:
우리가 구현한 AVL 트리 알고리즘의 정확성을 확인하기 위해 다음 예를 사용하여 테스트할 수 있습니다.

public static void main(String[] args) {
    AVLTree tree = new AVLTree();

    tree.root = tree.insert(tree.root, 10);
    tree.root = tree.insert(tree.root, 20);
    tree.root = tree.insert(tree.root, 30);
    tree.root = tree.insert(tree.root, 40);
    tree.root = tree.insert(tree.root, 50);
    tree.root = tree.insert(tree.root, 25);

    tree.inOrderTraversal(tree.root);
}

출력 결과:
10 20 25 30 40 50

요약:
이 기사에서는 Java를 사용하여 AVL 트리 알고리즘을 구현하는 방법을 소개하고 특정 코드 예제를 제공합니다. 삽입 및 삭제 작업을 구현함으로써 AVL 트리가 항상 균형을 이루도록 보장하여 검색, 삽입 및 삭제 성능을 향상시킬 수 있습니다. 나는 이 글을 공부함으로써 독자들이 AVL 트리 알고리즘을 더 잘 이해하고 적용할 수 있다고 믿습니다.

위 내용은 Java를 사용하여 AVL 트리 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!