AVL Tree

Soon is an implementation of an avl tree.

An AVL tree (Adelson-Velskii and Landis), two people, the initials of AVL come from their surnames.

Website to create an animated AVL: https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Is a type of self-balancing binary search tree (BST self balancing). It was invented in 1962 by Soviet computer scientists Adelson-Velskii and Landis.

The height of an AVL tree is always O(log(n)), where n is the number of nodes in the tree.

The idea is to take advantage of the fact that the height is proportional to log(n) and that it is a binary search tree (if both things are true it is an AVL) and we must always maintain that it is AVL, therefore its operations have a cost O(log(n))

In the AVL, each node has a balance factor (BF).

The BF must be kept up to date on each node.

To maintain balance its value at each node can be 0,-1,+1.

If the BF is a value other than -1,0,+1, if it is different in a node, it is said that the tree is unbalanced.

If a node is unbalanced, the tree must be balanced by rotating it and adjusting its value location.

balance factor = right subtree height - left subtree height

if n is a node, it is called left heavy if BF(n) < 0

If n is a node, it is called right heavy if BF(n) >0

If n is a node, it is called balanced if BF(n) = 0

The main purpose of an AVL tree is to maintain a balance between the height of the tree and the number of nodes, allowing search, insertion, and deletion operations to be performed efficiently.

Types of imbalances
There are four types of imbalances in an AVL tree:
Left-left imbalance (LL): The unbalanced node has a left child and the left child also has a left child.
Left-right imbalance (LR): The unbalanced node has a left child and the left child has a right child.
Right-right imbalance (RR): The unbalanced node has a right child and the right child also has a right child.
Right-left imbalance (RL): The unbalanced node has a right child and the right child has a left child.

Rotations

• RRot (right rotation): right rotation
• LRot (left rotation): left rotation

For each type of imbalance, a specific rotation must be performed:

• LL imbalance: Right rotation (RRot) at node. simple balancing.
• LR imbalance: Left rotation (LRot) at node->left followed by a right rotation (RRot) at node. double balance
• RR imbalance: Left rotation (LRot) at node. simple balancing.
• RL imbalance: Right rotation (RRot) at node->right followed by a left rotation (LRot) at node. double balance.

If the highlight looks wrong, it’s a WordPress error.

Examples of types of imbalance in drawings.

The triangles represent tree structures and the round ones are nodes.

example of an imbalance:

and how to balance it

how is it balanced:

Left rotation algorithm in java

public Node leftRotation(Node node) {
if (node == null) {
return null;
}
Node temporary = node.right;
node.right = temporary.left;
temporary.left = node;
node.height = 1 + Math.max(height(node.left), height(node.right));
temporary.height = 1 + Math.max(height(temporary.left), height(temporary.right));
return temporary;
}

an example of left rotation entering node “a” as a parameter.

• What is in yellow is not moved, remains pointing from the same place.
• The blue will be moved, “c” on its left points to “a”, on its right it does not change.
• The green remains pointing from the same place.
• We changed the header of “a” to “c”.
• It’s like pointing to “c” with an invisible arrow and pulling it, only changes the pointer to “f”.
• We only need to update the heights of “a” and “c”, not “f”, the rest have their correct height.

Right rotation algorithm in java

public Node rightRotation(Node node) {
if (node == null) {
return null;
}
Node temporary = node.right;
node.left = temporary.right;
temporary.right = node; 
node.height = 1 + Math.max(height(node.left), height(node.right));
temporary.height = 1 + Math.max(height(temporary.left),
height(temporary.right));
return temporary;
}

Height of a Node

    public int height(Node<T> node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + Math.max(height(node.getLeftNode()), height(node.getRightNode()));
        }
    }

Balance factor (FE)

public void updateBalanceFactor() {

int leftHeight = height(this.leftNode);

int rightHeight = height(this.rightNode);

this.balanceFactor = rightHeight - leftHeight;

}

Here is how an AVL tree works:

Properties of AVL tree

• It is a binary search tree, that is, for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node.
• The height of the left and right subtrees of each node differs by at most 1.

Operations on an AVL tree

• Search: An element is searched for in the tree in a similar way to a binary search tree.
• Insertion: A new element is inserted into the tree. If the insertion causes an imbalance in the tree, rotations are performed to restore the balance.
• Deletion: An element is removed from the tree. If the deletion causes an imbalance in the tree, rotations are performed to restore the balance.

Rotations on an AVL tree

To maintain the balance of the tree, rotations are performed when an element is inserted or deleted.

There are four types of rotations:

• Left rotation: The tree is rotated to the left when the right subtree of a node is too tall.
• Right rotation: The tree is rotated to the right when the left subtree of a node is too tall.
• Left-right rotation: The tree is rotated left and then right when the right subtree of a node is too tall and the left subtree of the right node is too tall.
• Right-left rotation: The tree is rotated right and then left when the left subtree of a node is too tall and the right subtree of the left node is too tall.

Advantages and disadvantages of AVL trees

Advantages:

• Efficient search: AVL trees allow efficient searches, with a time complexity of O(log n).
• Efficient insertion and deletion: AVL trees allow efficient insertions and deletions, with a time complexity of O(log n).

Disadvantages:

• Additional complexity: AVL trees require additional complexity to keep the tree balanced, which can increase the execution time in some cases.
• Additional memory requirements: AVL trees require additional memory to store the height of each node and perform the necessary rotations.

The binary trees were graphed with “Graphviz Online”: https://dreampuf.github.io/GraphvizOnline/

Example of how to draw the LL binary tree

digraph G {

  subgraph cluster_0 {
    style=filled;
    color=lightgrey;
    node [style=filled,color=white];
    a5 [shape=triangle];
    a6 [shape=triangle];
    a7 [shape=triangle];
    
    a0 [color=red,label="-2"];
    a3 [color=red,label="+1"];
    
    a4 [color=red];
    
    a0  -> a3 [label="L",tailport=w, headport=n];
    a0  -> a2 [label="R",tailport=e, headport=n];
    a3  -> a4 [label="L",tailport=w, headport=n];
    a3  -> a5 [label="R",tailport=e, headport=n];
    a2  -> a6 [label="L",tailport=w, headport=n];
    a2  -> a7 [label="R",tailport=e, headport=n];
    label = "tree binary LL";
  }


}