Balanced Trees in Data Structures

Learn Balanced Trees in Data Structures with practical examples, explanations, best practices, and real-world coding techniques.

What Is a Balanced Tree?

A balanced tree is a tree data structure designed to keep its height under control so that operations such as searching, insertion, and deletion remain efficient. The goal is not necessarily to make every branch exactly the same length, but to prevent the tree from becoming excessively skewed.

Binary search trees rely heavily on their height. When a binary search tree remains reasonably balanced, searching can approach O(log n) time. If the tree becomes highly skewed, the height can grow toward O(n), making the structure behave similarly to a linked list.

Why Tree Balance Matters

Consider inserting sorted values into a normal binary search tree: 10, 20, 30, 40, 50. Each new value is greater than the previous one, so every node can be inserted on the right side. 

10
     20
           30
                 40
                       50

Instead of forming a compact tree, the structure becomes a chain. Searching for 50 requires moving through several nodes. As the number of nodes increases, this can result in linear-time operations.

Balanced vs. Skewed Trees

A balanced tree distributes nodes across its branches so that its height remains relatively small. A skewed tree has most of its nodes concentrated along one side. 

Balanced:

       30
      /      20    40
   /     /  10  25 35  50


Skewed:

10
     20
           30
                 40

The balanced version has a much smaller height, which means fewer nodes need to be examined during search operations.

What Does "Balanced" Mean?

There is no single definition that applies to every tree structure. Different balanced-tree implementations use different rules to control their height.

For example, an AVL tree applies a strict height-balance condition to every node, while a Red-Black tree uses node colors and structural rules to keep the tree approximately balanced.

Self-Balancing Binary Search Trees

A self-balancing binary search tree automatically adjusts its structure when nodes are inserted or deleted. These adjustments prevent the tree from becoming too tall.

Two important self-balancing binary search tree families are:

  • AVL Trees — use height differences and rotations to maintain strict balance.
  • Red-Black Trees — use node colors and structural rules to maintain a bounded height.

How Balancing Is Achieved

Balanced binary search trees commonly use rotations to change the structure of the tree while preserving the binary-search-tree ordering property.

A rotation changes parent-child relationships without changing the sorted order of the values. This allows the tree to become shorter without rebuilding every node.

Basic Tree Rotation

A right rotation can be used when the left side of a subtree becomes too heavy. For example: 

Before:

      30
     /
   20
  /
10


After right rotation:

    20
   /   10   30

The ordering remains valid because 10 < 20 < 30, but the height of the subtree is reduced.

Left Rotation

A left rotation is used when the right side becomes too heavy. 

Before:

10
     20
           30


After left rotation:

    20
   /   10   30

Both left and right rotations are fundamental operations in self-balancing tree implementations.

AVL Trees

An AVL tree is a self-balancing binary search tree named after its inventors, Adelson-Velsky and Landis. It maintains a strict balance condition based on the height of the left and right subtrees of every node.

For an AVL tree, the balance factor of a node is commonly defined as: 

Balance Factor =
Height(left subtree) - Height(right subtree)

A node is balanced when its balance factor is -1, 0, or 1. If the value moves outside this range after an update, rotations are used to restore the AVL property.

AVL Tree Balance Example

Consider the following tree: 

    30
   /
  20
 /
10

The left subtree is significantly taller than the right subtree of node 30. The tree can be restructured with a right rotation: 

    20
   /   10   30

The resulting tree satisfies the AVL balance condition.

AVL Rotation Cases

AVL trees commonly describe four imbalance cases based on where the new node was inserted:

Case Imbalance Typical Fix
LL Left subtree of left child Right rotation
RR Right subtree of right child Left rotation
LR Right subtree of left child Left rotation, then right rotation
RL Left subtree of right child Right rotation, then left rotation

Red-Black Trees

A Red-Black tree is another type of self-balancing binary search tree. Each node has an additional color property, usually represented as red or black. A collection of structural rules ensures that the tree does not become excessively tall.

Unlike AVL trees, Red-Black trees do not maintain the same strict height balance at every node. Instead, they maintain a weaker balance condition that provides a bounded tree height.

Red-Black Tree Properties

A standard Red-Black tree follows rules such as:

  • Every node is either red or black.
  • The root is black.
  • A red node cannot have a red child.
  • Every path from a node to its descendant null leaves contains the same number of black nodes.
  • These rules prevent the tree from becoming excessively skewed.

The exact implementation details can vary, but these invariants are the foundation of standard Red-Black tree implementations.

AVL Trees vs Red-Black Trees

Both AVL and Red-Black trees maintain efficient logarithmic-height behavior, but they use different balancing strategies.

