Detailed explanation of balanced binary tree is easy to understand

Balanced binary trees （AVL）

Please understand before reading Binary search tree

Golang The communication group pays attention to official account Deng Jiawen Jarvan

Balanced binary tree definition ： The height difference of any node's subtree is less than or equal to 1

1. Why use 「 Balanced binary trees 」

Binary tree can improve the efficiency of query O(logn), But when you insert {1,2,3,4,5,6} This kind of data , Your binary tree is like a 「 Linked list 」 equally , Search efficiency becomes O(n)

So in 1962 year , A family name AV Big guy （G. M. Adelson-Velsky） And a last name L Big guy （ Evgenii Landis） Put forward 「 Balanced binary trees 」（AVL） .

So insert {1,2,3,4,5,6} The results of this data are shown in the figure below ：

2. Judge 「 Balanced binary trees 」

Judge 「 Balanced binary trees 」 Of 2 Conditions ：

• 1. yes 「 Binary sort tree 」
• 2. The left or right subtree of any node is 「 Balanced binary trees 」（ The height difference between left and right is less than or equal to 1）

（1） The picture below is not 「 Balanced binary trees 」 Because it's not 「 Binary sort tree 」 In violation of 1 Conditions

（2） The picture below is not 「 Balanced binary trees 」 Because the height difference of node subtree is greater than 1 Illegal article 2 Conditions

（3） The picture below is 「 Balanced binary trees 」 Because it conforms to 1、2 Conditions

3. Relevant concepts

3.1 Balance factor BF

Definition ： Height difference between left subtree and right subtree

Calculation ： Height of left subtree - The value of the height of the right subtree

Alias ： abbreviation BF（Balance Factor instead of Boy Friend）

Generally speaking BF The absolute value of is greater than 1,, A balanced tree is a binary tree , need 「 rotate 」 correct

3.2 Minimum unbalanced subtree

The closest... To the insertion node , also BF The absolute value of is greater than 1 The node of is the subtree of the root node .

「 rotate 」 Correction only needs correction 「 Minimum unbalanced subtree 」 that will do

An example is shown in the figure below ：

4. Two rotation modes

2 Kind of 「 rotate 」 The way ：

1. left-handed
   • The old root node is the left subtree of the new root node
   • The left subtree of the new root node （ If there is ） Is the right subtree of the old root node
2. Right hand ：
   • The old root node is the right subtree of the new root node
   • The right subtree of the new root node （ If there is ） Is the left subtree of the old root node

4 Kind of 「 rotate 」 Correction type ：

1. LL type ： Insert the left subtree of the left child , Right hand
2. RR type ： Insert the right subtree of the right child , left-handed
3. LR type ： Insert the right subtree of the left child , First left , Turn right again
4. RL type ： Insert the left subtree of the right child , First right , Turn left again

4.1 LL Type imbalance 「 Right hand 」

Third node 「1」 Inserted When ,BF(3) = 2,BF(2) = 1LL Type imbalance , Right hand , The root node rotates clockwise

（1） Minimum unbalanced subtree 「 Right hand 」

Right hand

• Old root node （ node 3） For the new root node （ node 2） The right subtree
• Of the new root node Right subtree （ If there is ） Is the left subtree of the old root node

4.2 RR Type imbalance 「 left-handed 」

Third node 「3」 Inserted When ,BF(1)=-2 BF(2)=-1,RR Type imbalance , left-handed , The root node rotates counterclockwise

（1） The minimum unbalanced subtree is left-handed

left-handed

• Old root node （ node 1） For the new root node （ node 2） The left subtree
• The left subtree of the new root node （ If there is ） Is the right subtree of the old root node

4.3 LR type

Third node 「3」 Inserted When ,BF(3)=2 BF(1)=-1LR Type imbalance , First 「 left-handed 」 Again 「 Right hand 」

（1） Minimum unbalanced subtree left subtree {2,1} First left

left-handed

• Old root node （ node 1） For the new root node （ node 2） The left subtree
• The left subtree of the new root node （ If there is ） Is the right subtree of the old root node

（2） Minimum unbalanced subtree {3,2,1} Turn right again

Right hand

• Old root node （ node 3） For the new root node （ node 2） The right subtree
• Of the new root node Right subtree （ If there is ） Is the left subtree of the old root node

4.4 RL type

