AVL tree

The AVL tree is named after its inventors G.M. Adelson-Velsky and E.M. Landis.

It is the first self-balancing binary search tree, also known as the highly balanced tree.

Compared with “binary search tree”, it is characterized that the maximum difference in height between two subtrees of any node in AVL tree is 1.

example

Balance of AVL tree

5, 2, 7, 1, 3, 6, 9Copy the code

Unbalanced tree:

One, two, three, four, five, six, sevenCopy the code

Balance factor

The height (depth) difference between the left subtree and the right subtree of a node is the Balance Factor (BF) of the node.

The equilibrium factor for all nodes in a balanced binary tree can only be -1, 0 or 1.

If the absolute value of a node’s balance factor is greater than 1, the tree is not a balanced binary tree.

In order to conveniently calculate the balance factor of each node, we can assign height to each node, indicating the height of this node.

implementation

Node definition

/** * Internal node **@paramThe < V > generic *@since0.0.5 * /
private static class Node<V> {
    /** ** left node **@since0.0.5 * /
    private Node<V> left;
    /** ** right node **@since0.0.5 * /
    private Node<V> right;
    /** * data **@since0.0.5 * /
    private V data;
    /** * Height of the current element **@since0.0.5 * /
    private int height;
    public Node(V data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.height = 1; }}Copy the code

After a lot of practice, it feels more natural to define an internal class.

If properties are manipulated through external getters/setters, the code becomes less intuitive.

The class definition

This is the same as BST, we inherit from ISortTree interface.

All elements must be subclasses of Comparable.

/** ** AVL balance tree **@authorThe old horse shouts the west wind@since0.0.5 * /
public class AvlTree<V extends Comparable<? super V>> implements ISortTree<V> {
	/** * Root node **@since0.0.5 * /
    private Node<V> root;

    /** * The size of the entire tree **@since0.0.5 * /
    private int size;


    /** * constructor * <p> * initializes an empty tree **@since0.0.5 * /
    public AvlTree(a) {
        this.root = null;
        this.size = 0; }}Copy the code

Whether the balance

Directly according to the altimeter difference between the left and right nodes, here a new concept of height, so that the implementation becomes very simple.

/** * Get the balance factor of the node *@param node
 * @return* /
private int getBalanceFactor(Node node){
	if(node==null) {return 0;
	}
	return getHeight(node.left)-getHeight(node.right);
}

// Determine whether the tree is a balanced binary tree
public boolean isBalanced(a){
	return isBalanced(root);
}

private boolean isBalanced(Node node){
	if(node==null) {return true;
	}
	int balanceFactory = Math.abs(getBalanceFactor(node));
	if(balanceFactory>1) {return false;
	}
	return isBalanced(node.left)&&isBalanced(node.right);
}

/** * Gets the height of the current node **@paramThe node node *@returnHighly *@since0.0.5 * /
private int getHeight(Node<V> node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}
Copy the code

Add a node

Adding nodes to a balanced binary tree is likely to cause the tree to become unbalanced, so we need to maintain the balance after each node insertion.

Remember: everything we do is to maintain the balance of the tree.

Once you understand the following four scenarios, you understand the AVL tree.

There are four cases of node insertion that damage the balance:

LL (right-handed)

Insert a new node into the left child of the left subtree (L), resulting in an imbalance. In this case, dextral operation is required.

[image upload failed…(image-9bb1BC-1607243267564)]

Let’s abstract this out and get the following:

The code implementation is as follows:

/** * dextral **@since0.0.5 * /
private Node<V> rightRotate(Node<V> y) {
    Node<V> x = y.left;
    Node<V> t3 = x.right;
    x.right = y;
    y.left = t3;
    / / update the height
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

	// Update the root node
    if(y == root) {
        this.root = x;
    }
    return x;
}
Copy the code

Ps: After the self-test, it is necessary to update the root node, otherwise it will lead to the subsequent traversal of the root node disorder.

RR (left rotation)

This is similar to LL, but in the opposite direction.

Let’s abstract this out and get the following:

The code implementation is as follows:

/** * left rotation **@since0.0.5 * /
private Node<V> leftRotate(Node<V> y) {
    Node<V> x = y.right;
    Node<V> t3 = x.left;
    x.left = y;
    y.right = t3;
    / / update the height
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

	// Update the root node
    if(y == root) {
        this.root = x;
    }
    return x;
}
Copy the code

LR

The scenario is as follows:

Let’s abstract this out and get the following:

RL

The scenario is as follows:

[image upload failed…(image-499a82-1607243267564)]

Let’s abstract this out and get the following:

Complete add implementation

You can compare the following code to the above four scenarios.

@Override
public void add(V data) {
    this.root = add(root, data);
}

/** * inserts the element **@paramThe node node *@paramV The element to be inserted *@returnResults *@since0.0.5 * /
private Node<V> add(Node<V> node, V v) {
    if (node == null) {
        size++;
        return new Node<>(v);
    }
    if (v.compareTo(node.data) < 0) {
        node.left = add(node.left, v);
    } else if (v.compareTo(node.data) > 0) {
        node.right = add(node.right, v);
    }
    / / update the height
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    // Calculate the balance factor
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor > 1 && getBalanceFactor(node.left) > 0) {
        / / right LL
        return rightRotate(node);
    }
    if (balanceFactor < -1 && getBalanceFactor(node.right) < 0) {
        / / left-handed RR
        return leftRotate(node);
    }
    //LR
    if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    //RL
    if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}
Copy the code

Delete operation

Before deleting AVL tree nodes, we need to know the node deletion operation of binary search tree. Different from binary search tree node deletion, we need to carry out balanced maintenance operation after deleting AVL tree nodes.

@Override
public boolean remove(V data) {
    Node<V> node = getNode(root, data);
    if(node ! =null) {
        root = remove(root, data);
        return true;
    }
    return false;
}
/** * returns the key node ** in the binary search tree with node as the root node@paramThe node node *@paramElements of v *@returnResults *@since0.0.5 * /
private Node<V> getNode(Node<V> node, V v) {
    if (node == null) {
        return null;
    }
    if (v.equals(node.data)) {
        return node;
    } else if (v.compareTo(node.data) < 0) {
        return getNode(node.left, v);
    } else {
        returngetNode(node.right, v); }}/** * returns the minimum value of the binary search tree rooted in node * <p> * ps: in effect, the leftmost subtree **@paramThe node node *@returnResults *@since0.0.5 * /
private Node<V> getMiniNode(Node<V> node) {
    if (node.left == null) {
        return node;
    }
    return getMiniNode(node.left);
}
/** * deletes an element **@paramThe node node *@paramElements of v *@returnResults the * /
private Node<V> remove(Node<V> node, V v) {
    if (node == null) {
        return null;
    }
    Node<V> retNode;
    if (v.compareTo(node.data) < 0) {
        node.left = remove(node.left, v);
        retNode = node;
    } else if (v.compareTo(node.data) > 0) {
        node.right = remove(node.right, v);
        retNode = node;
    } else {   // e.compareTo(node.e) == 0
        // The left subtree of the node to be deleted is empty
        if (node.left == null) {
            Node<V> rightNode = node.right;
            node.right = null;
            size--;
            retNode = rightNode;
        }
        // The right subtree of the node to be deleted is empty
        else if (node.right == null) {
            Node<V> leftNode = node.left;
            node.left = null;
            size--;
            retNode = leftNode;
        } else {
            // The left and right subtrees of the node to be deleted are not empty
            // Find the smallest node larger than the node to be deleted, that is, the smallest node in the right subtree of the node to be deleted
            // Replace the node to be deleted with this node
            Node<V> successor = getMiniNode(node.right);
            successor.right = remove(node.right, successor.data);
            successor.left = node.left;
            node.left = node.right = null; retNode = successor; }}if (retNode == null) {
        return null;
    }
    // Maintain balance
    / / update the height
    retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
    // Calculate the balance factor
    int balanceFactor = getBalanceFactor(retNode);
    if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
        / / right LL
        return rightRotate(retNode);
    }
    if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
        / / left-handed RR
        return leftRotate(retNode);
    }
    //LR
    if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
        node.left = leftRotate(retNode.left);
        return rightRotate(retNode);
    }
    //RL
    if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
        node.right = rightRotate(retNode.right);
        return leftRotate(retNode);
    }
    return node;
}
Copy the code

test

The preparatory work

To make it easier to visualize, let’s print out the tree before and after the left/right execution.

/** * dextral **@since0.0.5 * /
private Node<V> rightRotate(Node<V> y) {
    System.out.println("Right hand before execution:");
    print();

    Node<V> x = y.left;
    Node<V> t3 = x.right;
    y.left = t3;
    x.right = y;
    / / update the height
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    // Update the root node
    if(y == root) {
        this.root = x;
    }

    System.out.println("After right-handed execution:");
    print();
    return x;
}

/** * left rotation **@since0.0.5 * /
private Node<V> leftRotate(Node<V> y) {
    System.out.println("Before left-handed execution:");
    print();

    Node<V> x = y.right;
    Node<V> t3 = x.left;
    x.left = y;
    y.right = t3;
    / / update the height
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
    // Update the root node
    if(y == root) {
        this.root = x;
    }

    System.out.println("After left-handed execution:");
    print();
    return x;
}
Copy the code

test

Ll – Right-handed scene

/** * ll- dextral test */
@Test
public void llTest(a) {
    AvlTree<Integer> avlTree = new AvlTree<>();
    avlTree.add(3);
    avlTree.add(2);
    avlTree.add(1);
}
Copy the code

