Elementary Data Structures

Stack

Queue
Double Ended Queue
Dynamic Allocation of Node
Shadow Copy
1.1 Stack
A Stack is a simple data structure where elements are added
and removed only from one end called the top.
It follows the rule:
LIFO (Last In First Out)
The last element added is the first one removed.
Example:
Push 10
Push 20
Push 30

Stack:

Top
30
20
10
If we remove an element:
Pop → 30
Basic Operations
1. push(x)
Adds element x to the top of the stack.
2. pop()
Removes and returns the top element.
3. stack_empty()
Checks whether the stack is empty.
4. top_element()
Shows the top element without removing it.

Implementations of Stack
1. Array Implementation
 Uses an array to store elements.
 A variable top keeps track of the stack position.
Problem:
 Array size is fixed.
 If the stack becomes full → Stack Overflow.

2. Linked List Implementation

Uses nodes connected with pointers.
Advantages:
 Stack size can grow dynamically.
  No fixed limit unless memory ends.

Applications of Stack
Stacks are used in many places such as:
 Function calls in programming
 Recursion
 Expression evaluation
 Undo operations
 Backtracking problems

1.2 Queue
A Queue is another linear data structure where elements are
inserted at one end and removed from the other.
It follows:
FIFO (First In First Out)
Example:
Front → 10 20 30 ← Rear
Remove → 10 first
Like people standing in a line at a ticket counter.

Queue Operations
1. enqueue(x)
Insert element at the rear of the queue.
2. dequeue()
Remove element from the front.
3. queue_empty()
Check if queue is empty.
4. front_element()
View the first element.

Queue Implementation
Array Implementation
Uses two variables:
 front
 rear
Problem:
  Fixed size array.
Solution:
 Circular queue is used.

Linked List Implementation

Nodes are connected with pointers.
Advantages:
 Dynamic size
 No overflow problem

Applications of Queue
Queues are used in:
 CPU scheduling
 Printer queue
 Breadth First Search (BFS)
 Network data packets

1.3 Double Ended Queue (Deque)

A Deque is a queue where insertion and deletion can happen
at both ends.
Operations:
 Insert at front
 Insert at rear
 Delete from front
 Delete from rear
Example:
Front → 10 20 30 ← Rear
You can remove 10 or 30.

Implementation
Deque can be implemented using:
 Arrays
 Doubly Linked Lists

Uses
Deque is used in:
 Sliding window algorithms
 Task scheduling
 Cache systems

1.4 Dynamic Allocation of Nodes

Dynamic allocation means memory is created when the
program runs, not before.
Instead of using memory every time with malloc, we use a free
list.

Free List
A free list is a list of nodes that are currently not used.
Two main functions are used.
get_node()
 Takes a node from the free list.
 If free list is empty, new memory block is created.
return_node()
 Returns a node back to the free list.
  The node can be reused later.

Advantage
 Faster memory usage
 Avoids frequent memory allocation
 Improves efficiency of dynamic structures

1.5 Shadow Copies of Array Structures

Arrays normally have fixed size, which causes problems when
the array becomes full.
To solve this, we use shadow copying.

Idea
Maintain two arrays:
1. Current array (in use)
2. New larger array (copying data)

Working
1. When the array becomes about 75% full, a new bigger
array is created.
2. Some elements are copied from the old array to the new
array during each operation.
3. After copying is finished:
o New array becomes active
o Old array is removed.

Example
Array sizes increase like this:
4 → 8 → 16 → 32 → 64
Each time the size doubles.

Advantage
 Avoids array overflow
 Allows arrays to grow dynamically
 Keeps operations efficient

Simple Summary
Sectio
Topic
n
1.1 Stack (LIFO structure)
1.2 Queue (FIFO structure)
Deque (Insert/Delete at both
1.3
ends)
1.4 Dynamic Node Allocation
Shadow Copy for dynamic
1.5
arrays

Here are very easy and small C codes for each topic so they
are simple to understand and easy to write in exams.

1. Stack (Easy Code)

int stack[100], top = -1;
void push(int x){
stack[++top] = x;
}

int pop(){
return stack[top--];
}
Idea:
 push() → add element to stack
 pop() → remove top element

2. Queue (Easy Code)

int queue[100], front = 0, rear = -1;

void enqueue(int x){

queue[++rear] = x;
}

int dequeue(){
return queue[front++];
}
Idea:
 enqueue() → insert element
 dequeue() → remove element

3. Double Ended Queue (Deque)

int dq[100], front = 0, rear = -1;

void insertRear(int x){

dq[++rear] = x;
}

int deleteFront(){
return dq[front++];
}
Idea:
Deque allows insert and delete from both ends.

4. Dynamic Allocation of Node

struct node{
int data;
struct node *next;
};

struct node* create(){

return (struct node*)malloc(sizeof(struct node));
}
Idea:
Creates a new node dynamically in memory.

5. Shadow Copy (Array Resize)

int *arr = malloc(4*sizeof(int));
int *newArr = malloc(8*sizeof(int));
for(int i=0;i<4;i++)
newArr[i] = arr[i];
Idea:
 Create bigger array
 Copy elements from old array.

Very Short Summary

Topic Operation
Stack push, pop
Queue enqueue, dequeue
insert, delete both
Deque
ends
Dynamic create node using
Node malloc
Shadow copy array to bigger
Copy array

If you want, I can also give a super neat exam answer format
(with diagram + code) for these 5 topics, which makes the
answer look perfect for 10-mark questions.

Data Structure Classification – Primitive

and Non-Primitive,
Data Structure Classification
Data structures are mainly classified into Primitive and Non-
Primitive data structures.

1. Primitive Data Structures

Primitive data structures are basic data types that are directly
supported by the programming language and store single
values.
Examples:
 Integer (int)
 Float
 Character (char)
 Boolean
Example in C
int a = 10;
float b = 5.5;
char c = 'A';
Diagram
Data Structures
|
Primitive
-------------------
| | | |
int float char boolean

2. Non-Primitive Data Structures

Non-primitive data structures are derived from primitive
data types and can store multiple values.
They are divided into two types:
1. Linear Data Structures
2. Non-Linear Data Structures

(a) Linear Data Structures

Elements are arranged sequentially (one after another).
Examples:
 Array
 Stack
 Queue
 Linked List
Diagram
Linear Data Structure

Array → [10][20][30][40]

Stack (LIFO)
-----
|40|
-----
|30|
-----
|20|
-----
 |10|
-----

Queue (FIFO)
Front → [10][20][30][40] ← Rear

(b) Non-Linear Data Structures

Elements are not arranged sequentially.
They form hierarchical or network relationships.
Examples:
 Tree
 Graph
Diagram
Tree

A
/\
B C
/\ \
D E F
Graph

A ----- B
\ /
\ /
C
 |
D

(Array, Stack, Queue) (Tree, Graph)

If you want, I can also give a shorter 5-mark exam answer

version with a cleaner diagram (very useful for writing in
exams).
Linear static arrray

Definition
A Linear Static Array is a linear data structure where elements
are stored sequentially in contiguous memory locations, and
the size of the array is fixed (static) and cannot be changed
during program execution.

Example
int arr[5] = {10, 20, 30, 40, 50};

Linear – Static (Array)

Linear Data Structure
A Linear Data Structure stores elements in sequential order
(one after another).
Example:
 Array
 Stack
 Queue
 Linked List

Static Data Structure – Array

A Static Array is a linear data structure with fixed size.
The size of the array is decided before program execution and
cannot be changed later.
Definition
An Array is a collection of same data type elements stored in
contiguous memory locations.

Example
int arr[5] = {10, 20, 30, 40, 50};

Diagram
Index : 0 1 2 3 4
-----------------------------
Array : | 10 | 20 | 30 | 40 | 50 |
-----------------------------

Characteristics
 Elements stored sequentially
 Fixed size
 Same data type
 Access using index

Advantages
 Easy to access elements
 Fast access using index
Disadvantages
 Size cannot be changed
  Memory may be wasted

✅ Very short exam definition:

Static Array: A linear data structure where elements of the
same data type are stored in contiguous memory locations and
the size is fixed.

Dynamic – Linked List (Very Easy

Explanation)
What is Linked List?
A Linked List is a dynamic linear data structure where data is
stored in nodes, and each node is connected to the next node
using a link (pointer).
✔ Dynamic means the size can increase or decrease
anytime.

Node Structure
Each node has two parts:
1. Data → stores the value
2. Link → points to the next node

Simple Diagram
[10 | * ] → [20 | * ] → [30 | * ] → NULL
Explanation:
 First node → 10
 Second node → 20
 Third node → 30
 Arrow (→) shows connection
  NULL means end of list

Another Simple View

Data : 10 20 30
↓ ↓ ↓
Node → Node → Node → NULL

Key Points
 Elements stored one after another (linear)
 Memory not continuous
 Size can change
 Nodes connected by links

Very Short Exam Definition

Linked List:
A dynamic linear data structure where nodes store data and a
link to the next node.

If you want, I can also give 2-line answer + very neat exam
diagram (the one teachers expect in Data
#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
struct node *next;
};
int main() {
struct node *n1, *n2;

n1 = (struct node*)malloc(sizeof(struct node));

n2 = (struct node*)malloc(sizeof(struct node));

n1->data = 10;
n1->next = n2;

n2->data = 20;
n2->next = NULL;

printf("%d -> %d", n1->data, n2->data);

return 0;
}

Stack, Queue, Non Linear – Tree, Graph.

Here is a simple explanation with small diagrams (good

for exams).

Linear Data Structures

1. Stack
A Stack is a linear data structure that follows LIFO (Last In
First Out).
The element inserted last will be removed first.
Example
Stack of plates.
Diagram
-----
|30 |
-----
|20 |
-----
|10 |
-----
Top element 30 will be removed first.
Operations
 Push – Insert element
 Pop – Delete element

2. Queue
A Queue is a linear data structure that follows FIFO (First In
First Out).
The element inserted first will be removed first.
Example
People standing in a line.
Diagram
Front → [10][20][30][40] ← Rear
Element 10 will be removed first.
Operations
 Enqueue – Insert element
 Dequeue – Remove element

Non-Linear Data Structures

3. Tree
A Tree is a non-linear data structure where elements are
arranged in a hierarchical structure.
Diagram
A
/\
B C
/\ \
D E F
 A → Root
 B, C → Children
 D, E, F → Leaf nodes

4. Graph
A Graph is a non-linear data structure consisting of vertices
(nodes) and edges (connections).
Diagram
A ----- B
\ /
\ /
C
|
 D
 A, B, C, D → Vertices
 Lines → Edges

✅ Very short exam definitions

 Stack: Linear data structure that follows LIFO.
 Queue: Linear data structure that follows FIFO.
 Tree: Non-linear hierarchical data structure.
 Graph: Non-linear structure consisting of nodes and
edges.

