Balanced Tree

In Turkish: Dengeli Ağaç

Updated September 30, 20263 min read

In short

A balanced tree is a tree that keeps its height close to log n by rebalancing after changes, so search, insert, and delete stay O(log n) even in the worst case.

What is a balanced tree?

A balanced tree is a tree in which no branch is allowed to grow much deeper than the others, so its height stays proportional to log n, where n is the number of nodes. Height matters because searching, inserting, and deleting all walk from the root down a single path: a balanced tree with a million nodes is only about 20 levels tall, so an operation takes about 20 steps. Self-balancing trees keep this shape automatically, no matter what order the data arrives in.

The best-known self-balancing binary search trees are AVL trees and red-black trees. An AVL tree requires the heights of every node's two subtrees to differ by at most one, while a red-black tree colors each node red or black and follows rules that keep the longest path from the root no more than twice as long as the shortest. After an insert or delete, both repair any violation with rotations, small local rearrangements that change a few parent-child links while preserving the sorted order. AVL trees are more strictly balanced and slightly faster to search, while red-black trees need fewer rotations on updates, which is why many standard libraries use them.

Think of a well-run company where every manager has a similar number of reports, so any employee is only a few levels below the CEO; an unbalanced tree is a company where everyone reports to exactly one other person, and the newest hire is hundreds of levels down. Balanced trees power sorted maps and sorted collections in standard libraries, such as Java's TreeMap and C++'s std::map, which are usually red-black trees, and they appear inside operating system kernels, for example in CPU schedulers. For data stored on disk, databases use B-trees, which stay balanced by keeping all their leaves at the same depth.

A balanced tree is often confused with a plain binary search tree and with a complete tree. A plain BST follows the same ordering rule but never rebalances, so inserting sorted data turns it into a long chain with O(n) operations, which is exactly the problem balancing solves. A complete binary tree, the shape used by heaps, fills every level from left to right; it is always balanced, but a balanced tree doesn't have to be complete.

Key takeaways

A balanced tree keeps its height proportional to log n.
Search, insert, and delete are guaranteed O(log n), even when data arrives in sorted order.
AVL trees and red-black trees rebalance themselves using rotations.
Sorted maps such as Java's TreeMap and C++'s std::map are balanced trees under the hood.
An unbalanced binary search tree can degrade into a chain with O(n) operations.

Example

A left rotation turning a chain back into a balanced treepython

class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def rotate_left(x):
    # x's right child y becomes the new root of this subtree
    y = x.right
    x.right = y.left  # y's left subtree moves under x, keeping the order intact
    y.left = x
    return y

# Inserting 1, 2, 3 in sorted order builds a chain: 1 -> 2 -> 3 (height 3)
root = Node(1, right=Node(2, right=Node(3)))
root = rotate_left(root)  # the kind of repair AVL and red-black trees make
print(root.value, root.left.value, root.right.value)  # 2 1 3 (height 2)

Readers ask

What makes a tree balanced?

A tree is balanced when its height stays proportional to log n, which usually means that for every node the left and right subtrees have similar heights. Each kind of balanced tree defines this precisely; an AVL tree, for example, allows a height difference of at most one.

What is the difference between an AVL tree and a red-black tree?

Both are self-balancing binary search trees with O(log n) operations. AVL trees are balanced more strictly, so lookups are slightly faster, while red-black trees allow a little more imbalance and need fewer rotations when data changes, which suits workloads with many inserts and deletes.

Why use a balanced tree instead of a hash table?

A hash table is faster for exact-key lookups, O(1) on average, but it keeps no order. A balanced tree keeps keys sorted, so it can efficiently answer range queries, find the next larger key, and list items in order.