Third node 「1」 Inserted When ,BF(1)=-2 BF(3)=1RL Type imbalance , First 「 Right hand 」 Again 「 left-handed 」

（1） Minimum unbalanced subtree root node right subtree {3,2} First right

Right hand

• Old root node （ node 3） For the new root node （ node 2） The right subtree
• Of the new root node Right subtree （ If there is ） Is the left subtree of the old root node

（2） Minimum unbalanced subtree {1,2,3} Turn left again （L）

left-handed

• Old root node （ node 1） For the new root node （ node 2） The left subtree
• The left subtree of the new root node （ If there is ） Is the right subtree of the old root node

5. example

So let's start with {3,2,1,4,5,6,7,10,9,8} Practice just for example 4 There are two ways to insert

（1） Insert... In turn 3、2、1 Insert the third point 1 When BF(3)=2 BF(2)=1,LL Type imbalance .

For the minimum unbalanced tree {3,2,1} Conduct 「 Right hand 」

Right hand ：

• Old root node （ node 3） For the new root node （ node 2） The right subtree
• New root node （ node 2） The right subtree （ There is no right subtree ） Is the left subtree of the old root node

（2） Insert... In turn 4 ,5 Insert 5 A.m. BF(3) = -2 BF(4)=-1,RR Type imbalance

For the minimum unbalanced tree {3,4,5} Conduct 「 left-handed 」

left-handed ：

• Old root node （ node 3） For the new root node （ node 4） The left subtree
• New root node （ node 4） The left subtree （ There is no left subtree ） Is the right subtree of the old root node

（3） Insert 4 ,5 Insert 5 A.m. BF(2)=-2 BF(4)=-1 ,RR Type imbalance For the minimum unbalanced tree 「 left-handed 」

left-handed ：

• Old root node （ node 2） For the new root node （ node 4） The left subtree
• New root node （ node 4） Of The left subtree （ node 3） Is the right subtree of the old root node

New root node （ node 4） The left subtree （ node 3） Is the right subtree of the old root node

（4） Insert 7 Node time BF(5)=-2, BF(6)=-1 ,RR Type imbalance , For the minimum unbalanced tree Conduct 「 left-handed 」

left-handed ：

• Old root node （ node 5） For the new root node （ node 6） The left subtree
• The left subtree of the new root node （ Nothing here ） Is the right subtree of the old root node

（5） Insert... In turn 10 ,9 . Insert 9 A.m. BF(10) = 1,BF(7) = -2 ,RL Type imbalance , Right first 「 Right hand 」 Again 「 left-handed 」

Right subtree first 「 Right hand 」

The right subtree of the minimum unbalanced subtree {10,9} First right ：

• Old root node （ node 10） For the new root node （ node 9） The right subtree
• New root node （ node 9） The right subtree （ There is no right subtree ） Is the left subtree of the old root node

The minimum unbalanced subtree is then left-handed ：

• Old root node （ node 7） For the new root node （ node 9） The left subtree
• New root node （ node 9） The left subtree （ There is no left subtree ） Is the right subtree of the old root node

（6） Finally, insert the node 8 ,BF(6)=-2 BF(9)=1,RL Type imbalance , First 「 Right hand 」 Again 「 left-handed 」

The right subtree of the minimum unbalanced subtree {9,7,10,8} First 「 Right hand 」

Right hand ：

• Old root node （ node 9 {9,10}） For the new root node （ node 7） The right subtree
• New root node （ node 7） The right subtree （ Here is node 8） For the old root node （ node 9） The left subtree

Minimum unbalanced subtree {6,5,7,9,8,10} Again 「 left-handed 」

left-handed ：

• Old root node （ node 6 {6,5} ） For the new root node （ node 7） The left subtree
• The left subtree of the new root node （ Nothing here ） Is the right subtree of the old root node

Left rotation end

Program end

6. Code implementation

6.1 Define the node

public class AVLNode {
    
    /**  data  **/
    public int data;
    /**  Relative height  **/
    public int height;
    /**  Parent node  **/
    public AVLNode parent;
    /**  The left subtree  **/
    public AVLNode left;
    /**  Right subtree  **/
    public AVLNode right;
    public AVLNode(int data) {
    
        this.data = data;
        this.height = 1;
    }
}

6.2 Calculate the height