If you want, I can also give very small C code for Stack and
Queue (5–6 lines each) which is perfect for writing in
exams.

Search Trees: Two Models of Search

Trees.

I will explain only in simple sentences (no symbols).

Model 1 – First Type of Search Tree

When searching a value in the tree:
 Compare the search value with the value in the node.
  If the search value is smaller, move to the left child.
 If the search value is not smaller, move to the right child.
 Continue this process until you reach the last level of the
tree called a leaf.

Important point:
The nodes inside the tree are used only for comparison.
The actual objects or data are stored only in the leaf nodes.

Model 2 – Second Type of Search Tree

When searching a value in the tree:
 Compare the search value with the node value.
 If the search value is smaller, move to the left child.
 If the search value is larger, move to the right child.
 If both values are equal, the object is found in that node.
Important point:
Here data is stored in every node of the tree.

Simple Difference
Model 1: Data is stored only in leaf nodes.
Model 2: Data is stored in every node.

Very Short Exam Answer

Model 1: Move left if the key is smaller, otherwise move right
until reaching a leaf. Objects are stored only in leaf nodes.
Model 2: Move left if the key is smaller, move right if larger, and
if both are equal the object is found in the node. Objects are
stored in every node.

I will simplify this whole topic so you can understand it easily.

2.1 Two Models of Search Trees (Easy Explanation)

Main Differences
Model 1 Model 2
Data only in leaf nodes Data in every node
Internal nodes used for Nodes store data +
comparison comparison
Needs 1 comparison per step Needs 2 comparisons
Structure is more regular Structure is less regular

Small Code in C (Tree Node)

typedef struct node {
int key;
struct node *left;
struct node *right;
} tree_node;

Each node has:

 key → value
  left pointer
 right pointer

✔ One easy sentence to remember for exams

 Model 1: Data only in leaves
 Model 2: Data in every node

General Properties and

Transformations.

I will explain 2.2 General Properties and Transformations

in a very simple way.

1. Interval Idea in Search Tree (Easy)

In a search tree, every node represents a range of values
(interval) where keys can exist.
Root Node
The root can contain any value, so its interval is:
-∞ to +∞
(meaning any number is possible)

Example Tree
10
/ \
5 16
/\ \
3 7 20
Intervals
Node 10
Possible values:
-∞ to +∞
Left side → values less than 10
Right side → values greater than or equal to 10
Node 5
Possible values:
between -∞ and 10
Left side → values less than 5
Right side → values between 5 and 10
So every node divides the range into two parts.
This helps the tree search correctly.

2. Different Trees Can Store Same Data

The same set of keys can be arranged in many different
tree shapes.
Both trees store the same data, but the structure is
different.
Some trees are better (faster search).

3. Tree Rotations
To improve tree structure we use rotations.
Rotation means rearranging nodes but keeping the same
data.
Two types:
1. Left Rotation
2. Right Rotation

4. Left Rotation (Easy)

Before rotation
10
 \
20
/
15
After left rotation
20
/
10
\
15
The tree becomes more balanced.

5. Right Rotation (Easy)

Before rotation
20
/
10
/
5
After right rotation
10
/ \
5 20

Important Point
Rotation:
  changes tree shape
 keeps same keys
 improves tree balance

Very Short Exam Answer

Intervals in Search Tree:
Each node represents a range of possible key values. The left
subtree contains smaller keys and the right subtree contains
larger keys.
Rotations:
Left and right rotations are operations that rearrange nodes of a
search tree without changing the data, helping maintain a
better tree structure.
The height of a search tree is the longest path from the
root node to a leaf node.
In simple words:
Height = maximum number of levels from root to leaf.

Example
10
/ \
5 20
/\
3 7
Longest path:
10 → 5 → 3
So the height = 2
(we count edges between nodes)

What is Depth?
Depth means the distance of a node from the root.
Example:
10
/ \
5 20
/
3
Depth values:
Root (10) → depth = 0
Node (5) → depth = 1
Node (3) → depth = 2

Maximum Leaves
If tree height = h
Maximum number of leaf nodes =
2^h
Example:
Height = 3
Maximum leaves = 8

Minimum Leaves
Minimum number of leaves =
h+1
Example:
Height = 3
Minimum leaves = 4

Important Idea
Some trees are good and some are bad.
Good tree → small height → faster searching
Bad tree → large height → slower searching

Very Short Exam Answer

The height of a search tree is the maximum length of the
path from the root to a leaf node. The depth of a node is its
distance from the root. For a tree of height h, the maximum
number of leaves is 2^h, and the minimum number of leaves is
h + 1.

Basic Find, Insert, and Delete

I’ll explain Section 2.4: Basic Find, Insert, Delete in

Search Trees (Binary Search Tree) in a very simple way
for exams with idea + small code + diagram explanation.

2.4 Basic Operations in Search Tree

A Search Tree (BST) stores (key, object) pairs.
Main operations:
1. Find → Search a key
2. Insert → Add a new key
3. Delete → Remove a key

1. Find Operation
Idea
To find a key:
1. Start from root
2. Compare with node key
3. If smaller → go left
4. If greater → go right
 5. Continue until key found or NULL

Example Tree
50
/ \
30 70
/\ /\
20 40 60 80

Explanation:
 Start at 50
 40 is smaller than 50 → go left to 30
 40 is greater than 30 → go right to 40
 Value found
So 40 exists in the tree.

Find(40)
50 → 30 → 40
FOUND

Example: Find 42
Search process:
50 → 30 → 40 → NULL
Explanation:
 Start at 50
 Move left to 30
  Move right to 40
 Next position has no node
So 42 is not present in the tree.

Simple C Code (Find)

#include <stdio.h>
int main() {
int a = 25, b = 5;
// > (Greater than), < (Less than), == (Equal to)
printf("a > b: %d\n", a > b); // Output: 1 (True)
printf("a < b: %d\n", a < b); // Output: 0 (False)
return 0;
}

2. Insert Operation
Idea
Insert like find operation, but when we reach NULL we create
a new node.
Steps:
1. Start from root
2. Compare key
3. Move left or right
4. When NULL found → insert node

Example Insert(35)
Before:
 50
/
30
\
40
After Insert 35
50
/
30
\
40
/
35

Simple C Code (Insert)

#include <stdio.h>

int main() {
int root = 50;
int newKey = 30;

printf("Root value: %d\n", root);

printf("New value to insert: %d\n", newKey);

if(newKey < root)

printf("Insert on LEFT side of root\n");
 else
printf("Insert on RIGHT side of root\n");

return 0;
}
3. Delete Operation
Delete is more complex.
There are 3 cases.

Case 1: Delete Leaf Node

Example delete 20
Before
30
/
20
After
30

Case 2: Node with One Child

Example delete 30
Before
30
\
40
After
40
Case 3: Node with Two Children
Replace node with Inorder Successor (smallest in right
subtree).
Example delete 50
Before
50
/ \
30 70
Replace with 60
60
/ \
30 70

Simple C Code (Delete)

#include <stdio.h>

int main() {
int key = 40;
int deleteKey = 40;

printf("Node value: %d\n", key);

printf("Value to delete: %d\n", deleteKey);

if(key == deleteKey)
printf("Node deleted\n");
else
 printf("Node not found\n");

return 0;
}

Time Complexity
Operati Tim
on e
Find O(h)
Insert O(h)
Delete O(h)
Where h = height of tree
Balanced tree → O(log n)
Worst case → O(n)

✅ In one line (Exam Answer):

 Find: Traverse left or right based on key comparison.
 Insert: Locate correct position and add new node.
 Delete: Remove node and adjust tree structure.
If you want, I can also show one super-simple exam
diagram for Find + Insert + Delete (1 page answer
format) which teachers like in Data Structures exams.

Returning from Leaf to Root

I’ll explain Section 2.5 Returning from Leaf to Root in a
very simple way.

2.5 Returning from Leaf to Root (Easy Explanation)

In a search tree, every operation works like this:
1. Start from the root
2. Move down the tree
3. Reach a leaf node (end node)
Example:
50
/ \
 30 70
/\
20 40
If we search 20, the path is:
50 → 30 → 20
We move from root to leaf.

Why Return from Leaf to Root?

In some operations (especially balanced trees), after reaching
the leaf we must:
 update nodes
 rebalance the tree
So we must go back from leaf to root.
Example path back:
20 → 30 → 50

Methods to Return from Leaf to Root

There are 4 ways to remember the path.

Stack
Back pointers
Back pointers with lazy update
Reverseing a path

1. Stack Method (Most Common)

While going down the tree:
 store nodes in a stack
We pop nodes from stack.
Advantage
 Very simple
 Uses little memory

2. Back Pointer Method

Each node stores a pointer to its parent node.
Example node structure:
Node
├ left
├ right
└ parent
Example tree:
50
/
30
/
20
From 20, we can go up using parent pointer:
20 → 30 → 50
Advantage
Easy to go back.
Disadvantage
Each node needs extra memory for parent pointer.

4. Lazy Back Pointer

This is similar to back pointer.
But the parent pointer is updated only during the search.
So the parent pointer is correct only for the current path.
Example path:
50 → 30 → 20
Only these nodes have correct parent pointers.

5. Reversing the Path

This method temporarily reverses pointers while going
down the tree
Normal tree:
50
|
30
|
20
While going down, pointers are reversed.
Temporary structure:
20
|
30
|
50
Now returning:
20 → 30 → 50
After finishing, tree becomes normal again.
.
Problem
 Tree structure becomes temporarily broken
 Hard to implement
So this method is rarely used today.

Simple Summary
Method Idea
Stack Save visited nodes in stack
Back Pointer Each node stores parent
Lazy Back Parent stored only during
Pointer search
Reverse pointers
Reverse Path
temporarily

✅ Simple one-line exam answer

Returning from leaf to root is needed in search trees to
update or rebalance nodes. This can be done using a
stack, back pointers, lazy back pointers, or by reversing
the path.

Dealing with Non unique Keys.

Sure! Let's break this down into a simple, easy-to-understand
explanation. The topic is handling nonunique keys in a
search tree.

The Problem
In real-world applications, sometimes multiple objects have the
same key. For example:
 In a database, several students might have the same
grade.
 In a product inventory, multiple products might have the
same price.
A normal search tree assumes unique keys, but this doesn’t
work here. So we need a way to store multiple objects with
the same key.

What We Want
1. Find: When we search for a key, we want all objects with
that key.
o Time: O(h + k), where:
 h = height of the tree
 k = number of objects with that key
2. Insert: Add a new object with a key. Should be fast.
 o Time: O(h)
3. Delete: Remove all objects with a key. Should also be fast.
o Time: O(h)

How to Do It (The Easy Way)

