1. AVL tree: left-right rotation -bite

AVL The definition of a tree

The absolute value of the height difference between the left and right subtrees does not exceed 1 Binary search tree of .
Yes n Nodes , The time complexity is log With n Bottom 2 The logarithmic ;

AVL Insertion of trees

Left spin : Left rotation means that the left subtree of the right subtree of the rotating node becomes its new right subtree , At the same time, the rotation node becomes the left subtree of the previous right subtree
Single rotation at right end : Right rotation means that the right subtree of the left subtree of the rotating node becomes its new left subtree , At the same time, the rotation node becomes the right subtree of the previous left subtree

When to use left-handed , Right hand , Double left and right , Right and left double choice ?
When adding a node to the right subtree of the right subtree of the node to be rotated : left-handed , When on the left subtree of the right subtree of the node to be rotated : Right left double rotation .
When adding nodes to the left subtree of the left subtree of the node to be rotated : Right hand , When on the right subtree of the left subtree of the node to be rotated : Double left and right .

Create a node class :

public class TreeNode {
    
    public int val;
    public int bf;
    public TreeNode left;
    public TreeNode right;
    public TreeNode parent;

    public TreeNode(int val){
    
        this.val = val;
    }
}

Insert elements :

public TreeNode root;// The root node 
    public boolean insert(int val) {
    
        TreeNode node = new TreeNode(val);
        if(root == null) {
    
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
         Give Way node Parent node of node (parent)
        while (cur != null) {
    
            if(cur.val < val) {
    
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val) {
    
                return false;
            }else {
    
                parent = cur;
                cur = cur.left;
            }
        }
        //cur == null
         Judge node, This insert parent Which subtree of .
        if(parent.val < val) {
    
            parent.right = node;
        }else {
    
            parent.left = node;
        }
        //
        node.parent = parent;
        cur = node;
        //  Modification of balance factor 
        while (parent != null) {
    
            // First look at cur yes parent Left or right   The balance factor is ++ still --
            if(cur == parent.right) {
    
                // If it is a right tree , Then the height of the right tree increases   Balance factor ++
                parent.bf++;
            }else {
    
                // If it is a left tree , Then the height of the left tree increases   Balance factor --
                parent.bf--;
            }

            // Check the current balance factor   Is it an absolute value  1 0 -1
            if(parent.bf == 0) {
    
                // It shows that it has been balanced 
                break;
            }else if(parent.bf == 1 || parent.bf == -1) {
    
                // Continue upward to modify the balance factor 
                cur = parent;
                parent = cur.parent;
            }else {
    
                if(parent.bf == 2) {
     // Right tree height -》 You need to lower the height of the right tree 
                    if(cur.bf == 1) {
    
                        // left-handed 
                        rotateLeft(parent);
                    }else {
    
                        //cur.bf == -1
                        // Right left double rotation 
                        rotateRL(parent);
                    }
                }else {
    
                    //parent.bf == -2  Zuo Shugao -》 You need to lower the height of the left tree 
                    if(cur.bf == -1) {
    
                        // Right hand 
                        rotateRight(parent);
                    }else {
    
                        //cur.bf == 1
                        // Double left and right 
                        rotateLR(parent);
                    }
                }
                // The above code is balanced 
                break;
            }
        }
        return true;
    }

Left spin : Left rotation means that the left subtree of the right subtree of the rotating node becomes its new right subtree , At the same time, the rotation node becomes the left subtree of the previous right subtree

    private void rotateLeft(TreeNode parent) {
    
		// Get the right subtree of the left rotation node 
        TreeNode subR = parent.right;
        // Get the left subtree of the right subtree of the left rotation node 
        TreeNode subRL = subR.left;
		// The right subtree of the left-hand node becomes the left subtree of the old right subtree of the left-hand node 
        parent.right = subRL;
        // The left subtree of the old right subtree becomes a left-handed node 
        subR.left = parent;
        // If the left subtree of the current old right subtree is not empty , Then let its parent node point to the left-handed node .
        if(subRL != null) {
    
            subRL.parent = parent;
        }
		// First save the parent node of the left rotation point , So that it points to subR
        TreeNode pParent = parent.parent;
        parent.parent = subR;
		 Determine whether the left rotation node is the root node 
        if(root == parent) {
    
            root = subR;
            root.parent = null;
        }else {
    
        	// Determine which node of the left-handed node is the parent node .
            if(pParent.left == parent) {
    
                pParent.left = subR;
            }else {
    
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        // Adjust the balance factor 
        subR.bf = parent.bf = 0;
    }

Single rotation at right end : Right rotation means that the right subtree of the left subtree of the rotating node becomes its new left subtree , At the same time, the rotation node becomes the right subtree of the previous left subtree

    private void rotateRight(TreeNode parent) {
    

        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;
        // No, subLR
        if(subLR != null) {
    
            subLR.parent = parent;
        }
        // You must first record 
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        // Check   Is it currently the root node 
        if(parent == root) {
    
            root = subL;
            root.parent = null;
        }else {
    
            // Not the root node , Judge whether this subtree is a left subtree or a right subtree 
            if(pParent.left == parent) {
    
                pParent.left = subL;
            }else {
    
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = 0;
        parent.bf = 0;
    }

Double left and right : When adding nodes to the left subtree of the left subtree of the node to be rotated : Right hand , When on the right subtree of the left subtree of the node to be rotated : Double left and right .

    private void rotateLR(TreeNode parent) {
    
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;

        rotateLeft(parent.left);
        rotateRight(parent);
		// from dubLT.bf Value (-1/1) Adjust the balance factor .
        if(bf == -1) {
    
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
    
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }

Right left double rotation : When adding a node to the right subtree of the right subtree of the node to be rotated : left-handed , When on the left subtree of the right subtree of the node to be rotated : Right left double rotation .

    // Right left double rotation 
    private void rotateRL(TreeNode parent) {
    
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateR(parent.right);
        rotateL(parent);

        if(bf == -1){
    
            parent.bf = 0;
            subR.bf = 0;
            subRL.bf = 1;
        }else if(bf == 1){
    
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        }
    }

Judge whether it is AVL Trees

    private int height(TreeNode root) {
    
        if(root == null) return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);

        return leftH > rightH ? leftH+1 : rightH+1;
    }

    public boolean isBalanced(TreeNode root) {
    
        if(root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);

        if(rightH-leftH != root.bf) {
    
            System.out.println(" This node ："+root.val+"  The balance factor is abnormal ");
            return false;
        }

        return Math.abs(leftH-rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

AVL Delete tree ( undetermined )