The node height is equal to the maximum height of the left subtree and the right subtree + 1

/**  Through the height of subtree   Calculate the height  **/
private int calcHeight(AVLNode root) {
    
    if (root.left == null && root.right == null) {
    
        return 1;
    }
    else if (root.right == null) {
    
        return root.left.height + 1;
    } else if (root.left == null) {
    
        return root.right.height + 1;
    }else {
    
        return root.left.height > root.right.height ? root.left.height + 1 : root.right.height + 1;
    }
}

6.3 Calculation BF

BF（ Balance factor ） The value of is ： Height of left subtree - Height of right subtree

private int calcBF(AVLNode root) {
    
    if (root == null){
    
        return 0;
    }
    else if (root.left == null && root.right == null) {
    
        return 0;
    }
    else if (root.right == null) {
    
        return root.left.height ;
    } else if (root.left == null) {
    
        return - root.right.height;
    }else {
    
        return root.left.height - root.right.height;
    }
}

6.4 rotate

2 Kind of 「 rotate 」 The way ：

1. left-handed
   • The old root node is the left subtree of the new root node
   • The left subtree of the new root node （ If there is ） Is the right subtree of the old root node
2. Right hand ：
   • The old root node is the right subtree of the new root node
   • The right subtree of the new root node （ If there is ） Is the left subtree of the old root node

Focus on understanding ： After rotation, you need to refresh the height

Height changes only ： oldRoot and newRoot

But the height of their subtrees is constant （ It's critical ）

We can use them Calculate the height of subtrees

Using constant factors to calculate changing factors is a good idea

public AVLNode leftRotate(AVLNode root) {
    
    AVLNode oldRoot = root;
    AVLNode newRoot = root.right;
    AVLNode parent = root.parent;
    //1.newRoot  Replace  oldRoot  Location 
    if (null != parent ) {
    
        if (oldRoot.parent.data > oldRoot.data) {
    
            parent.left = newRoot;
        }else  {
    
            parent.right = newRoot;
        }
    }
    newRoot.parent = parent;
    //2. Reassemble  oldRoot ( take  newRoot  The left subtree   to  oldRoot  The right subtree )
    oldRoot.right = newRoot.left;
    if (newRoot.left != null) {
    
        newRoot.left.parent = oldRoot;
    }
    //3. oldRoot  by  newRoot  The left subtree 
    newRoot.left = oldRoot;
    oldRoot.parent = newRoot;
    // Refresh height 
    oldRoot.height = calcHeight(oldRoot);
    newRoot.height = calcHeight(newRoot);
    return newRoot;
}


public AVLNode rightRotate(AVLNode root) {
    
    AVLNode oldRoot = root;
    AVLNode newRoot = root.left;
    AVLNode parent = root.parent;
    //1.newRoot  Replace  oldRoot  Location 
    if (null != parent ) {
    
        if (oldRoot.parent.data > oldRoot.data) {
    
            parent.left = newRoot;
        }else {
    
            parent.right = newRoot;
        }
    }
    newRoot.parent = parent;
    //2. Reassemble  oldRoot ( take  newRoot  The right subtree   to  oldRoot  The left subtree )
    oldRoot.left = newRoot.right;
    if (newRoot.right != null) {
    
        newRoot.right.parent = oldRoot;
    }
    //3. oldRoot  by  newRoot  The left subtree 
    newRoot.right = oldRoot;
    oldRoot.parent = newRoot;
    // Refresh height 
    oldRoot.height = calcHeight(oldRoot);
    newRoot.height = calcHeight(newRoot);
    return newRoot;
}

6.5 Insert （ Master code ）

The insert

• Recursively insert new nodes
• Refresh height
• Rotate and refresh the height again

public class ALVTree {
    