1. Use a linked list at each leaf for duplicate keys.
o Each leaf in the tree corresponds to a key.
o If multiple objects have that key, store them in a
linked list under that leaf.
2. Find operation:
o Go to the leaf for the key → return the linked list.
o Done in O(h + k) time.
3. Insert operation:
o Go to the leaf → insert the new object at the
beginning of the linked list.
o Done in O(h) time.
4. Delete operation:
o To delete all objects of a key efficiently:
 Add an extra node between the leaf and the
linked list.
 This node has pointers to the start and end of
the list.
 Now we can remove the entire list in O(1) time
(just update pointers).
Note: If you want to delete the objects themselves (not just
references), you have to walk through the list → O(k) time.

Analogy
Think of it like a mailbox for each key:
 The tree is the street.
 Each leaf is a house with a mailbox (the key).
 The mailbox contains letters (objects with the same key).
 Insert a new letter → drop it in the mailbox.
 Find → open the mailbox and get all letters.
 Delete all letters → just remove the mailbox (or walk
through letters to shred them individually).

✅ Summary in Short
 Nonunique keys → store duplicates in linked lists at
leaves.
 Find → return list.
 Insert → add to list.
 Delete → use extra pointer node to remove entire list
quickly.

If you want, I can draw a simple diagram showing how

duplicates are stored in the tree with linked lists — it makes this
much easier to visualize.
Do you want me to do that?

Queries for the Keys in an Interval

Absolutely! Let’s simplify this step by step so it’s easy to
understand. I’ll put it in plain language and explain the main
ideas with examples.

2.7 Queries for the Keys in an Interval – Simplified

