Data Structures | AVL

​ In this article we talk about AVL tree.

​ AVL is self-balanced tree, where for each node difference between height of left and right subtrees no more than 1.

​ Whenever you insert a node into tree, you always rebalance tree. Asymptotic complexity of insert, search, and delete operations - logarithmic complexity and linear complexity for space complexity. Let’s define balance property of node. Balance property equals difference of height of left and right subtrees. If |difference| <= 1, then the node is said balanced, otherwise not balanced.

​ Whenever we peform insert operation, we need always check on balance property(of new value’s ancestor). If if not balanced, then rebalance tree by rotating operation.

There are 4 rotations exists:

  • Left rotation
  • Right rotation
  • Left-Right rotation
  • Right-Left rotation

The last two is compositions of first two(with different orders).

Example of implementation of insert operation: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package play;

public class AVL {
    private Node root;
    private int height(Node node) {
        if (node == null) return 0;
        return node.height;
    }
    int balance(Node node) {
        if (node == null) return 0;
        return height(node.left) - height(node.right);
    } 
    private Node leftRotate(Node node) {
        Node retNode = node.right;
        Node leftNode = retNode.left;
        retNode.left = node;
        node.right = leftNode;
        return retNode;
    }
    private Node rightRotate(Node node) {
        Node retNode = node.left;
        Node rightNode = retNode.right;
        retNode.right = node;
        node.left = rightNode;
        return retNode;
    }
    public void insert(int val) {
        root = insertRecursively(root, val);
    }
    private Node insertRecursively(Node node, int val) {
        if (node == null) return new Node(val);
        if (node.val < val) {
            node.right = insertRecursively(node.right, val);
        } else if (node.val > val) {
            node.left = insertRecursively(node.left, val);
        } else {
            return node;
        }
        node.height = 1 + Math.max(height(node.left), height(node.right));
        int bal = balance(node);
        if (bal > 1 && val < node.left.val) {
            return rightRotate(node);
        }
        if (bal < -1 && val > node.right.val) {
            return leftRotate(node);
        }
        if (bal > 1 && val > node.left.val) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (bal < - 1 && val < node.right.val) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }
    public void inorder() {
        inorderRecursively(root);
    }
    private void inorderRecursively(Node node) {
        if (node == null) return;
        inorderRecursively(node.left);
        System.out.println(node.val);
        inorderRecursively(node.right);
    }
}