Advanced Trees in DSA
Introduction
Advanced trees are specialized versions of binary trees designed to solve performance problems such as imbalance, slow search, and inefficient memory usage. These trees ensure fast and consistent operations even when large amounts of data are inserted or deleted.
In this chapter, you will learn four major advanced trees:
AVL Tree
Red-Black Tree
Segment Tree
Trie (Prefix Tree)
Each of these structures is used in high-performance systems like search engines, databases, compilers, and file systems.
AVL Tree
An AVL Tree is a self-balancing Binary Search Tree (BST). It ensures that the height difference between the left and right subtrees (called the balance factor) is always -1, 0, or 1.
If the tree becomes unbalanced after insertion or deletion, it automatically performs rotations to regain balance.
Why AVL Trees?
Guarantees O(log n) search time
Prevents skewed trees (like linked lists)
Used when searching is the highest priority
Balance Factor
Balance Factor = height(left subtree) – height(right subtree)
Allowed values: -1, 0, 1
AVL Tree Rotations
Left rotation
Right rotation
Left-Right rotation
Right-Left rotation
These rotations ensure the tree stays balanced.
Example: Right Rotation
30 20
/ / \
20 ? 10 30
/
10
C# Implementation (Simplified)
public int Height(Node node)
{
if (node == null) return 0;
return node.Height;
}
public int GetBalance(Node node)
{
return Height(node.Left) - Height(node.Right);
}
Red-Black Tree
A Red-Black Tree is another self-balancing BST but less strict than an AVL Tree. It assigns each node a color: red or black.
Key Red-Black Tree Rules
Every node is either red or black
Root is always black
No two red nodes can be adjacent
Every path from root to leaf has the same number of black nodes
Why Red-Black Trees?
Faster insertion and deletion than AVL Trees
Balanced structure ensures O(log n) operations
Used in:
C# Dictionary<TKey, TValue>
Java TreeMap
Linux Kernel
When to Use Red-Black Trees
When you need fast insertion and deletion
When perfect balance is not necessary
Segment Tree
A segment tree is a powerful tree used for answering range queries efficiently.
What Are Range Queries?
Examples:
Find the sum of values from index 2 to 8
Find the minimum in a range
Update an index value
Segment trees help answer these queries in O(log n) time.
Applications of Segment Trees
Competitive programming
Stock analysis
Range updates in arrays
Game development
Segment Tree Visualization
For an array:
[2, 5, 1, 4]
The segment tree stores:
Sum of full range
Sum of left half
Sum of right half
Example Structure
(12)
/ \
(7) (5)
/ \ / \
(2) (5) (1) (4)
Trie (Prefix Tree)
A Trie is a tree-like data structure used to store collections of strings. It is perfect for prefix-based searching.
Why Tries?
Very fast search and insert
Useful for autocomplete systems
Prefix-based operations are efficient
Trie Structure
Each node contains:
A character
A dictionary of child nodes
A flag to indicate if a word ends here
Example
Inserting words: car, cat, can
c
|
a
/ | \
r t n
Trie Implementation (Simplified)
public class TrieNode
{
public Dictionary<char, TrieNode> Children = new();
public bool IsEndOfWord = false;
}
Applications of Tries
Search engines
Spell checkers
Auto-suggest feature
IP routing
Summary
Advanced trees solve the problems of imbalance and slow searching found in basic trees. Each of these trees serves a unique purpose:
AVL Tree: Best for frequent searching
Red-Black Tree: Best for frequent insertion/deletion
Segment Tree: Best for range queries
Trie: Best for prefix-based string operations
These structures are widely used in real-world systems that require speed, reliability, and efficiency.