Explanation
1. What is the problem?
Normally, a search tree lets you find a single key.
But sometimes we want all keys in a range [a, b[ (from a
inclusive to b exclusive).
 Example: Tree has keys {2, 5, 7, 10}
 Query interval [4, 9[ → result = {5, 7}
If you just use normal find, it will say “not found” for a key
that’s not exactly in the tree. That’s not very helpful if you want
a range of keys or the nearest key.

2. Two ways to do interval queries

Method 1: Doubly linked list of leaves
 Connect all leaf nodes (actual data nodes) into a doubly
linked list.
 Now you can move from a leaf to the next larger or next
smaller in O(1) time.
 Querying a range is just walking along the list and
collecting the keys in [a, b[.
✅ Pros: Very fast for ranges.
⚠️Cons: Slightly more work when inserting or deleting nodes to
maintain the list.

Method 2: Stack-based search (no tree changes)

This is what the paragraph you quoted is describing.
  You don’t change the tree at all.
 Instead, you change the query function to find keys in
[a, b[ using a stack.
How it works:
1. Start at the root and push it onto the stack.
2. While the stack is not empty:
o Pop a node from the stack.
o If it’s a leaf, check if a <= key < b → if yes, add it to
the result.
o If it’s an internal node:
 If the interval is completely left of the node
→ push the left child.
 If the interval is completely right of the node
→ push the right child.
 If the node key is inside the interval → push
both left and right children.
3. Repeat until the stack is empty.
This way, you only explore nodes that might contain keys in the
interval.

3. Why the paragraph says “nodes visited”

 When you use this method:
o You visit nodes on the path to the start of the
interval (a)
o You visit nodes on the path to the end of the
interval (b)
o You also visit nodes between these two paths
 If there are i nodes between these paths, there are at least
i+1 leaves in the interval.
  Total nodes visited ≈ twice the number of nodes for a
normal find + number of leaves in the interval.
✅ Meaning: Slightly slower than method 1, but you don’t need
to change how you insert or delete nodes.

4. Example
Tree:
7
/\
3 10
/\ \
1 5 12
Query [4, 11[:
 Start at 7 → 7 in interval → push left and right → result =
[7]
 Node 3 → 3 < 4 → interval is to the right → push 5
 Node 5 → 5 in interval → result = [7, 5]
 Node 10 → 10 in interval → result = [7, 5, 10]
 Node 12 → 12 ≥ 11 → ignore
Final result = [5, 7, 10]

✅ Key Takeaways
1. Interval queries = find all keys in [a, b[.
2. Two methods:
o Linked leaves → very fast
o Stack-based → no change to tree, a bit slower
 3. Stack-based works by pushing children only when
they might have keys in the interval.
4. Total nodes visited ≈ twice a normal find + leaves in
interval.

If you want, I can draw a simple diagram showing the

stack and how it moves for [4, 11[ so it’s very visual.
Do you want me to do that?
Here is a small and simple C code for Interval Query in a
Binary Search Tree.
This version is much shorter and easier for exams.

Simple C Code – Interval Query in BST

#include <stdio.h>
#include <stdlib.h>

struct node
{
int key;
struct node *left;
struct node *right;
};

void intervalFind(struct node *root, int a, int b)

{
if (root == NULL)
return;
 // check left subtree
if (root->key > a)
intervalFind(root->left, a, b);

// print key if in interval

if (root->key >= a && root->key < b)
printf("%d ", root->key);

// check right subtree

if (root->key < b)
intervalFind(root->right, a, b);
}

Example Tree
7
/\
3 10
/\ \
1 5 12
Query
intervalFind(root, 4, 11);
Output
5 7 10

Why this code is easy

 Uses recursion
  No stack implementation needed
 Only 3 conditions
 Prints keys between a and b

✅ Important condition
a ≤ key < b

If you want, I can also give a 5-line exam algorithm version

that teachers usually expect for 2.7 Interval Query.

Building Optimal Search Trees

A. Bottom-up Construction (start from leaves)

B. Top-down Construction (start from root)

Two ways to build an optimal tree

A. Bottom-up Construction (start from leaves)
Idea:
1. Start with each key as a leaf node.
2. Combine two consecutive nodes to make a small tree.
3. Repeat combining trees until you have only one root.
Example:
Keys: [1, 2, 3, 4, 5, 6, 7]
Step 1: Leaves → 1 2 3 4 5 6 7
Step 2: Combine pairs → (1,2) (3,4) (5,6) 7
Step 3: Combine pairs → ((1,2),(3,4)) ((5,6),7)
Step 4: Combine final trees → (((1,2),(3,4)),((5,6),7))
Pros: Simple to implement.
Cons: Can be unbalanced if number of nodes isn’t perfect
(some subtrees bigger than others).
Sure! Let’s draw the tree for your Bottom-up Construction
example step by step so it’s easy to visualize.

Keys: [1, 2, 3, 4, 5, 6, 7]

Step 1: Leaves
1 2 3 4 5 6 7

Step 2: Combine consecutive nodes

Combine pairs: (1,2), (3,4), (5,6) and 7 stays alone.
(1,2) (3,4) (5,6) 7

Step 3: Combine pairs again

Combine (1,2) & (3,4) → left tree
Combine (5,6) & 7 → right tree
((1,2),(3,4)) ((5,6),7)
#include <stdio.h>

// Swap two elements

void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }

// Sift down for Bottom-Up

void siftDown(int arr[], int n, int i){
int largest=i, left=2*i+1, right=2*i+2;
if(left<n && arr[left]>arr[largest]) largest=left;
if(right<n && arr[right]>arr[largest]) largest=right;
if(largest!=i){
swap(&arr[i], &arr[largest]);
siftDown(arr,n,largest);
}
}

// Bottom-Up Heap
void bottomUp(int arr[], int n){
for(int i=n/2-1;i>=0;i--) siftDown(arr,n,i);
}

// Print heap
void print(int arr[], int n){
for(int i=0;i<n;i++) printf("%d ", arr[i]);
printf("\n");
}

int main(){
int arr[]={5,3,8,1,2,7};
int n=6;

bottomUp(arr,n);
printf("Bottom-Up Heap: ");
print(arr,n);

return 0;
}

✅ Observation:
 Height is not perfectly balanced.
 Left subtree has more nodes than right subtree.
 Simple to implement, but can be unbalanced if n is not a
power of 2.

If you want, I can also draw the Top-down construction tree side
by side so you can compare both easily.
Do you want me to do that?

B. Top-down Construction (start from root)

Idea:
1. Take the middle key of the list → this becomes the root.
2. Keys left of middle → build left subtree (recursively).
3. Keys right of middle → build right subtree (recursively).
Example:
Keys: [1, 2, 3, 4, 5, 6, 7]
 Middle = 4 → root = 4
 Left half [1,2,3] → middle = 2 → left child = 2
o Left child of 2 = 1
o Right child of 2 = 3
 Right half [5,6,7] → middle = 6 → right child = 6
o Left child of 6 = 5
o Right child of 6 = 7
Resulting Tree (perfectly balanced):
4
/ \
2 6
/\ /\
1 35 7
Pros: Always balanced, minimal height → fast search.
Cons: Slightly more work to find middle in a list, but easy with
arrays.
Quick Comparison
 Start Easy to
Method Balance When to Use
From Implement
Bottom- Can be Small lists or
Leaves Easy
up unbalanced simple approach
Top- Always Slightly Best for optimal
Root
down balanced harder height

💡 Tip to remember:
 Bottom-up → build from bottom (leaves) → combine
upwards
 Top-down → pick root first → divide list → recurse
#include <stdio.h>

// Swap two elements

void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }

// Top-Down Heap
void topDown(int arr[], int n){
for(int i=1;i<n;i++){
int k=i;
while(k>0 && arr[k]>arr[(k-1)/2]){
swap(&arr[k], &arr[(k-1)/2]);
k=(k-1)/2;
}
}
}
// Print heap
void print(int arr[], int n){
for(int i=0;i<n;i++) printf("%d ", arr[i]);
printf("\n");
}

int main(){
int arr[]={5,3,8,1,2,7};
int n=6;

topDown(arr,n);
printf("Top-Down Heap: ");
print(arr,n);

return 0;
}
. Converting Trees into Lists.
Absolutely! Let’s simplify “Converting Trees into Lists” so
it’s easier to understand. I’ll break it down step by step with a
clear example.
1. What we want to do
We have a tree (like a binary search tree) and we want to
convert it into an ordered list.
 Example tree:
4
/\
2 6
/\/\
1 35 7
 We want a list: [1, 2, 3, 4, 5, 6, 7] (in increasing order)

2. How we do it
We can use Depth-First Search (DFS) with a stack:
 A stack helps us remember which nodes to visit next.
 We can traverse the tree and insert each node at the
front of the list if we go from largest to smallest
(decreasing order).

Step-by-step process:
1. Start at the root.
2. Push the root into the stack.
3. While the stack is not empty:
o Pop the top node.
o Insert the node’s value at the front of the list.
o Push the node’s left child, then right child into the
stack.
4. Repeat until the stack is empty.
Why it works
 By pushing left child before right child, when popping
from stack, we visit right first, then left → this gives
decreasing order.
 Inserting at the front of the list reverses it → gives
increasing order.

Easy Pseudocode
Sure! Here’s a simple C version of converting a binary search
tree into an increasing order list using in-order traversal
(recursive, easy to understand):
#include <stdio.h>
#include <stdlib.h>

// Define a tree node

struct Node {
int val;
struct Node* left;
struct Node* right;
};

// Function to create a new node

struct Node* newNode(int val) {
struct Node* node = (struct Node*)malloc(sizeof(struct
Node));
node->val = val;
node->left = node->right = NULL;
return node;
}

// In-order traversal to convert tree to list

void treeToList(struct Node* root) {
if (root == NULL) return;
treeToList(root->left); // Visit left subtree
printf("%d ", root->val); // Visit node
treeToList(root->right); // Visit right subtree
}

int main() {

// Example tree
struct Node* root = newNode(4);
root->left = newNode(2);
root->right = newNode(6);
root->left->left = newNode(1);
root->left->right = newNode(3);
root->right->left = newNode(5);
root->right->right = newNode(7);

printf("Tree as list: ");

treeToList(root); // Output: 1 2 3 4 5 6 7
return 0;
}
✅ Key points:
 Uses recursive in-order traversal → automatically gives
increasing order.
 Very simple and clear.
 Prints the tree nodes as a list.

If you want, I can also write a C version using a stack

(iterative method), which is closer to your original “stack-
based tree-to-list” explanation.
Do you want me to do that?

Result for our example tree:

1. Stack starts with [4]
2. Pop 4 → insert at front → list = [4]
3. Push left (2), right (6) → stack = [2, 6]
4. Pop 6 → insert at front → list = [6, 4]
5. Push left (5), right (7) → stack = [2, 5, 7]
6. Continue… final list → [1, 2, 3, 4, 5, 6, 7]
✅ Done! We have an increasing order list.
3. Tips for Implementation
 If the tree’s height is small, you can use an array
instead of a stack for simplicity.
 This algorithm runs in O(n) time for n nodes.

If you want, I can also draw a simple diagram showing the

stack and list changes step by step—it makes it super
easy to visualize.
Do you want me to do that?

Removing a Tree

Sure! Let’s simplify “Removing a Tree” so it’s easy to

understand. I’ll break it down step by step.

1. What we want to do
When we no longer need a tree, we need to free all its nodes
to avoid memory leaks.
 Each node is dynamically allocated.
 We cannot free all nodes in one step instantly; we have to
visit every node.
 Goal: O(n) time, i.e., constant time per node.
2. Basic idea
There are two common approaches:
1. Stack-based method:
o Use a stack (like converting a tree to a list).
o Push nodes onto the stack, pop them one by one,
free them.
2. Elegant rotation method (the one in your book):
o Works without an explicit stack.
o Keeps rotating the tree so that the left-most node
becomes a leaf.
o Free the leaf and move the tree down.
o Repeat until the tree is empty.

3. How the rotation method works

Imagine your tree:
4
/\
2 6
/\
1 3
Steps:
1. Start at root (4).
2. Check if left child is NULL:
o If yes → tree has no left subtree → free root and done.
o If no → continue.
3. Rotate nodes:
o If the left child has no right child → left child is a leaf.
  Free that leaf.
 Move root down to its right child.
 Free the old root.
o Else → perform a rotation: move the left child’s right
child up, move current node down.
4. Repeat until all nodes are freed.

Visual idea of rotations

1. Original root = 4
4
/\
2 6
/\
1 3
2. Rotate left-lower neighbor:
2
/\
1 4
\
6
3. Free left leaf (1), move root down (4), free root, repeat…
Eventually all nodes are removed.

4. Key points
 This method avoids recursion and extra stack.
 Each node is freed once, so time complexity = O(n).
  It’s like walking down the left side of the tree, freeing
nodes as leaves appear.

If you want, I can also make a very simple C code version to

remove a tree that is easy to understand using recursion or
stack.
Do you want me to do that?
Perfect! Let’s make it super simple in C. The easiest way to
remove a tree is using recursive post-order traversal (left →
right → node).

Simple C Code to Remove a Tree

#include <stdio.h>
#include <stdlib.h>

// Define tree node

struct Node {
int val;
struct Node* left;
struct Node* right;
};

// Create a new node

struct Node* newNode(int val) {
struct Node* node = (struct Node*)malloc(sizeof(struct
Node));
node->val = val;
node->left = node->right = NULL;
 return node;
}

// Remove (free) the tree

void removeTree(struct Node* root) {
if (root == NULL) return;

removeTree(root->left); // Free left subtree

removeTree(root->right); // Free right subtree

// Free current node

printf("Freeing node %d\n", root->val); // Optional: show
which node is freed
free(root);
}

int main() {
// Example tree
struct Node* root = newNode(4);
root->left = newNode(2);
root->right = newNode(6);
root->left->left = newNode(1);
root->left->right = newNode(3);
root->right->left = newNode(5);
root->right->right = newNode(7);
 // Remove the tree
removeTree(root);
return 0;
}

✅ How it works
1. Go all the way left (smallest nodes).
2. Go right if present.
3. Free the node itself.
4. Repeat for all nodes → entire tree removed.
 This is easy to understand, perfect for beginners.
 Time complexity: O(n) (each node freed once).
 No memory leaks.

If you want, I can also make a stack-based iterative version

in C (like the one in your book) so it doesn’t use recursion,
which is closer to that “rotation trick.”
Do you want me to do that?

2nd module
Balanced Search Trees: Height-
Balanced Trees. Weight-Balanced Trees
 Height-Balanced Weight-Balanced
Feature
Trees (e.g., AVL) Trees (e.g., BB[α])
Difference of heights Ratio of sizes (number
Balance Criterion of left and right of nodes) of left and
subtrees ≤ 1 right subtrees ≤ α
Weight (number of
Focus Height of subtrees
nodes) of subtrees
Node Size (number of
Height of subtree at
Information nodes) of subtree at
each node
Stored each node
Rebuild subtree or
How Balance is Rotations after
rotate if weight
Maintained insert/delete
condition violated
O(log n) amortized
Insertion/ O(log n) (due to
(may need subtree
Deletion Cost limited rotations)
rebuilding)
Search Cost O(log n) O(log n)
Example AVL Tree BB[α] Tree
When height When subtree sizes
When Useful difference must be matter more than
strictly controlled exact height

Key Idea to Remember:

 Height-Balanced → cares about height → rotations are
frequent but simple.
 Weight-Balanced → cares about number of nodes →
may rebuild subtrees, not just rotate.
If you want, I can also make a small diagram showing both
tree types side by side so it’s super easy to visualize the
difference.
Do you want me to do that?

Sure! Let’s break down Balanced Search Trees, focusing on

Height-Balanced Trees and Weight-Balanced Trees, in a
simple and easy-to-understand way.

1. Balanced Search Trees – Overview

A balanced search tree is a binary search tree (BST) that
tries to keep its structure “balanced” to ensure that
operations like search, insert, and delete are fast.
 In a normal BST, if nodes are inserted in sorted order, the
tree can become a linked list → operations degrade to
O(n).
 Balanced trees prevent this by keeping the tree
approximately balanced → operations stay O(log n).
Two common types of balancing:
1. Height-Balanced Trees
2. Weight-Balanced Trees

Okay, let’s take 30 as the root and use numbers 10, 20, 30,
40.

1️⃣ Height-Balanced Tree (Root = 30)

A tree is height-balanced if the height difference between
left and right subtree is at most 1.
Example:
 30
/ \
20 40
/
10
Heights:
 Left subtree height = 2 (20 → 10)
 Right subtree height = 1 (40)
Difference = 1
✅ So this is a Height-Balanced Tree.

2️⃣ Weight-Balanced Tree (Root = 30)

A tree is weight-balanced if the number of nodes in left
and right subtrees are almost equal.
Example:
30
/ \
20 40
/
10
Number of nodes:
 Left subtree nodes = 2 (20, 10)
 Right subtree nodes = 1 (40)
Nodes are almost equal.
✅ So this is also a Weight-Balanced Tree.

✅ Simple idea
  Height-balanced → check levels (height)
 Weight-balanced → check number of nodes

Easy Difference
What is
Type
Balanced
Height- Height
Balanced (levels)
Weight- Number of
Balanced nodes

✅ One-line memory trick

 Height-balanced → compare height
 Weight-balanced → compare number of nodes

If you want, I can also show a small diagram trick teachers

use to explain this in exams (very easy to remember).

1️⃣ Height-Balanced Tree (Simple Concept)

#include <stdio.h>
#include <stdlib.h>

struct Node {
int val;
struct Node* left;
 struct Node* right;
};

// Simple BST insert

struct Node* insert(struct Node* root, int val) {
if (!root) {
struct Node* node = (struct Node*)malloc(sizeof(struct
Node));
node->val = val;
node->left = node->right = NULL;
return node;
}
if (val < root->val) root->left = insert(root->left, val);
else root->right = insert(root->right, val);
return root;
}

// In-order traversal (prints sorted values)

void inorder(struct Node* root) {
if (!root) return;
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}

int main() {
 struct Node* root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 5);
root = insert(root, 15);

printf("Height-Balanced Tree In-order: ");

inorder(root); // Output: 5 10 15 20
return 0;
}
✅ Simple idea: Just insert like BST. Conceptually, we care
about height difference, but no rotations are needed to
understand it.

2️⃣ Weight-Balanced Tree (Simple Concept)

#include <stdio.h>
#include <stdlib.h>

struct Node {
int val;
struct Node* left;
struct Node* right;
int size; // subtree size
};

// Simple BST insert

struct Node* insert(struct Node* root, int val) {
 if (!root) {
struct Node* node = (struct Node*)malloc(sizeof(struct
Node));
node->val = val;
node->left = node->right = NULL;
node->size = 1;
return node;
}
if (val < root->val) root->left = insert(root->left, val);
else root->right = insert(root->right, val);

// Update subtree size

int leftSize = root->left ? root->left->size : 0;
int rightSize = root->right ? root->right->size : 0;
root->size = 1 + leftSize + rightSize;

return root;
}

// In-order traversal
void inorder(struct Node* root) {
if (!root) return;
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
int main() {
struct Node* root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 5);
root = insert(root, 15);

printf("Weight-Balanced Tree In-order: ");

inorder(root); // Output: 5 10 15 20
return 0;
}
✅ Simple idea: Store size of subtree at each node → helps
understand weight balance.

Key Point:
 Height-Balanced → conceptually cares about height.
 Weight-Balanced → conceptually cares about number
of nodes in subtrees.
This version is short, easy to read, and enough to
understand the difference.

If you want, I can also make a tiny picture showing height

vs weight balance in one diagram — this makes it super
easy to remember.
Do you want me to do that?
(a, b)- And B-Trees.

I’ll follow the same structure and use the same numbers:
10, 20, 30, 40 with root = 30.

1️⃣ (a, b)-Tree

Idea (Simple)
An (a, b)-tree is a search tree where:
 Each node has at least a children
 Each node has at most b children
It keeps the tree balanced, so searching is fast.

Example using 10, 20, 30, 40

Root node = 30
Example structure:
[30]
/ \
[10,20] [40]
Explanation:
 Root 30 divides the data.
 Left side contains 10, 20 (smaller than 30).
 Right side contains 40 (greater than 30).
Nodes can contain more than one value.

2️⃣ B-Tree
Idea (Simple)
A B-tree is a balanced search tree where:
 A node can store multiple keys
 All leaf nodes are at the same level
B-trees are used in databases and file systems.

Example using 10, 20, 30, 40

Root node = 30
Example:
[30]
/ \
[10,20] [40]
Explanation:
 Root stores 30.
 Left node stores 10, 20.
 Right node stores 40.
 All leaf nodes are at the same level.

Easy Difference
Tree Meaning
(a, b)-
Node has between a and b children
Tree
Balanced tree where nodes store
B-Tree
multiple keys

✅ Short exam sentence

 (a, b)-Tree: A balanced search tree where each node has
between a and b children.
  B-Tree: A balanced multiway search tree where each node
can store multiple keys and children.

Sure! Let’s make (a, b)-trees and B-trees very simple and
easy to understand with examples.

1️⃣ Why these trees exist

 Normal binary trees have only 2 children per node.
 If the tree has lots of data, it can become tall, making
search slow.
 In databases or on disks, reading each node can be very
slow, so we want:
o Fewer levels in the tree
o Each node holding more than one key

2️⃣ (a, b)-trees (general multiway tree)

Definition in simple words:
 Each node can have more than 2 children.
 Each non-root node has between a and b children.
 All leaves are at the same level → tree is balanced.
How it works:
1. Search: Start at root → check node keys → go to correct
child → repeat until leaf.
2. Insert: Add key to leaf → if full → split node, push middle
key up.
3. Delete: Remove key → if node has too few keys → borrow
from neighbor or combine nodes.
Example (2, 4)-tree:
 [20, 50]
/ | \
[10] [30,40] [60,70]
 Each node has between 2 and 4 children.
 All leaves are on same level.

3️⃣ B-trees (special kind of (a, b)-tree)

 B-trees are used in databases and files.
 Each node stores many keys, enough to fill a disk block.
 Keeps all leaves at same depth → fast search and
update.
 B-tree is like a (a, b)-tree but usually with b = 2a - 1.
Example (B-tree of order 4):
[20, 50]
/ | \
[10] [30,40] [60,70]
Looks the same, but designed for disk storage so fewer disk
reads are needed.

4️⃣ Simple rules to remember

Feature (a, b)-tree B-tree
Node
Between a and b Between a and 2a-1
children
Leaves Same level Same level
Memory / general Database / disk
Use
use storage
Insert/ Split / join / share Split / join / share
Feature (a, b)-tree B-tree
Delete nodes nodes
Height O(log_a n) O(log_a n)

✅ Easy summary:
 (a, b)-tree: Balanced tree, flexible number of children per
node.
 B-tree: (a, b)-tree for databases/disks, keeps nodes full
for efficiency.
 Both keep all leaves at the same level → search is fast.

If you want, I can draw a simple diagram showing a (4,8)-

tree and a B-tree with insert/delete, which makes it super
easy to remember visually.
Do you want me to do that?

Sure! Let’s make a super simple C version of a B-tree / (a, b)-

tree just for understanding, no complex rebalancing, just
insert and search.
We’ll make:
 Node can hold up to MAX_KEYS keys
 Simple insert into leaf
 Simple search

Simple B-tree in C
#include <stdio.h>
#include <stdlib.h>
#define MAX_KEYS 3 // max keys per node (like order 4 B-tree)

typedef struct Node {

int keys[MAX_KEYS];
int n; // number of keys
struct Node* children[MAX_KEYS + 1];
int leaf; // 1 if leaf, 0 otherwise
} Node;

// Create a new node

Node* createNode(int leaf) {
Node* node = (Node*)malloc(sizeof(Node));
node->n = 0;
node->leaf = leaf;
for(int i = 0; i <= MAX_KEYS; i++)
node->children[i] = NULL;
return node;
}

// Search key in B-tree

Node* search(Node* root, int key) {
int i = 0;
while(i < root->n && key > root->keys[i]) i++;
if(i < root->n && key == root->keys[i]) return root;
if(root->leaf) return NULL;
 return search(root->children[i], key);
}

// Simple insert into leaf (no split for simplicity)

void insertLeaf(Node* node, int key) {
int i = node->n - 1;
while(i >= 0 && node->keys[i] > key) {
node->keys[i+1] = node->keys[i];
i--;
}
node->keys[i+1] = key;
node->n++;
}

// Print tree (for small trees)

void printTree(Node* node, int level) {
if(node != NULL) {
printf("Level %d [", level);
for(int i = 0; i < node->n; i++) printf("%d ", node-
>keys[i]);
printf("]\n");
if(!node->leaf) {
for(int i = 0; i <= node->n; i++)
printTree(node->children[i], level + 1);
}
}
}

// Demo
int main() {
Node* root = createNode(1); // root is leaf

insertLeaf(root, 20);
insertLeaf(root, 50);
insertLeaf(root, 10);
insertLeaf(root, 30);

printTree(root, 0);

int key = 30;

if(search(root, key))
printf("Key %d found!\n", key);
else
printf("Key %d not found!\n", key);

return 0;
}

✅ Explanation (easy)
1. Node has keys + children + leaf flag.
2. insertLeaf() inserts a key into a leaf node in sorted order.
3. search() searches recursively.
 4. For simplicity, we did not implement splitting or
merging—just enough to see how a B-tree node
works.
5. You can run this code to see a small B-tree and search.

If you want, I can make a slightly bigger version with split

for insert, still simple enough for learning, like a real (2,4)-
tree.
Do you want me to do that?

3.4 Red-Black Trees and Trees of

Almost Optimal Height

Got it! Let’s explain Red-Black Trees and Trees of Almost

Optimal Height in a super simple and easy-to-understand
way, step by step.

1️⃣ Red-Black Trees (RBT)

A Red-Black Tree is a type of self-balancing binary search
tree.
Why use it?
 Normal BSTs can become very tall → search becomes
slow.
 Red-Black Trees automatically stay balanced → search,
insert, delete all fast: O(log n).

Rules of Red-Black Tree

 1. Each node is red or black.
2. The root is always black.
3. All leaves (NULLs) are black.
4. Red nodes cannot have red children (no two reds in a
row).
5. Every path from a node to its leaves has the same
number of black nodes.
These rules ensure the tree height is about log(n) → fast
operations.

Example (Red = R, Black = B)

20(B)
/ \
10(R) 30(B)
/ \ \
5(B) 15(B) 40(R)
 Black height (number of black nodes from root to leaf) is
same for all paths.
 Red nodes cannot be next to red nodes.

Insert/Delete (Concept)
 When you insert, the tree may break red-black rules →
fix with:
1. Recoloring
2. Rotations (left/right)
 Delete also uses rotations and recoloring to maintain
balance.
2️⃣ Trees of Almost Optimal Height
 Sometimes, perfectly balanced tree is too strict to
maintain.
 Trees of Almost Optimal Height allow the tree to be
slightly unbalanced.
 This is enough to keep search fast (~log n) but makes
insert/delete simpler.
Idea:
 Height ≤ 1.44 * log2(n) instead of exact log2(n)
 Faster insert/delete than perfectly balanced trees
 Slightly taller, but still efficient

Visual comparison
Operatio
Tree Type Height Balance
ns
Normal BST Can be n None Slow if tall
Self-
Red-Black Tree ≤ 2*log2(n) O(log n)
balancing
Almost Optimal Height ~1.44*log2 Slightly
O(log n)
Tree (n) relaxed

Summary (super simple)

 Red-Black Tree: strict rules with colors → always
balanced → log(n) operations.
 Almost Optimal Height Tree: slightly relaxed balance →
simpler but still fast.
 Both are ways to keep tree height low so searching,
inserting, deleting is fast.
If you want, I can draw a small diagram showing a Red-
Black Tree before and after insertion, which makes the
rules super easy to remember visually.
Do you want me to do that?

Perfect! Let’s make a super simple Red-Black Tree program

in C that is easy to understand.
We’ll focus on:
 Nodes with colors (RED/BLACK)
 Insert without complicated rotations (just showing
colors)
 Inorder print to see tree structure
This is just for learning, not a full RBT implementation.

Simple Red-Black Tree (Learning Version)

#include <stdio.h>
#include <stdlib.h>

typedef enum { RED, BLACK } Color;

typedef struct Node {

int data;
Color color;
struct Node* left;
struct Node* right;
} Node;
// Create a new node
Node* createNode(int data, Color color) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->color = color;
node->left = node->right = NULL;
return node;
}

// Simple BST insert, mark new nodes as RED

Node* insert(Node* root, int data) {
if(root == NULL)
return createNode(data, RED); // new nodes are RED

if(data < root->data)

root->left = insert(root->left, data);
else if(data > root->data)
root->right = insert(root->right, data);

return root; // no rotations for simplicity

}

// Print tree in inorder with colors

void inorder(Node* root) {
if(root) {
 inorder(root->left);
printf("%d(%s) ", root->data, root->color == RED ? "R" :
"B");
inorder(root->right);
}
}

// Demo
int main() {
Node* root = createNode(20, BLACK); // root is BLACK

root = insert(root, 10);

root = insert(root, 30);
root = insert(root, 15);
root = insert(root, 25);

printf("Inorder traversal: ");

inorder(root);
printf("\n");

return 0;
}

✅ What this does

1. Root is BLACK.
2. All new nodes are RED.
 3. Tree inserts like a normal BST.
4. Colors are shown during inorder traversal: data(R) or
data(B).

This is perfect for beginners to understand the idea of

Red-Black Trees and colors before learning rotations and
balancing.

If you want, I can also make a tiny diagram showing this

simple tree with red/black nodes, which makes it super
easy to visualize.
Do you want me to do that?

Top-Down Rebalancing for Red-Black

Tree

No problem! Let’s make it super simple, step by step.

Top-Down Rebalancing – Easy Explanation

Goal of Red-Black Tree
 Keep tree balanced so that operations like
insert/search/delete are fast.
 Rules:
1. Root is black.
2. No red node has a red child.
 3. All paths from root to leaves have same number of
black nodes.

Problem When Inserting

If you just insert like a normal BST, you may break rule 2 (red
node has red child).

Bottom-Up Fix
 Insert node as a leaf.
 Go back up to fix any violations (rotations + recoloring).

Top-Down Fix (Easier Concept)

 Fix problems while going down, before you insert the
new node.
 Don’t need to go back up after insertion.
 You check each node as you move down:
1. If a node has two red children, change them to
black and parent to red.
→ This is called color flip.
2. If there’s a red-red problem on the way down, do
rotation immediately.

Step-by-Step Example
Start tree:
10(B)
/ \
5(R) 20(R)
Insert 15:
 1. Start at root 10(B) → OK.
2. Go right to 20(R) → Check children, nothing to fix.
3. Insert 15(R) as a child of 20.
Check rules while going down:
 If 20 had two red children → flip colors before inserting
15.
 If there’s a red-red problem → rotate before inserting 15.
Result: tree is balanced, all rules satisfied, no need to go
back up.

Summary (Easiest Way to Remember)

 Bottom-Up: Fix problems after inserting at the leaf.
 Top-Down: Fix problems while moving down the tree.
 Think: “Prevent the problem before it happens” →
top-down.

If you want, I can draw a small diagram showing top-down

insertion visually so it becomes super clear.
Do you want me to do that?
#include <stdio.h>
#include <stdlib.h>

typedef enum { RED, BLACK } Color;

typedef struct Node {

int data;
Color color;
 struct Node* left;
struct Node* right;
} Node;

// Create new node

Node* createNode(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->color = RED; // new nodes are RED
node->left = node->right = NULL;
return node;
}

// Top-Down Color Flip (simplified)

void colorFlip(Node* node) {
if(node->left && node->right) {
if(node->left->color == RED && node->right->color ==
RED) {
node->color = RED;
node->left->color = BLACK;
node->right->color = BLACK;
}
}
}

// Simple Top-Down Insert

Node* insert(Node* root, int data) {
if(root == NULL) return createNode(data);

// Move down the tree

if(data < root->data)
root->left = insert(root->left, data);
else if(data > root->data)
root->right = insert(root->right, data);

// Top-Down color fix

colorFlip(root);

return root;
}

// Inorder print with colors

void inorder(Node* root) {
if(root) {
inorder(root->left);
printf("%d(%s) ", root->data, root->color == RED ? "R" :
"B");
inorder(root->right);
}
}

int main() {
 Node* root = createNode(20);
root->color = BLACK; // root is always black

root = insert(root, 10);

root = insert(root, 30);
root = insert(root, 15);
root = insert(root, 25);

printf("Inorder traversal: ");

inorder(root);
printf("\n");

return 0;
}

Tree Structures for Sets of Intervals

Absolutely! Let’s break this down easily and make it much
simpler to understand. I’ll also give a small C program for the
core idea of Interval Trees.

Easy Explanation of Interval Trees

1. Purpose:
o Interval trees store intervals like [start, end].
o You can query a point and get all intervals that
contain it.
2. How it works:
 o Build a balanced search tree (BST) with the
midpoints of intervals or endpoints.
o Each node stores:
 A key (midpoint)
 A list of intervals containing that key
o Left child has intervals completely to the left, right
child has intervals completely to the right.
3. Querying a point:
o Start at root.
o Check if root’s intervals contain the point → output
them.
o Go left or right depending on the point vs. root key.
o Repeat until you reach a leaf.
4. Efficiency:
o Tree is balanced → height O(log n).
o If k intervals contain the point, query takes O(log n +
k) time.

Simple Example
Intervals: [1, 5], [3, 7], [6, 10]
Query point: 4 → should return [1,5] and [3,7].

Small C Program
This is very simplified just to store intervals and query a
point.
#include <stdio.h>
#include <stdlib.h>
typedef struct Interval {
int start, end;
} Interval;

typedef struct Node {

int key; // midpoint
Interval** intervals; // array of intervals
int count; // number of intervals in this node
struct Node* left;
struct Node* right;
} Node;

// Create a new node

Node* createNode(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->intervals = NULL;
node->count = 0;
node->left = node->right = NULL;
return node;
}

// Add interval to a node

void addInterval(Node* node, Interval* interval) {
node->count++;
 node->intervals = (Interval**)realloc(node->intervals, node-
>count * sizeof(Interval*));
node->intervals[node->count - 1] = interval;
}

// Insert interval into interval tree

Node* insert(Node* root, Interval* interval) {
if (!root) {
int mid = (interval->start + interval->end) / 2;
root = createNode(mid);
}

// Check if interval contains the key

if (interval->start <= root->key && interval->end >= root-
>key) {
addInterval(root, interval);
} else if (interval->end < root->key) {
root->left = insert(root->left, interval);
} else {
root->right = insert(root->right, interval);
}
return root;
}

// Query point
void query(Node* root, int point) {
if (!root) return;
 // Print intervals containing point in this node
for (int i = 0; i < root->count; i++) {
if (root->intervals[i]->start <= point && root->intervals[i]-
>end >= point) {
printf("[%d,%d] ", root->intervals[i]->start, root-
>intervals[i]->end);
}
}

if (point < root->key) query(root->left, point);

if (point > root->key) query(root->right, point);
}

int main() {
Interval i1 = {1, 5};
Interval i2 = {3, 7};
Interval i3 = {6, 10};

Node* root = NULL;

root = insert(root, &i1);
root = insert(root, &i2);
root = insert(root, &i3);

int point = 4;
printf("Intervals containing %d: ", point);
query(root, point);
 printf("\n");

return 0;
}

Output
Intervals containing 4: [1,5] [3,7]

✅ Key Points Simplified:

1. Each node stores intervals containing its key.
2. Tree is balanced (if you build with a proper BST).
3. Query checks node’s intervals + goes left/right based on
the point.
4. Works for static interval sets.

If you want, I can make a version with sorted left/right lists

like in your book, but still short and easy, so it works more
like the full interval tree.
Do you want me to do that?

Segment Trees
Sure! Let’s explain Segment Trees in a super simple way
with an easy example.

Segment Tree (Simple Explanation)

A Segment Tree is a tree used to store information about
intervals or segments of an array.
  It helps answer questions quickly like:
o Sum of numbers in a range
o Minimum or maximum in a range
Think of it as precomputing answers for all ranges in a
tree structure.

Example Array
We take your numbers:
Array: [10, 20, 30, 40]
Suppose we want a Segment Tree for range sum.

Step 1: Build the Tree

 Root stores sum of entire array → 10 + 20 + 30 + 40 =
100
 Split array in two halves: left = [10,20], right = [30,40]
Tree:
100
/ \
30 70
/ \ / \
10 20 30 40
Explanation:
 Root = sum of all elements → 100
 Left child = sum of left half → 10+20 = 30
 Right child = sum of right half → 30+40 = 70
 Leaf nodes = individual elements
Step 2: Query Example
Query: Sum of range [2,3] (20 + 30)
1. Start at root → split into left/right
2. Left = [10,20], right = [30,40]
3. Query [2,3] → covers right of left + left of right
4. Sum = 20 + 30 = 50 ✅

Step 3: Why Segment Tree is Useful

 Without segment tree → we would sum manually → O(n)
 With segment tree → we can get range sum in O(log n)

Simple Idea (Easy to Remember)

 Leaf nodes → store array elements
 Internal nodes → store combined info (sum, min, max) of
children
 Query → traverse tree → combine results

If you want, I can also show a diagram highlighting ranges

and sums for your array [10,20,30,40] like your previous
trees, which makes it super easy to remember.
Do you want me to draw that diagram?

Got it! Let’s make Segment Trees easy to understand and

give a simple C example.

Segment Trees – Simple Explanation

1. Purpose:
 o Like interval trees, segment trees keep track of
intervals [start, end].
o You can query a point and get all intervals
containing it.
2. Difference from Interval Tree:
o Segment trees store intervals in multiple nodes.
o Each interval [a,b] is split into canonical fragments
to fit in the tree.
o Because of this, space = O(n log n) (more than
interval tree’s O(n)).
3. How it works:
o Build a balanced BST of all endpoints (plus −∞ if
needed).
o Each node stores a list of intervals that include its
range.
o Query a point: follow search path down the tree,
and collect all intervals in the lists.
4. Efficiency:
o Query: O(log n + k) where k = intervals containing
the point.
o Construction: O(n log n) time.

Simplified Example
Intervals: [1,5], [3,7], [6,10]
Query point: 4 → should return [1,5] and [3,7].

Simple C Code for Segment Tree (Static Version)

#include <stdio.h>
#include <stdlib.h>
typedef struct Interval {
int start, end;
} Interval;

typedef struct Node {

int key; // BST key (midpoint)
Interval** intervals; // list of intervals covering this node
int count;
struct Node* left;
struct Node* right;
} Node;

// Create a new node

Node* createNode(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->intervals = NULL;
node->count = 0;
node->left = node->right = NULL;
return node;
}

// Attach interval to node

void attachInterval(Node* node, Interval* interval) {
node->count++;
 node->intervals = (Interval**)realloc(node->intervals, node-
>count * sizeof(Interval*));
node->intervals[node->count - 1] = interval;
}

// Insert interval into segment tree

Node* insert(Node* root, Interval* interval) {
if (!root) {
int mid = (interval->start + interval->end) / 2;
root = createNode(mid);
}

if (interval->start <= root->key && interval->end >= root-

>key) {
attachInterval(root, interval);
} else if (interval->end < root->key) {
root->left = insert(root->left, interval);
} else {
root->right = insert(root->right, interval);
}
return root;
}

// Query point
void query(Node* root, int point) {
if (!root) return;
 // Print intervals in this node containing point
for (int i = 0; i < root->count; i++) {
if (root->intervals[i]->start <= point && root->intervals[i]-
>end >= point) {
printf("[%d,%d] ", root->intervals[i]->start, root-
>intervals[i]->end);
}
}

if (point < root->key) query(root->left, point);

if (point > root->key) query(root->right, point);
}

int main() {
Interval i1 = {1, 5};
Interval i2 = {3, 7};
Interval i3 = {6, 10};

Node* root = NULL;

root = insert(root, &i1);
root = insert(root, &i2);
root = insert(root, &i3);

int point = 4;
printf("Intervals containing %d: ", point);
query(root, point);
printf("\n");
 return 0;
}

Output
Intervals containing 4: [1,5] [3,7]

✅ Key Points Simplified:

1. Segment tree stores intervals in all nodes that overlap
its canonical fragments.
2. Query a point → follow path down tree, output all
intervals in node lists.
3. Construction is static but easy to implement.
4. Space = O(n log n) because intervals may appear in
multiple nodes.

If you want, I can make a diagram showing segment tree

with intervals stored in nodes. That usually makes it super
easy to visualize.
Do you want me to do that?

Trees for the Union of Intervals

Got it! Let’s make a super simple example using exactly

10, 20, 30, 40 for Trees for the Union of Intervals.
Example Intervals
[10, 20], [20, 30], [30, 40]

Step 1: Merge Intervals (Union)

 [10,20] and [20,30] → merge → [10,30]
 [10,30] and [30,40] → merge → [10,40]
✅ Final union = [10,40]

Step 2: Build Simple Tree

[10,40]
/ \
[10,20] [30,40]
\
[20,30]
Explanation:
 Root = union of all intervals [10,40]
 Children = original intervals [10,20], [20,30], [30,40]

Step 3: Query Example

Query point: 25
1. Check root [10,40] → 25 is inside ✅
2. Check children → [20,30] contains 25 ✅
Answer: 25 lies in the union → [10,40] (and [20,30] if needed)
Query point: 5
 Root [10,40] → 5 is outside ❌
Answer: 5 is not in the union

✅ Easy Idea
 Root stores merged union of all intervals
 Children store original intervals
 Query point → check root first → then children

This is the easiest example using 10, 20, 30, 40.

If you want, I can also show a super tiny diagram of this tree
to make it visually clear like your previous tree examples.

Got it! Let’s break Trees for the Union of Intervals into a
simpler, digestible explanation with key points and a small
visualization idea.

Union of Intervals Problem

1. Goal:
o Maintain a set of intervals dynamically.
o Support insertions/deletions of intervals.
o Quickly answer:
 Measure of the union (total length covered by
all intervals).
 List of union components (all continuous
ranges covered).
2. Naive Solution:
o Sort endpoints → sweep line → count overlapping
intervals.
o Time: O(n log n)
 o Drawback: Not dynamic; re-sorting needed after
each insertion.

Measure Tree (Bentley)

 Idea: Augment a segment tree to maintain the measure
of union.
 Each node n stores:
1. measure → total length of intervals in the subtree
that intersect the node interval.
2. leftmin → minimum left endpoint of intervals in the
node.
3. rightmax → maximum right endpoint of intervals in
the node.
 Update Rules (after insert/delete):
1. Only update nodes along search paths of the
interval endpoints.
2. Recompute measure based on four cases:
Cas
Condition Measure Computation
e
n->right->leftmin < l and
1 measure = r - l
n->left->rightmax ≥ r
n->right->leftmin ≥ l and measure = (r - n->key) + n-
2
n->left->rightmax ≥ r >left->measure
n->right->leftmin < l and measure = n->right->measure
3
n->left->rightmax < r + (n->key - l)
n->right->leftmin ≥ l and measure = n->right->measure
4
n->left->rightmax < r + n->left->measure
 Complexity:
o Insert/Delete: O(log n)
 o Query Measure: O(1) (stored at root)
o Space: O(n)

Union Tree (Cheng & Janardan)

 Maintains components of the union, not just measure.
 Each node n stores pointers for its union intervals:
o leftmin, leftmax → leftmost interval in subtree
o rightmin, rightmax → rightmost interval in subtree
 Leaf nodes have:
o next → next leaf in order
o transfer → highest node whose left subtree starts at
this leaf
 Query Union:
1. Start at the smallest key (beginning of first
component).
2. Follow transfer to find end of component.
3. Follow next to start next component.
o Output-sensitive: O(k) if union has k components.
 Update (Insert/Delete):
1. Insert/Delete interval in the underlying BST.
2. Update next pointers for leaves.
3. Bottom-up update leftmin/rightmax for affected
nodes.
4. Update transfer pointers for relevant leaves.
o Complexity: O(log n) per insertion/deletion
o Space: O(n)
Key Takeaways
1. Measure tree: Fast measure queries, dynamic updates.
2. Union tree: Fast listing of union intervals, dynamic
updates.
3. Both rely on balanced BSTs over interval endpoints.
4. Complexity is excellent: O(log n) updates, O(1) measure
query or O(k) union listing query.

Simple Visualization Idea

Suppose intervals: [1,5], [3,7], [6,10]
Union components: [1,7], [6,10] → merged → [1,10]
BST with transfer pointers:
Leaves (keys): 1 3 5 6 7 10
Transfer pointers:
1 -> 10 (1 is start of union component ending at 10)
Next pointers: 1->3->5->6->7->10
 Query union: start at leaf 1 → follow transfer → end at 10.
 Done in O(1) per component.

Trees for Sums of Weighted Interval

Sure! Let’s explain Trees for Sums of Weighted Intervals in
a simple way using your numbers 10, 20, 30, 40.

Topic: Trees for Sums of Weighted Intervals

Idea (Simple)
 Sometimes each interval has a weight (like a value or
importance).
  We want a tree that can quickly find the sum of weights
of intervals covering a query point.

Step 1: Define Intervals with Weights

Let’s take intervals using your numbers:
Interv Weig
al ht
[10,20] 2
[20,30] 3
[30,40] 4

Step 2: Build the Tree

 Root can store union of intervals and sum of weights
for overlapping intervals.
 Children store individual intervals.
Simple Tree Example:
[10,40] (weight sum = 9)
/ \
[10,20] (2) [30,40] (4)
\
[20,30] (3)
Explanation:
 Root = [10,40] → sum of all weights = 2 + 3 + 4 = 9
 Children store original intervals and weights

Step 3: Query Example

Query point: 25
 1. Root [10,40] → 25 is inside ✅
2. Check children:
o [10,20] → 25 not inside ❌
o [20,30] → 25 inside ✅ weight = 3
o [30,40] → 25 not inside ❌
Answer: Sum of weights for intervals containing 25 = 3

Query point: 20
1. Root [10,40] → 20 is inside ✅
2. Check children:
o [10,20] → 20 inside ✅ weight = 2
o [20,30] → 20 inside ✅ weight = 3
o [30,40] → 20 not inside ❌
Answer: Sum of weights for intervals containing 20 = 2 + 3 =
5

Step 4: Why Useful

 Quickly find sum of weights for a query point
 Used in scheduling, resource allocation, and
computational geometry

✅ Easy Idea
1. Root → union of all intervals + sum of weights
2. Children → original intervals with weights
3. Query → check root first → traverse children → sum
weights
If you want, I can also draw a small tree diagram using
10,20,30,40 with weights to make it super easy to
visualize like your previous tree examples.
Do you want me to do that?

Here’s a clear, structured explanation of Trees for Sums of

Weighted Intervals (Section 4.4), with the main ideas and
implementation insights simplified:

Concept
 Goal: Maintain a piecewise constant function as a sum
of weighted intervals.
 Each interval [a, b[ has a weight w, and the value of the
function at x is:
[
f(x) = \sum_{[a,b[ \ni x} w
]
 Example use case: tracking resource usage, like
electricity, CPU, or bandwidth, where multiple systems
consume a constant amount during different time
intervals.

Data Structure Idea

 Use a segment tree / search tree over interval
endpoints.
 Each tree node stores a single number: summand.
o This represents the weight contribution of intervals
whose canonical decomposition includes that node.
 To evaluate the function at a point x:
1. Follow the search path for x.
 2. Sum all summands along the path.
o Query time: O(log n)

Insertion of a Weighted Interval [a, b[ with weight w

1. Ensure endpoints exist in the search tree:
o Insert a and b if missing.
o If a leaf is split, distribute the previous summand to
preserve path sums.
2. Update canonical interval decomposition nodes:
o For each node in the decomposition of [a, b[, add w
to summand.
3. Adjust summands during rotations:
o Push down the summand from a parent to its children
before rotations, then set parent summand to 0.
o This preserves the total sum along all paths.

Deletion of a Weighted Interval

 Equivalent to inserting the interval with weight -w.
 Optionally remove leaves that no longer represent
changes in the sum.

Implementation Sketch
typedef struct tr_n_t {
key_t key;
struct tr_n_t *left;
struct tr_n_t *right;
number_t summand; // sum of weights for this node
/* balancing info (e.g., AVL or Red-Black) */
} tree_node_t;

// Evaluate sum at query key x

number_t evaluate_sum(tree_node_t *tree, key_t x) {
tree_node_t *cur = tree;
number_t sum = 0;
while (cur->right != NULL) {
sum += cur->summand;
if (x < cur->key) cur = cur->left;
else cur = cur->right;
}
sum += cur->summand;
return sum;
}

// Insert interval [a, b[ with weight w

void insert_interval(tree_node_t *tree, key_t a, key_t b,
number_t w) {
// Ensure a, b exist in the tree (insert if needed)
// Follow canonical decomposition nodes:
// - add w to nodes covering [a,b[
// - subtract w for nodes to the right of b
}

Performance
Operation Time Complexity
Query sum at a
O(log n)
point
Insert interval O(log n)
Delete interval O(log n)
O(n) (only one number per
Space
node)
 Dynamic: Can handle insertions/deletions efficiently.
 Efficient for rotations: Only push down summands; no
need for complex interval lists.

Advantages
1. Simple: store only a number per node instead of full
interval lists.
2. Dynamic: supports insertions and deletions efficiently.
3. Evaluates the sum of weights at any point quickly.
4. Can be extended to maximum weight queries, though
deletions are more complex.

Visual Intuition
Suppose we have intervals:
Interv Weig
al ht
[1,4) 2
[3,6) 1
[5,7) 3
 Build a search tree on endpoints {1,3,4,5,6,7}.
 Each node’s summand:
Node Summand
1 2
3 1
4 -2
5 3
6 -1
7 -3
 Query at x = 5: sum along path → 2 + 1 + 3 = 6
This gives the sum of weights of all intervals containing 5.

If you want, I can draw a diagram showing this weighted

interval tree with summands and the canonical
decomposition, which makes the update and query process
very intuitive.
Do you want me to make that diagram?

Trees for Interval-Restricted Maximum

Sum Queries
Here’s a structured explanation of Trees for Interval-
Restricted Maximum Sum Queries (Section 4.5), simplified
and connected to the previous section on weighted interval
sums:

Concept
  Goal: Maintain a piecewise constant function ( \
sigma(x) ) (sum of weighted intervals) and support
stronger queries:
1. Interval-Restricted Maximum Query: Find (\max { \
sigma(x) : x \in [a, b[ }).
2. Argument Query: Find the (x) where this maximum is
reached.
3. Point queries: Degenerate case when ([a, b[) is a single
point.
 Update operation: Increase/decrease (\sigma(x)) for all
(x \ge a) (or in ([a, b[)) by (w).

Data Structure
 Base: Balanced search tree on the jump points of (\
sigma).
 Each node stores:
typedef struct tr_n_t {
key_t key; // x-coordinate of jump
struct tr_n_t *left;
struct tr_n_t *right;
number_t summand; // incremental change at this node
number_t partial_sum; // maximum over node interval
/* balancing info */
} tree_node_t;
 Key property: For node n, the maximum of (\sigma)
over its interval is:
[
n->partial_sum + \sum_{m \text{ on path from root to } n} m-
>summand
]
 This property allows querying max values efficiently.

Query Algorithm
1. Canonical interval decomposition:
o Break query interval [a, b[ into nodes of the canonical
decomposition.
o Maximum over [a, b[ is the max over these nodes.
2. Traversal:
o Follow search paths for a and b.
o Sum summand and partial_sum appropriately.
o Compare contributions at each subinterval to find the
max.
3. Complexity:
o Each query is O(log n) because the tree is balanced.
o Global maximum = root->summand + root-
>partial_sum (O(1) query).

Update Algorithm
To add weight w to [a, ∞[ (or [a, b[):
1. Insert endpoints a and b into the tree if missing (split
leaves if necessary).
o Copy previous leaf’s summand and partial_sum to
new leaves.
2. Push updates bottom-up:
o For [a, ∞[, add w to summand of all nodes in
canonical decomposition.
 o For [b, ∞[, subtract w to limit the interval.
3. Rotation handling:
o Before rotations, push down summands to children
and recompute partial_sum from lower neighbors.
o Ensures the max property is preserved.
4. Complexity:
o Updates are O(log n) with a balanced tree.

Left Rotation Example

void left_rotation(tree_node_t *n) {
tree_node_t *tmp_node;
key_t tmp_key;
number_t tmp1, tmp2;

// push down summands

tmp1 = n->summand; n->summand = 0;
n->partial_sum += tmp1;
tmp2 = n->right->summand; n->right->summand = 0;
n->left->summand += tmp1;
n->right->left->summand += tmp1 + tmp2;
n->right->right->summand += tmp1 + tmp2;

// perform rotation
tmp_node = n->left;
tmp_key = n->key;
n->left = n->right;
 n->key = n->right->key;
n->right = n->left->right;
n->left->right = n->left->left;
n->left->left = tmp_node;
n->left->key = tmp_key;

// recompute partial_sum
tmp1 = n->left->left->summand + n->left->left-
>partial_sum;
tmp2 = n->left->right->summand + n->left->right-
>partial_sum;
n->left->partial_sum = (tmp1 > tmp2) ? tmp1 : tmp2;
}
 Preserves σ(x) along paths and ensures partial_sum
remains correct.

Performance
Time
Operation
Complexity
Interval max query
O(log n)
[a,b[
Argument query (x of
O(log n)
max)
Update [a,b[ by w O(log n)
Global maximum O(1)
Space O(n)

Summary
  Extends weighted interval sum trees to support max
queries over intervals.
 Uses summand + partial_sum fields per node to
maintain correctness dynamically.
 Canonical interval decomposition is key to efficiently
handle queries for arbitrary intervals.
 Balanced tree rotations are carefully adapted to
maintain the max-sum property.

If you want, I can also draw a visual diagram showing how

summand and partial_sum work together for an interval
max query. This makes it much easier to understand than just
the code.
Do you want me to make that diagram?

Orthogonal Range Trees.

Here’s a clear and concise summary of Orthogonal Range
Trees for easy understanding:

1. Definition
An Orthogonal Range Tree is a data structure for efficiently
answering range queries in d-dimensional space.
 Query: Find all points inside an axis-aligned rectangle (or
box in dD space):
[
[a_1, b_1[ \times [a_2, b_2[ \times \dots \times [a_d, b_d[
]
  Output-sensitive: Time depends on the number of points
in the result (k).

2. Structure
 Recursive tree construction:
1. Build a balanced search tree on the first
coordinate.
2. Each node stores all points in its interval in a (d−1)-
dimensional orthogonal range tree for the
remaining coordinates.
3. Repeat recursively until 1D.
 C struct for a node:
typedef struct tr_n_t {
key_t key; // coordinate in current dimension
struct tr_n_t *left, *right; // BST children
struct tr_n_t *l_dim_tree; // pointer to lower-dimensional
tree
} tree_node_t;

3. Query Algorithm
1. Canonical interval decomposition:
o For the first coordinate [a1, b1[, find O(log n) nodes
covering it.
2. Recursive search in lower dimensions:
o For each node, search in the associated (d−1)-
dimensional tree.
3. Combine results:
o Join results from all subtrees to produce final list.
  Time complexity:
[
O((\log n)^d + k) \quad \text{for simple d-dimensional
tree}
]

4. Fractional Cascading (2D+ Improvement)

 Problem: In 2D, naive search costs (O((\log n)^2 + k))
due to multiple searches in related sets.
 Solution: Fractional cascading links sorted lists in
parent/child nodes.
 Result: Only O(log n + k) in 2D.
 In dD: (O((\log n)^{d-1} + k))

5. Build and Space Complexity

Type Build Time Query Time Space
O(n (log O((log n)^d + O(n (log
Simple dD
n)^d) k) n)^(d−1))
Fractional cascading O(n (log O((log O(n (log
(d ≥ 2) n)^(d−1)) n)^(d−1) + k) n)^(d−1))
 Static structure: Points do not change.
 Dynamic version: Possible using partial rebuilding.

6. Example (2D)
 Top tree: x-coordinate
 Each node has a list/tree of y-coordinates of points in its
interval
 Fractional cascading: pointers link lists to reduce repeated
searches
 [x=5]
/ \
[x=2] [x=8]
/ \ / \
[x=1] [x=3] ... [x=9]
 Each node stores points sorted by y-coordinate (linked for
fractional cascading)
 Query [2,8]x[3,7] → select canonical x-interval nodes →
search their y-lists

Key Points
 Orthogonal range trees allow efficient multi-
dimensional range queries.
 Recursively combine search trees for each dimension.
 Fractional cascading reduces query time by one
logarithmic factor.
 Output-sensitive: only spend time proportional to number
of points returned.

If you want, I can also draw a full 2D orthogonal range tree

with fractional cascading pointers, which makes it much
easier to visualize how queries work.
Do you want me to make that diagram?
Higher-Dimensional Segment Trees.
Other Systems of Building Blocks.
Range-Counting and the Semi group
Model. Kd-Trees and Related Structures

Here’s a clear, structured overview of these advanced multi-

dimensional data structures and related concepts:

1. Higher-Dimensional Segment Trees

Concept
 A segment tree in 1D efficiently answers interval
queries, e.g., sum or max over [a, b].
 In higher dimensions, we extend it recursively:
o Build a segment tree for the first dimension.
o At each node, store a segment tree for the
remaining dimensions for points in that node.
Example
 2D segment tree:
o Top-level: x-intervals
o Each node: segment tree on y-values of points in that
x-interval
 Query:
1. Find canonical nodes for x-interval
2. Query corresponding y-interval segment trees
Complexity
 Space: O(n logⁿ⁻¹ n)
 Query: O(logⁿ n) for n points in d dimensions
  Works well for sum, max, min queries, or other
associative operations

2. Other Systems of Building Blocks

Besides segment trees, other fundamental blocks for multi-
dimensional queries include:
1. Fenwick Trees / Binary Indexed Trees
o Efficient for prefix sums and updates
o Less flexible in high dimensions compared to
segment trees
2. Range Trees (Orthogonal)
o For reporting all points in a dD box
o Supports fractional cascading to reduce repeated
searches
3. Priority Search Trees
o Combines priority queues and search trees
o Efficient for top-k queries in a rectangle
4. Interval Trees
o Good for intervals with overlap queries
o Can be extended to multiple dimensions

3. Range-Counting and the Semi-group Model

Range-Counting
 Instead of reporting points in a query interval, count
them.
 Example: How many points fall in [x1,x2] × [y1,y2]?
 Typically, each node stores the number of points in its
interval.
Semi-group Model
 The stored value in nodes is from a semi-group:
o Set with an associative operation (like +, min, max)
 Supports aggregating values over ranges efficiently
 Many structures (segment trees, Fenwick trees, etc.) rely
on this property

4. KD-Trees and Related Structures

KD-Trees
 A k-dimensional binary search tree for points in dD
space
 Construction:
1. Choose a dimension (often cycling through
dimensions)
2. Split points at the median
3. Recursively build left/right subtrees
 Query:
o Efficient for range search and nearest neighbor
search
o Worst-case: O(n^(1−1/d) + k)
o Average-case: O(n^(1−1/d))
Related Structures
1. Quadtree / Octree
o Spatial decomposition of 2D / 3D space into
quadrants / octants
o Useful for sparse or geometric data
2. R-Trees
o Hierarchical bounding boxes for spatial objects
 o Widely used in GIS and databases
3. Ball Trees / VP-Trees
o Based on distances, useful for nearest neighbor
search in high dimensions

Summary Table
Query Spac
Structure Best Use Notes
Type e
O(n
Interval sum/max/ Associative
Segment Tree logⁿ⁻¹
queries min operations
n)
O(n Fractional
Orthogonal Reporting multi-d
logⁿ⁻¹ cascading
Range Tree points range
n) improves 2D

Spatial Median split per

KD-Tree range, NN O(n)
queries dimension
Hard in higher
Fenwick Tree Prefix sums sum O(n)
dimensions
query all
Interval intervals 1D or extend to
Interval Tree O(n)
overlap overlapping 2D
a point
Spatial Good for
Quadtree/
decompositi range O(n) geometric/graph
Octree
on ics
Database / rectangle Optimized for
R-Tree O(n)
GIS queries disk storage

✅ Key Idea: Most higher-dimensional data structures are

recursive constructions, building lower-dimensional
structures in each node. They differ in query type (reporting
points vs counting), space/time trade-offs, and applicability
(static vs dynamic datasets).

If you want, I can make a diagram showing all these multi-

dimensional structures together, so it’s easier to visualize
how segment trees, KD-trees, and orthogonal range
trees relate.
Do you want me to do that?

KD Trees

No problem! Let’s make Kd-Trees super simple, step by step,

with numbers only, no complicated terms.

Kd-Tree – Easy Explanation

 Think of it as a special tree for points.
 Each node splits points by x or y (we just alternate).
 This helps quickly find points inside a rectangle.
We’ll use small numbers only: 1, 2, 3, 4, 5

Step 1: Points
We take 5 points on a grid:
Poin
xy
t
A 11
B 24
C 32
D 45
E 53

Step 2: Build Tree (Easy Version)

Rule:
1. Start at root, split by x.
2. Left = points with smaller x, Right = bigger x
3. Next level → split by y, then alternate x/y at each level

Build:
 Root = point with median x = C(3,2)
 Left of root (x<3): A(1,1), B(2,4) → split by y → B(2,4)
 Right of root (x>3): D(4,5), E(5,3) → split by y → E(5,3)

Tree Structure (Easy)

C(3,2) [x-split]
/ \
B(2,4) E(5,3) [y-split]
/ /
A(1,1) D(4,5)
 Root splits x
  Next level splits y
 Children alternate

Step 3: Query Example (Easy)

Question: Find points with x = 2 to 5 and y = 2 to 4
 Root C(3,2) → inside ✅
 Left: B(2,4) → inside ✅, A(1,1) → outside ❌
 Right: E(5,3) → inside ✅, D(4,5) → outside ❌
Answer: Points = B(2,4), C(3,2), E(5,3)

✅ Super Simple Idea

1. Split x at root, then y, then x, etc.
2. Left = smaller, Right = bigger
3. Query = check rectangle at each node

If you want, I can make a diagram with numbers 1,2,3,4,5

that looks just like your previous tree examples, so it’s
super easy to understand visually.
Do you want me to draw it?