Feature AVL Tree Red-Black Tree
Balance strategy Height-based Color and structural rules
Balance strictness Stricter Less strict
Search O(log n) worst case O(log n) worst case
Insertion O(log n) worst case O(log n) worst case
Deletion O(log n) worst case O(log n) worst case

Balanced Tree Operations

A self-balancing binary search tree still performs the familiar BST operations:

  • Search: Follow the ordering property to locate a value.
  • Insertion: Insert the new value and restore the balancing rules if necessary.
  • Deletion: Remove the value and rebalance the affected portion of the tree.
  • Rotation: Change the local tree structure while preserving sorted order.

Why Rotations Preserve BST Ordering

Rotations may change the parent-child relationships, but they do not arbitrarily rearrange values. The relative ordering of the nodes remains valid for a binary search tree. 

Before:

      30
     /
   20
  /
10

In-order traversal:
10, 20, 30


After rotation:

    20
   /   10   30

In-order traversal:
10, 20, 30

The unchanged in-order ordering demonstrates why the rotation still represents the same sorted set of values.

Height and Performance

The main reason balanced trees are useful is that their height remains logarithmic relative to the number of nodes. A shorter tree means that search paths contain fewer nodes.

For a balanced binary search tree containing n nodes, search, insertion, and deletion can be maintained at O(log n) worst-case time, depending on the specific balancing scheme.

Balanced Trees vs Ordinary Binary Search Trees

Property Ordinary BST Balanced BST
Height Can become O(n) Maintained around logarithmic height
Search O(log n) average, O(n) worst case O(log n) worst case for standard self-balancing trees
Insertion O(log n) average, O(n) worst case O(log n) worst case
Deletion O(log n) average, O(n) worst case O(log n) worst case

Where Balanced Trees Are Used

Balanced tree structures are useful when applications need ordered data together with predictable search and update performance. They are especially valuable when data changes frequently and a simple sorted array would make insertions or deletions expensive.

  • Ordered collections and sets
  • Dictionary and map implementations
  • In-memory indexing structures
  • Compiler and language-runtime data structures
  • Database and storage-system components
  • Scheduling and ordered event management
  • Range and ordered lookup operations

Common Mistakes

  • Assuming every binary search tree is automatically balanced.
  • Confusing a balanced tree with a complete or perfect binary tree.
  • Forgetting that different balanced trees use different balancing rules.
  • Applying a single rotation when an AVL imbalance requires a double rotation.
  • Changing node relationships during a rotation without preserving BST ordering.
  • Assuming AVL and Red-Black trees maintain exactly the same height constraints.
  • Ignoring the cost of maintaining balance during insertion and deletion.

Key Takeaways

  • Balanced trees keep their height under control to maintain efficient operations.
  • A skewed binary search tree can degrade from logarithmic behavior to linear behavior.
  • Self-balancing trees automatically restructure themselves after updates.
  • Rotations change tree structure while preserving BST ordering.
  • AVL trees use strict height-based balance conditions.
  • Red-Black trees use colors and structural rules to maintain bounded height.
  • Standard self-balancing binary search trees provide O(log n) worst-case search, insertion, and deletion.

Code Examples 

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function rightRotate(root) {
  const newRoot = root.left;
  const movedSubtree = newRoot.right;

  newRoot.right = root;
  root.left = movedSubtree;

  return newRoot;
}

const root = new Node(30);
root.left = new Node(20);
root.left.left = new Node(10);

const balancedRoot = rightRotate(root);

console.log(balancedRoot.value);
// 20
    
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function height(node) {
  if (node === null) {
    return 0;
  }

  return 1 + Math.max(
    height(node.left),
    height(node.right)
  );
}

function balanceFactor(node) {
  if (node === null) {
    return 0;
  }

  return height(node.left) - height(node.right);
}

const root = new Node(30);
root.left = new Node(20);
root.left.left = new Node(10);

console.log(balanceFactor(root));
// 2
    
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

function height(node) {
  return node ? node.height : 0;
}

function updateHeight(node) {
  node.height =
    1 + Math.max(height(node.left), height(node.right));
}

function rightRotate(root) {
  const newRoot = root.left;
  const subtree = newRoot.right;

  newRoot.right = root;
  root.left = subtree;

  updateHeight(root);
  updateHeight(newRoot);

  return newRoot;
}

const root = new Node(30);
root.left = new Node(20);
root.left.left = new Node(10);

updateHeight(root.left);
updateHeight(root);

const balancedRoot = rightRotate(root);

console.log(balancedRoot.value);
// 20

Pro Tip

When learning balanced trees, focus first on why height matters, then understand rotations, and only after that learn the specific balancing rules of AVL and Red-Black trees. The rotation concept is the foundation for understanding how self-balancing works.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.