My IT Utilities

AVL tree

Start from a random AVL tree and insert, search or delete values step by step: see each node's balance factor, the LL, RR, LR and RL rotations, its array form and the C++ code highlighted.

Everything is simulated in this browser; nothing is sent to any server.

No steps

No steps

AVL tree

Array index · Balance factor

60[0]+145[1]+185[2]+167[5]018[3]-153[4]028[8]0

Array form

The children of index i are at 2i+1 and 2i+2.

  • Unrelated
  • Already passed
  • Being compared
  • Found
  • New
  • To delete
  • Successor
  • Unbalanced
  • Pivot

No steps

Code

#include <iostream>
#include <algorithm>
using namespace std;
class Node { // A node holds its value and pointers to its two children
private: // Private attributes: only the methods touch them
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
int height(Node* n) { // Height: a leaf is 1 and an empty spot (nullptr) is 0
if (n == nullptr) return 0;
return 1 + max(height(n->getLeft()), height(n->getRight()));
}
int balanceFactor(Node* n) { // Balance factor: left height minus right height
return height(n->getLeft()) - height(n->getRight());
}
Node* rotateRight(Node* y) { // Single right rotation: the left child x goes up and y goes down
Node* x = y->getLeft();
y->setLeft(x->getRight());
x->setRight(y);
return x;
}
Node* rotateLeft(Node* x) { // Single left rotation: the right child y goes up and x goes down
Node* y = x->getRight();
x->setRight(y->getLeft());
y->setLeft(x);
return y;
}
Node* rebalance(Node* n) { // Returns the root of the subtree, balanced
int bf = balanceFactor(n); // The node's balance factor is computed
if (bf > 1) { // Left heavy. If the left child is not right heavy this is the LL case
if (balanceFactor(n->getLeft()) < 0) // The left child is right heavy: LR case, rotate left first
n->setLeft(rotateLeft(n->getLeft())); // First rotation of the LR case
return rotateRight(n); // Right rotation: solves LL and the second half of LR
}
if (bf < -1) { // Right heavy. If the right child is not left heavy this is the RR case
if (balanceFactor(n->getRight()) > 0) // The right child is left heavy: RL case, rotate right first
n->setRight(rotateRight(n->getRight())); // First rotation of the RL case
return rotateLeft(n); // Left rotation: solves RR and the second half of RL
}
return n; // The factor is between -1 and 1: no rotation needed
}
Node* insert(Node* root, int v) { // Inserts v into the AVL tree and returns the root
if (root == nullptr) // Empty spot: the new node goes here
return new Node(v); // Creates the new node
if (v < root->getValue()) // Smaller values go left and larger ones go right
root->setLeft(insert(root->getLeft(), v)); // Goes down the left subtree
else
root->setRight(insert(root->getRight(), v)); // Goes down the right subtree
return rebalance(root); // On the way back from each call the node's balance is checked
}
int main() {
Node* root = buildTree(); // The tree shown, already built
root = insert(root, v); // First call, from main
return 0; // End of the operation
}

This tool starts from a random AVL tree, a binary search tree that stays balanced, and lets you change it by hand: type a value from 1 to 99 and press Insert, Search or Delete. Each node shows its balance factor, the height difference between its subtrees, and its index in the array. When a node reaches factor 2 or -2, the animation marks it and applies the right rotation: LL, RR, LR or RL. Below, the same tree appears as an array and the C++ code highlights the line being run. Everything is simulated in your browser.

How to use it

  1. Adjust the tree size with the slider or press Generate new tree to change the starting point.
  2. Type a value from 1 to 99 and press Insert, Search or Delete; the animation starts by itself.
  3. Watch the balance factor under each node and the rotation applied when it reaches 2 or -2.
  4. Step forward or back, and compare the tree with its array form and with the highlighted C++ line.

Frequently asked questions

What is an AVL tree and what does it guarantee?
It is a binary search tree that rebalances itself: at every node, the difference between the height of the left subtree and the right one is at most 1. That difference is called the balance factor and is -1, 0 or 1 in a valid AVL. Because of this, the height grows logarithmically with the number of nodes.
What are the four rotation cases and when is each one used?
If a node ends up with factor 2 and its left child is left heavy, it is the LL case and a single right rotation is enough. If the child is right heavy, it is LR: the child is rotated left and then the node is rotated right. With factor -2 it is symmetric: RR is solved with a single left rotation, and RL with a right rotation of the child followed by a left rotation.
How much do insert, search and delete cost compared with a BST?
In an AVL all three operations take logarithmic time in the worst case, because the height never blows up. In a plain BST the cost depends on the height, which can become linear if values are inserted in order and the tree degenerates into a list. In exchange, the AVL performs some rotations when inserting or deleting.
How is an AVL stored in an array and what is the index above each node?
In heap form: the root goes at index 0 and the children of index i at 2i+1 and 2i+2. The number in brackets above each node is that position, and it matches the array cell where its value appears. If children are missing, the positions in between stay empty.

Related tools