# Binary Search Tree Implementations: Performance Comparison of BST, AVL, and Red-Black Trees in Python

> Compare Python BST AVL and Red-Black tree implementations. Discover performance trade-offs between balanced and unbalanced trees to choose the best fit for your needs.

- Repository: [The Algorithms/Python](https://github.com/TheAlgorithms/Python)
- Tags: performance
- Published: 2026-02-24

---

**TheAlgorithms/Python repository provides three distinct binary search tree implementations—plain BST, AVL tree, and red-black tree—offering trade-offs between unbalanced O(n) worst-case performance with zero overhead, strictly balanced O(log n) with frequent rotations, and relaxed balancing with fewer rotations but greater tree depth.**

The choice of binary search tree implementation dramatically impacts application performance depending on input patterns and operation frequency. This analysis examines the three implementations found in the TheAlgorithms/Python repository, comparing their theoretical complexity, practical speed characteristics, and internal balancing mechanisms based on the actual source code.

## Overview of the Three Implementations

The repository ships three classic binary search tree families in `data_structures/binary_tree/`:

- **Plain BST** ([`binary_search_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/binary_search_tree.py)): Unbalanced structure with no rotation logic
- **AVL Tree** ([`avl_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/avl_tree.py)): Strictly self-balancing with height-difference enforcement
- **Red-Black Tree** ([`red_black_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/red_black_tree.py)): Relaxed balancing using color properties

All three expose similar public APIs (`insert`, `search`, `remove`/`delete`, and traversal methods), making them interchangeable in client code while delivering vastly different performance guarantees.

## Performance Characteristics and Complexity Analysis

### Plain BST (Unbalanced)

The `BinarySearchTree` class in [`binary_search_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/binary_search_tree.py) implements the simplest approach: nodes are added exactly where the key belongs without any rebalancing logic.

- **Time Complexity**: **O(n)** worst-case when input is sorted (degenerates to a linked list), but **O(log n)** average for random data
- **Space Complexity**: O(n) for all implementations
- **Practical Speed**: Fastest for tiny, random datasets because there is zero rotation overhead, but becomes catastrophically slow for ordered input

Nodes are simple objects with `value`, `left`, `right`, and `parent` attributes. The insertion algorithm walks down the tree until finding a `None` child, with no height tracking or structural adjustments.

### AVL Tree (Strictly Balanced)

The `AVLtree` class in [`avl_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/avl_tree.py) guarantees **O(log n)** worst-case performance for all operations through strict self-balancing.

- **Height Bound**: ≤ 1.44 · log₂ n (theoretical bound)
- **Rotation Overhead**: Up to 2 rotations per insert or delete operation
- **Time Complexity**: Guaranteed **O(log n)** regardless of input order
- **Practical Speed**: Slightly slower than plain BST on random data due to rotation work (`right_rotation`, `left_rotation`, `lr_rotation`, `rl_rotation`), but far more reliable for any input order

Each node stores its `height` attribute. After insertion (`insert_node`) or deletion (`del_node`), the code recomputes heights using `get_height` (implemented via `my_max`) and performs necessary rotations to maintain the invariant that the height difference between subtrees never exceeds 1.

### Red-Black Tree (Relaxed Balancing)

The `RedBlackTree` class in [`red_black_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/red_black_tree.py) offers a middle ground between strict AVL balancing and unlinked BST simplicity.

- **Height Bound**: ≤ 2 · log₂ n (less strict than AVL)
- **Rotation Overhead**: At most a handful of color flips and rotations per operation (average ≤ 2 rotations), typically fewer than AVL
- **Time Complexity**: Guaranteed **O(log n)** for search, insert, and delete
- **Practical Speed**: Typically marginally faster than AVL on heavy write workloads because fewer rotations are required, at the price of moderately larger tree depth

Nodes carry a `color` attribute (0 for black, 1 for red). Insertions trigger `_insert_repair` and deletions use `_remove_repair`, performing recoloring and rotations to maintain the five red-black properties. Helper properties like `grandparent`, `sibling`, `is_left`, and `is_right` keep the repair logic readable.

## Architectural Differences and Balancing Strategies

The internal mechanics reveal why performance differs:

**Plain BST** maintains no structural invariants. The `insert` method simply traverses to a leaf position and attaches the new node, making it vulnerable to pathological cases like inserting already-sorted data.

**AVL Tree** enforces immediate balance correction. After every mutation in `insert_node` or `del_node`, the algorithm checks balance factors and applies single or double rotations to restore the height invariant, ensuring the tree remains approximately half as tall as a red-black tree in the worst case.

**Red-Black Tree** delays strict balancing. By allowing temporary violations of ideal structure and fixing them through local recoloring and limited rotations (via `_insert_repair` and `_remove_repair`), it reduces the constant factor for write operations while maintaining logarithmic bounds.

## Practical Usage Examples

Each implementation handles the same dataset differently:

```python

# Plain BST (unbalanced) - binary_search_tree.py

from data_structures.binary_tree.binary_search_tree import BinarySearchTree

bst = BinarySearchTree()
bst.insert(8, 3, 6, 1, 10, 14, 13, 4, 7)
print("In-order:", list(bst.inorder()))   # → [1, 3, 4, 6, 7, 8, 10, 13, 14]

print("Search 6 →", bst.search(6).value)  # → 6

```

```python

# AVL tree (strictly balanced) - avl_tree.py

from data_structures.binary_tree.avl_tree import AVLtree

avl = AVLtree()
for v in [8, 3, 6, 1, 10, 14, 13, 4, 7]:
    avl.insert(v)
print("Root after inserts:", avl.root.get_data())  # → 8 (balanced)

```

```python

# Red-Black tree (relaxed balancing) - red_black_tree.py

from data_structures.binary_tree.red_black_tree import RedBlackTree

rbt = RedBlackTree()
for v in [8, 3, 6, 1, 10, 14, 13, 4, 7]:
    rbt = rbt.insert(v)  # insert returns the new root

print("In-order traversal:", list(rbt.inorder_traverse()))  # → sorted list

print("Min/Max:", rbt.get_min(), rbt.get_max())             # → 1, 14

```

## Summary

- **Plain BST** ([`binary_search_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/binary_search_tree.py)): Choose only when input is guaranteed random or trees remain very small (≤ 10 elements); offers minimal overhead but **O(n)** worst-case degradation
- **AVL Tree** ([`avl_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/avl_tree.py)): Select when guaranteed **O(log n)** worst-case performance and minimal tree height are critical; incurs more rotations than red-black trees but provides the tightest height bound (≤ 1.44 log₂ n)
- **Red-Black Tree** ([`red_black_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/red_black_tree.py)): Prefer for heavy write workloads with frequent insertions and deletions; offers guaranteed **O(log n)** with fewer rotations than AVL at the cost of greater maximum depth (≤ 2 log₂ n)

## Frequently Asked Questions

### Which binary search tree implementation is fastest for searching?

The **AVL tree** typically provides the fastest search performance among the three implementations because it maintains the strictest balance (height ≤ 1.44 log₂ n), resulting in fewer node comparisons per query. While both AVL and red-black trees guarantee **O(log n)** search time, the AVL's tighter height bound means fewer pointer traversals in practice, though the difference is negligible for most applications.

### Why would I use a plain BST instead of a self-balancing tree?

Use the plain `BinarySearchTree` implementation only when you have **guaranteed random input** or extremely small datasets (fewer than 10 elements). According to the source code in [`binary_search_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/binary_search_tree.py), the plain BST has zero rotation overhead, making it marginally faster for tiny trees, but it degenerates to **O(n)** linear search when encountering sorted input data.

### How many rotations occur during AVL tree insertions?

The AVL tree implementation in [`avl_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/avl_tree.py) performs **at most 2 rotations** per insertion or deletion. The `insert_node` method updates node heights via `get_height` and triggers `right_rotation`, `left_rotation`, `lr_rotation`, or `rl_rotation` only when the balance factor exceeds ±1, ensuring the tree remains strictly balanced with minimal structural adjustments.

### Is the red-black tree faster than AVL for frequent updates?

**Yes**, the red-black tree typically outperforms AVL trees under heavy write workloads. As implemented in [`red_black_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/red_black_tree.py), the relaxed balancing strategy requires fewer rotations per operation (average ≤ 2) compared to AVL's strict rebalancing, making insertions and deletions slightly faster despite allowing a larger maximum tree height (≤ 2 log₂ n versus AVL's ≤ 1.44 log₂ n).