The log is as follows:

Before dextral execution: 3 2 1 After dextral execution: 2 1 3Copy the code

Rr – Left-handed test

/** * rr- left rotation test */
@Test
public void rrTest(a) {
    AvlTree<Integer> avlTree = new AvlTree<>();
    avlTree.add(1);
    avlTree.add(2);
    avlTree.add(3);
}
Copy the code

The log is as follows:

Before left-handed execution: 1 2 3 After left-handed execution: 2 1 3Copy the code

LR- Left-right rotation test

/** * LR - left + right test */
@Test
public void lrTest(a) {
    AvlTree<Integer> avlTree = new AvlTree<>();
    avlTree.add(3);
    avlTree.add(1);
    avlTree.add(2);
}
Copy the code

The log is as follows:

Before left-handed execution: 3 1 2 After left-handed execution: 3 1 2 Before right-handed execution: 3 2 1 after right-handed execution: 2 1 3Copy the code

So you can see that we’re doing left rotation first, let’s program it in ll form.

RL- Right – left – handed test

/** * rL - rL + rL test */
@Test
public void rlTest(a) {
    AvlTree<Integer> avlTree = new AvlTree<>();
    avlTree.add(1);
    avlTree.add(3);
    avlTree.add(2);
}
Copy the code

The log is as follows:

Before right-handed execution: 1 3 2 After right-handed execution: 1 3 2 Before left-handed execution: 1 2 3 After left-handed execution: 2 1 3Copy the code

First turn right to rr, then turn left.

summary

Hope you found this article helpful, and if you have any other ideas, please share them in the comments section.

All geeks’ likes, favorites and forwarding are the biggest motivation for Lao Ma to continue writing!

Of course, there are many ways to implement a balanced tree, so in the next video we’ll look at the famous red-black tree.