How to implement AVL tree algorithm using java

How to use Java to implement the AVL tree algorithm

Introduction:
The AVL tree is a self-balancing binary search tree that can perform insertion and deletion It performs automatic balancing during operation to ensure that the height of the tree is always kept within a small range. In this article, we will learn how to implement the AVL tree algorithm using Java and provide concrete code examples.

1. Basic description and characteristics of AVL tree:
AVL tree was proposed by G. M. Adelson-Velsky and Evgenii Landis in 1962. In AVL tree, for each node, its left child The height difference between the tree and the right subtree cannot exceed 1. If it exceeds 1, a rotation operation is required for automatic balancing. Compared with ordinary binary search trees, AVL trees have better search, insertion and deletion performance.

2. Node implementation of AVL tree:
In Java, we can use custom node classes to implement AVL trees. Each node contains a value and a reference to the left and right subtrees, as well as a variable to record the height of the node.

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

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

3. Calculate node height:
Before implementing the AVL tree algorithm, we need a function for calculating node height. This function obtains the height of the current node by recursively calculating the height of the left subtree and the right subtree, and then taking the larger value of the two and adding 1.

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

4. Implement the rotation operation of the AVL tree:
When inserting and deleting operations, the AVL tree needs to be rotated to maintain the balance of the tree. We will implement both left-hand and right-hand operations.

1. Left rotation operation:
   Left rotation is to promote the right subtree of the current node to the new root node. The original root node becomes the left subtree of the new root node. The left subtree of the original new root node The subtree becomes the right subtree of the original root node.

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. Right rotation operation:
   Right rotation is to promote the left subtree of the current node to the new root node, and the original root node becomes the right subtree of the new root node. The right subtree of the original new root node becomes the left subtree of the original root node.

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. Implementation of insertion operation:
When inserting a new node, it is first inserted according to the rules of the binary search tree, and then adjusted according to the balance factor of the node on the insertion path. , adjustments include rotation operations and updating node heights.

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. Implementation of deletion operation:
When deleting a node, it is first deleted according to the rules of the binary search tree, and then adjusted according to the balance factor of the node on the deletion path. The adjustment includes rotation. Manipulate and update node heights.

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. Test example:
In order to verify the correctness of the AVL tree algorithm we implemented, we can use the following example to test:

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);
}

Output result:
10 20 25 30 40 50

Summary:
This article introduces how to use Java to implement the AVL tree algorithm and provides specific code examples. By implementing insertion and deletion operations, we can ensure that the AVL tree is always balanced, resulting in better search, insertion, and deletion performance. I believe that by studying this article, readers can better understand and apply the AVL tree algorithm.

The above is the detailed content of How to implement AVL tree algorithm using java. For more information, please follow other related articles on the PHP Chinese website!