In computer science, AVL tree is the first self-balanced binary search tree invented. The maximum difference in height between two subtrees of any node in an AVL tree is 1, so it is also called a height balanced tree. Additions and deletions may require one or more tree rotations to rebalance the tree.

The characteristics of

AVL tree is essentially a binary search tree with the following characteristics:

  • It’s a binary search tree
  • The absolute value (balance factor) of the difference in height between the left and right subtrees of each node is at most 1.

Here is an AVL tree with a balance factor next to each node:

The height of the left subtree of node 4 is 0, and the right subtree does not exist, so the balance factor is 0 – (-1) = 1. All leaf nodes do not exist in the left and right subtrees, so the balance factor is 0.

For the AVL tree above, if 0 is inserted, then the binary tree at this time is:

The balance factor of node 4 is 2, which breaks the balance of AVL tree. So how to restore the balance of AVL? All you need to do is rotate left and rotate right.

rotating

The rotation of AVL tree can be divided into four cases, namely left-left, right-right, left-right and right-left.

Left left-handed

The case where all the nodes in the figure are tilted to the left is called left-left type. In this case, we rotate node 4 right to restore its balance.

Dextral: Rotate the two nodes clockwise so that parent node 4 is replaced by its left child node 1, and node 4 becomes the right child of node 1.

Here’s an example:The balance factor of node 6 is 2. At this time, it is left-left type and the operation is right-handed. The right child of node 4 becomes the left child of node 6

Right right type

Figure is right – right type, left – handed operation

The right of left-handed

The figure is right-left. Node 6 is right-handed first, then node 4 is left-handed

About type

The figure is left and right. Node 2 is left-handed first, and node 8 is right-handed.

Code implementation

public class Node {
    int data;
    Node lchild;
    Node rchild;
    int height;

    public Node(int data) {
        this.data = data; }}public class AVLTree {
    private Node root;

    // Record the height of the node
    private int height(Node node) {
        if (node == null) {
            return -1;
        } else {
            returnnode.height; }}// Right, right, left
    private Node L_Rotate(Node node) {
        Node temp;

        // Do the rotation
        temp = node.rchild;
        node.rchild = temp.lchild;
        temp.lchild = node;

        // Recalculate the height
        node.height = Math.max(height(node.lchild), height(node.rchild)) + 1;
        temp.height = Math.max(height(temp.lchild), height(temp.rchild)) + 1;

        return temp;
    }

    // Left - left - right rotation
    private Node R_Rotate(Node node) {
        Node temp;

        // Do the rotation
        temp = node.lchild;
        node.lchild = temp.rchild;
        temp.rchild = node;

        // Recalculate the height
        node.height = Math.max(height(node.lchild), height(node.rchild)) + 1;
        temp.height = Math.max(height(temp.lchild), height(temp.rchild)) + 1;

        return temp;
    }

    // The left/right type rotates first to the left and then to the right
    private Node L_R_Rotate(Node node) {
        // Left-rotate the left child
        node.lchild = L_Rotate(node.lchild);

        // Rotate the node right
        return R_Rotate(node);
    }

    // Right-left advance. right-handed rotation is left-handed
    private Node R_L_Rotate(Node node) {
        // Rotate the right child node
        node.rchild = R_Rotate(node.rchild);

        // Rotate the node left
        return L_Rotate(node);
    }

    public void insert(int data) {
        root = insert(data, root);
    }

    // Insert operations
    private Node insert(int data, Node node) {
        if (node == null) {
            node = new Node(data);
        } else if (data < node.data) {
            // Recursively insert the left child
            node.lchild = insert(data, node.lchild);

            // If the height of the left child is 2 higher than the height of the right child, the rotation is adjusted
            if (height(node.lchild) - height(node.rchild) == 2) {if (data < node.lchild.data) {  / / the left left
                    node = R_Rotate(node);
                } else {   / / typenode = R_L_Rotate(node); }}}else if (data > node.data) {
            // Insert recursively to the right child node
            node.rchild = insert(data, node.rchild);

            // If the height of the right child is 2 higher than the height of the left child, the rotation is adjusted
            if (height(node.rchild) - height(node.lchild) == 2) {
                if (data > node.rchild.data) { / / right right type
                    node = L_Rotate(node);
                } else {  Type/right/leftnode = R_L_Rotate(node); }}}// If data = node.data exists in the tree and does nothing

        node.height = Math.max(height(node.lchild), height(node.rchild)) + 1;
        return node;
    }

    // The AVL tree is traversed in the middle order
    public void inOrder(a) {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if(node ! =null) { inOrder(node.lchild); System.out.println(node.data); inOrder(node.rchild); }}}Copy the code