Advanced Data
Structures
• Bellman-Ford Algorithm, Segment Tree,
Red-Black Tree, Expression Tree, Binary
Indexed Tree, B-Tree
-Prokash Barman
Bellman-Ford Algorithm
Segment Tree
Red-Black Tree
Expression Tree
Binary Indexed Tree (Fenwick Tree)
B-Tree
Table of Conclusion
Contents Q&A
References
Bellman-Ford
Algorithm
o Purpose: Find shortest
paths in graphs with
negative edge weights
o Key features: Handles
negative weights,
detects negative cycles
Bellman-Ford
Algorithm -
Key Steps
o Initialization:
§ Set distance to source
vertex to 0
§ Set distances to all other
vertices to infinity
§ Set predecessors to null
Bellman-Ford Algorithm - Relaxation
Repeat for |V| - 1 iterations:
For each edge (u, v) with weight w:
If d[u] + w < d[v], update d[v] to d[u] + w and
set π[v] to u
Bellman-Ford
Algorithm - Negative
Cycle Detection
o Negative Cycle
Detection:
§ Perform one more pass:
§ For each edge (u, v) with
weight w:
§ If d[u] + w < d[v], a
negative cycle exists
Bellman-Ford Algorithm - Pseudocode
function BellmanFord(G, s):
# G is the graph and s is the source vertex
# Step 1: Initialization
for each vertex v in G:
if v is s:
d[v] = 0
else:
d[v] = ∞
π[v] = null
Bellman-Ford Algorithm - Pseudocode
# Step 2: Relaxation
for i from 1 to |V| - 1:
for each edge (u, v) in G:
if d[u] + w(u, v) < d[v]:
d[v] = d[u] + w(u, v)
π[v] = u
# Step 3: Negative Cycle Detection
for each edge (u, v) in G:
if d[u] + w(u, v) < d[v]:
return "Negative cycle detected"
return d, π
Time
Complexity: O(VE)
Bellman-
Ford Space
Algorithm - Complexity: O(V)
Complexity
Segment Tree
o Purpose: Efficient range
queries and updates
over an array
o Key features: Each node
represents an interval
Segment Tree -
Key Concepts
§ Root represents the entire
array
§ Leaves represent single
elements
§ Intermediate nodes
represent the union of
their children's intervals
Segment Tree -
Operations
o Build: Construct the segment tree from
the input array
o Query: Retrieve information from a
range of indices
o Update: Modify a single element or a
range of elements
function buildSegmentTree(arr):
# Construct the segment tree from the
array
function querySegmentTree(node, left,
right, queryLeft, queryRight):
# Perform a range query
Segment
Tree - function updateSegmentTree(node,
Pseudocode index, value):
# Update the value at a specific index
Build: O(n)
Query: O(log n)
Segment
Tree -
Complexity Update: O(log n)
Red-Black
Tree
o Purpose: Self-balancing
binary search tree
o Key features: Maintains
balance through coloring
nodes
Every node is either red or black
The root is always black
Red-Black If a node is red, its children must be
Tree - black
Properties Every path from a node to its
descendants' leaves contains the same
number of black nodes
Insert: Add a new node
while maintaining red-black
properties
Delete: Remove a node
while maintaining red-black
Red-Black properties
Tree -
Operations Search: Find a node with a
specific key
Red-Black Tree - Pseudocode
function insertRedBlackTree(node, key):
# Insert a new node
function deleteRedBlackTree(node, key):
# Delete a node
function searchRedBlackTree(node, key):
# Search for a node
Insert: O(log n)
Delete: O(log n)
Red-Black
Tree -
Search: O(log n)
Complexity
Expression
Tree
o Purpose: Represent and
evaluate arithmetic
expressions
o Key features: Leaves
represent operands, internal
nodes represent operators
Expression
Tree - Key
Concepts
LEAVES: INTERNAL NODES:
OPERANDS OPERATORS
Expression
Tree -
Operations
BUILD: CONSTRUCT THE EVALUATE: COMPUTE THE
EXPRESSION TREE FROM AN VALUE OF THE EXPRESSION
EXPRESSION
Expression Tree - Pseudocode
• function buildExpressionTree(expression):
• # Construct the expression tree
•
• function evaluateExpressionTree(node):
• # Evaluate the expression
Build: O(n)
Expression Evaluate: O(n)
Tree -
Complexity
Red-Black Tree:
Efficient search, insert,
and delete operations
Expression
Tree vs. Expression Tree:
Red-Black Represent and evaluate
Tree arithmetic expressions
Binary Indexed
Tree (Fenwick Tree)
o Purpose: Efficient
cumulative frequency
counting and updating
o Key features: Each
element stores
cumulative frequency of
a range
Binary Indexed
Tree - Key
Concepts
o Structure:
§ Represented as an
array
§ Each element stores
cumulative frequency
Build: Construct the binary
indexed tree from an array
Query: Retrieve the
Binary cumulative frequency up to
Indexed a given index
Tree -
Operations Update: Modify the
frequency of an element
Binary Indexed Tree - Pseudocod
Binary Indexed Tree - Pseudocode
• function buildBinaryIndexedTree(arr):
• # Construct the binary indexed tree
•
• function queryBinaryIndexedTree(index):
• # Retrieve the cumulative frequency
• function updateBinaryIndexedTree(index, value):
• # Update the frequency of an element
Build: O(n)
Binary Query: O(log n)
Indexed
Tree -
Complexity Update: O(log n)
B-Tree
01 02
Purpose: Self- Key features:
balancing tree Efficient
for sorted search, insert,
data and delete
operations
o Structure:
B-Tree - § Each node can have multiple
children
Key § Each node (except root) must have
at least m/2 children
Concepts § The root must have at least 2
children
Search: Find a key
B-Tree - in the B-tree
Operations
Insert: Add a new
key to the B-tree
Delete: Remove a
key from the B-tree
: B-Tree - Pseudocode
• function searchBtree(node, key):
• # Search for a key
• function insertBtree(node, key):
• # Insert a new key
• function deleteBtree(node, key):
• # Delete a key
B-Tree -
Complexity SEARCH: O(LOG INSERT: O(LOG
N) N)
DELETE: O(LOG
N)