    AVLNode root;
    public void insert(int data) {
    
        if (null == this.root) {
    
            this.root = new AVLNode(data);
            return;
        }
        this.root = insert(this.root, data);
    }
    public AVLNode insert(AVLNode root, int data) {
    
        // Insert the left subtree 
        if (data < root.data) {
    
            if (null == root.left) {
    
                root.left = new AVLNode(data);
                root.left.parent = root;
            }else {
    
                insert(root.left,data);
            }
        }
        // Insert right subtree 
        else if (data > root.data) {
    
            if (null == root.right) {
    
                root.right = new AVLNode(data);
                root.right.parent = root;
            } else {
    
                insert(root.right,data);
            }
        }
        // Refresh height 
        root.height = calcHeight(root);
        // rotate 
        //1. LL  type   Right rotation 
        if (calcBF(root) == 2){
    
            //2. LR  type   First left rotation 
            if (calcBF(root.left) == -1) {
    
                root.left = leftRotate(root.left);
            }
            root = rightRotate(root);
        }
        //3. RR type   Left rotation 
        if (calcBF(root) == -2){
    
            //4. RL  type   First right rotation 
            if (calcBF(root.right)== 1) {
    
                root.right = rightRotate(root.right);
            }
            root = leftRotate(root);
        }

        return root;
    }
    public AVLNode leftRotate(AVLNode root) {
    
        AVLNode oldRoot = root;
        AVLNode newRoot = root.right;
        AVLNode parent = root.parent;
        //1.newRoot  Replace  oldRoot  Location 
        if (null != parent ) {
    
            if (oldRoot.parent.data > oldRoot.data) {
    
                parent.left = newRoot;
            }else  {
    
                parent.right = newRoot;
            }
        }
        newRoot.parent = parent;
        //2. Reassemble  oldRoot ( take  newRoot  The left subtree   to  oldRoot  The right subtree )
        oldRoot.right = newRoot.left;
        if (newRoot.left != null) {
    
            newRoot.left.parent = oldRoot;
        }
        //3. oldRoot  by  newRoot  The left subtree 
        newRoot.left = oldRoot;
        oldRoot.parent = newRoot;
        // Refresh height 
        oldRoot.height = calcHeight(oldRoot);
        newRoot.height = calcHeight(newRoot);
        return newRoot;
    }


    public AVLNode rightRotate(AVLNode root) {
    
        AVLNode oldRoot = root;
        AVLNode newRoot = root.left;
        AVLNode parent = root.parent;
        //1.newRoot  Replace  oldRoot  Location 
        if (null != parent ) {
    
            if (oldRoot.parent.data > oldRoot.data) {
    
                parent.left = newRoot;
            }else {
    
                parent.right = newRoot;
            }
        }
        newRoot.parent = parent;
        //2. Reassemble  oldRoot ( take  newRoot  The right subtree   to  oldRoot  The left subtree )
        oldRoot.left = newRoot.right;
        if (newRoot.right != null) {
    
            newRoot.right.parent = oldRoot;
        }
        //3. oldRoot  by  newRoot  The left subtree 
        newRoot.right = oldRoot;
        oldRoot.parent = newRoot;
        // Refresh height 
        oldRoot.height = calcHeight(oldRoot);
        newRoot.height = calcHeight(newRoot);
        return newRoot;
    }
    /**  Through the height of subtree   Calculate the height  **/
    private int calcHeight(AVLNode root) {
    
        if (root.left == null && root.right == null) {
    
            return 1;
        }
        else if (root.right == null) {
    
            return root.left.height + 1;
        } else if (root.left == null) {
    
            return root.right.height + 1;
        }else {
    
            return root.left.height > root.right.height ? root.left.height + 1 : root.right.height + 1;
        }
    }
    private int calcBF(AVLNode root) {
    
        if (root == null){
    
            return 0;
        }
        else if (root.left == null && root.right == null) {
    
            return 0;
        }
        else if (root.right == null) {
    
            return root.left.height ;
        } else if (root.left == null) {
    
            return - root.right.height;
        }else {
    
            return root.left.height - root.right.height;
        }
    }
}

test

public static void main(String[] args) {
    
    ALVTree tree = new ALVTree();
    tree.insert(3);
    tree.insert(2);
    tree.insert(1);
    tree.insert(4);
    tree.insert(5);
    tree.insert(6);
    tree.insert(7);
    tree.insert(10);
    tree.insert(9);
    tree.insert(8);
    // Traverse the output 
    innerTraverse(tree.root);
}
private static void innerTraverse(AVLNode root) {
    
    if (root == null) {
    
        return;
    }
    innerTraverse(root.left);
    System.out.println(root.data + " height:"+root.height);
    innerTraverse(root.right);
}

Output

1 height:1
2 height:2
3 height:1
4 height:4
5 height:1
6 height:2
7 height:3
8 height:1
9 height:2
10 height:1