I3341 – Advanced

Algorithms
Required Knowledge / Prerequisites

 Programming Fundamentals
• Proficiency in at least one programming language (e.g., C, C++, Java, or
Python)
• Understanding of:
• Functions and recursion
• Pointers or references
• Basic memory concepts
• Ability to implement and test data structures
 Basic Data Structures
• Arrays and dynamic arrays
• Linked lists (singly and doubly linked)
• Stacks and queues
• Basic hashing concepts
 Fixed-size “array”
 Dynamic array example
 Show that a Python list grows by “resizing” (capacity idea)
 Trees and Graph Fundamentals
• Binary trees and tree terminology (root, leaf, height, depth)
• Binary search trees (BST)
• Tree traversals (inorder, preorder, postorder)
• Basic understanding of graphs (nodes, edges, connected components)
 Algorithm Analysis
• Asymptotic notation:
• Big-O, Big-Ω, Big-Θ
• Worst-case and average-case analysis
• Recurrence relations (basic)
• Introduction to amortized analysis (desirable but not mandatory)
 Recurrence Relations
 A recurrence relation is an equation that defines a sequence (or a function)
using its previous values.
 So instead of giving 𝑎𝑛 directly, you say how to compute it from earlier terms like
𝑎𝑛−1 ,𝑎𝑛−2 ,etc.
 Example 1: Arithmetic “+3”
 𝑎𝑛 = 𝑎𝑛−1 + 3, 𝑎0 = 2
 Meaning:
 Start with 𝑎0 = 2
 𝑎1 = 2 + 3 = 5
 𝑎2 = 5 + 3 = 8
 𝑎3 = 8 + 3 = 11
 Another classic example (Fibonacci)
 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 , 𝐹0 = 0, 𝐹1 = 1
 Compute:
 𝐹2 = 1 + 0 = 1
 𝐹3 = 1 + 1 = 2
 𝐹4 = 2 + 1 = 3
 Sequence: 0, 1, 1, 2, 3, 5, 8, ...
 Why we use them in Computer Science
 Recurrence relations are used a lot to describe algorithm time complexity,
especially for divide-and-conquer algorithms.
 Example: Merge Sort
 It splits the problem into 2 halves and merges them:

 Solve 2 subproblems of size 𝑛/2

 Combine/merge costs about 𝑛
 This helps us find the algorithm’s big−O (for merge sort it becomes 𝑂 𝑛 log 𝑛 ).
 Recursive (Programming / Implementation)
 A recursive function is a piece of code that calls itself to solve a problem by
breaking it into smaller parts.
 Example (Factorial recursive function in Python):
Recurrence vs. Recursive

 A recursive algorithm often leads to a recurrence relation for its running

time.
 Recurrence = how we describe/analyze.
 Recursive = how we implement/compute.
 Discrete Mathematics
• Sets and relations
• Equivalence relations
• Basic proof techniques (induction, contradiction)
• Elementary combinatorics and probability (for randomized algorithms)
 Linear Algebra & Optimization Basics
• Systems of linear equations
• Matrix representation
• Basic understanding of constraints and objective functions
(Required for Linear Programming section)
 Mathematical Maturity
• Ability to follow formal algorithm descriptions
• Comfort with abstract reasoning and complexity proofs
Binary Trees

 1. Binary Trees and Tree Terminology

 1.1 What Is a Tree?
 A tree is a hierarchical data structure consisting of:
• Nodes (elements)
• Edges (connections between nodes)
 Key properties:
• One special node called the root
• Every node (except the root) has exactly one parent
• There are no cycles
Binary Trees

 Binary Tree — Definition

 A binary tree is a tree where each node has at most two children:
 Left child
 Right child
“At most two” means: 0, 1, or 2 children.

Example (Binary Tree)

A
/\
B C
/\
D E
Binary Trees

 Tree Terminology
 Root
 The topmost node of the tree
 Has no parent

 Parent and Child

 A parent is a node that has children
 A child is a node directly connected below a parent

A is parent of B and C
B is child of A
 Leaf (External Node)
 A leaf is a node with no children

 Internal Node
 A node with at least one child
Binary Trees

 Tree Terminology
 Height
 Height of a node:
 Number of edges on the longest path from the node to a leaf

 Height of the tree:

 Height of the root

Height of D = 0
Height of B = 1
Height of A = 2
Binary Trees

 Tree Terminology
 Depth
 Depth of a node:
 Number of edges from the root to the node

Depth of A = 0
Depth of B = 1
Depth of D = 2
Binary Trees

 Formal Properties
 For a binary tree with height h:
 Maximum number of nodes:
2ℎ+1 − 1
 Minimum number of nodes:
ℎ+1
Binary Trees

 Simple Python Representation

class Node:
def __init__(self, value):
[Link] = value
[Link] = None
[Link] = None

 Example Construction

root = Node('A')
[Link] = Node('B')
[Link] = Node('C')
[Link] = Node('D')
[Link] = Node('E')
Tree Traversals (Preorder, Inorder,
Postorder)
 A tree traversal is a systematic way of visiting every node in a tree exactly
once.
 Because a tree is non-linear, there is no single natural order like arrays or
lists.
 Traversals define how recursion explores the structure.
Tree Traversals (Preorder, Inorder,
Postorder)
 Depth-First Traversals
 Preorder, Inorder, and Postorder are all Depth-First Search (DFS) traversals.
 Each traversal differs in when the root node is processed.

Traversal Order
Preorder Root → Left → Right
Inorder Left → Root → Right
Postorder Left → Right → Root
Tree Traversals (Preorder, Inorder,
Postorder)
 Example Tree
 We use the same tree for all traversals:
Preorder

 Preorder Traversal (Root → Left → Right)

 Visit Order: A → B → D → E → C
 Root is processed before children

def preorder(node):
if node:
print([Link], end=' ')
preorder([Link])
preorder([Link])
Preorder

 Iterative Preorder

def preorder_iterative(root):
if not root:
return

stack = [root]
while stack:
node = [Link]()
print([Link], end=' ')
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
Inorder

 Inorder Traversal (Left → Root → Right)

 Visit Order: D → B → E → A → C
 In BSTs, inorder traversal gives sorted order

def inorder(node):
if node:
inorder([Link])
print([Link], end=' ')
inorder([Link])
Inorder

 Iterative Inorder def inorder_iterative(root):

stack = []
cur = root

while cur is not None or stack:

# 1) Go as left as possible
while cur is not None:
[Link](cur)
cur = [Link]

# 2) Visit the node on top

cur = [Link]()
print([Link], end=' ')

# 3) Then go right
cur = [Link]
Postorder

 Postorder Traversal (Left → Right → Root)

 Visit Order: D → E → B → C → A
def postorder(node):
if node:
postorder([Link])
postorder([Link])
print([Link], end=' ')
 Traversals are the foundation for:
 Searching
 Sorting
 Deleting
 Copying
 Balancing
 Evaluating expressions
Postorder

def postorder_iterative_two_stacks(root):
 Iterative Postorder if root is None:
return

s1 = [root]
s2 = []

while s1:
node = [Link]()
[Link](node)

if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])

while s2:
node = [Link]()
print([Link], end=' ')
Binary Search Trees (BST)

 A Binary Search Tree (BST) is a binary tree that satisfies an ordering property:
 For every node N:
 All keys in the left subtree of N are less than N
 All keys in the right subtree of N are greater than N

 This property applies recursively to every subtree.

Binary Search Trees (BST)

 Why BSTs Are Important?

 BSTs allow:
 Efficient search
 Ordered data storage
 Fast insert and delete operations
 When balanced:
 Search, insert, delete → O(log n)
 When unbalanced:
 Performance degrades to O(n)
Binary Search Trees (BST)

 Searching in a BST
 At each node:
 Compare the target value with the current node
 Go left or right
 Eliminate half the tree at each step

def search(root, key):

if root is None or [Link] == key:
return root

if key < [Link]:

return search([Link], key)
else:
return search([Link], key)
Insertion in a BST

 Insertion in a BST
 Rule:
 Insert new keys as leaves
 Preserve the BST ordering property

def insert(root, key):

if root is None:
return Node(key)

if key < [Link]:

[Link] = insert([Link], key)
elif key > [Link]:
[Link] = insert([Link], key)

return root
Deletion

 BST Deletion
 Deletion has three cases:
 Leaf node → remove directly
 One child → replace node with its child
 Two children → replace with:
 inorder predecessor (max of left subtree), or
 inorder successor (min of right subtree)
BST Deletion — Inorder Predecessor
(Maximum in Left Subtree)
 Visual Example: Delete 40:
 Inorder predecessor of 40 = 30

 Replace 40 with 30:

BST Deletion — Inorder Predecessor
(Maximum in Left Subtree)
 Delete 40:
Finding the Inorder Predecessor

 Rule
 Go to left child
 Then go right as far as possible
 Python Helper Function

def find_max(node):
current = node
while [Link]:
current = [Link]
return current
 BST Deletion Using Inorder Predecessor
(Python)
else:
# Case 1: No child
if [Link] is None and [Link] is None:
return None
def delete(root, key):
if root is None:
# Case 2: One child
return root
if [Link] is None:
return [Link]
if key < [Link]:
if [Link] is None:
[Link] = delete([Link], key)
return [Link]
elif key > [Link]:
# Case 3: Two children
[Link] = delete([Link], key)
temp = find_max([Link]) # inorder predecessor
[Link] = [Link]
[Link] = delete([Link], [Link])

return root
BST Deletion Using Inorder Successor

 Initial Tree, Delete 40:

 Find the Inorder Successor

 The inorder successor is the smallest value in the right subtree.

 Inorder successor of 40 = 60
Finding the Inorder Successor

 Rule
 Go to right child
 Then go left as far as possible
 Python Helper Function

def find_min(node):
current = node
while [Link]:
current = [Link]
return current
 BST Deletion Using Inorder Successor
(Python) else:
# Case 1: no child
if [Link] is None and [Link] is None:
return None
def delete(root, key):
if root is None: # Case 2: one child
return root if [Link] is None:
return [Link]
if key < [Link]: if [Link] is None:
[Link] = delete([Link], key) return [Link]

elif key > [Link]: # Case 3: two children (successor)

[Link] = delete([Link], key) temp = find_min([Link])
[Link] = [Link]
[Link] = delete([Link], [Link])

return root
Introduction to AVL Trees

 Motivation: Why BSTs Are Not Enough

 A Binary Search Tree (BST) supports:
 Search
 Insertion
 Deletion
 All in O(h) time, where h is the height of the tree.
Introduction to AVL Trees

 The Problem with BST. A BST does not control its height.
 If keys are inserted in sorted or nearly sorted order, the BST becomes
degenerate:

 Height = n
 Operations degrade to O(n)
 BST becomes equivalent to a linked list, This is unacceptable when
performance must be guaranteed.
Introduction to AVL Trees

 Need for Self-Balancing Trees

 To guarantee O(log n) time:
 The tree height must be logarithmic
 The structure must rebalance itself

 This leads to self-balancing binary search trees.

AVL Tree

 An AVL tree is a Binary Search Tree that is strictly height-balanced.

 Named after Adelson-Velsky and Landis (1962) — the first self-balancing
BST.
 Balance Condition:
 For every node N: balance factor(N)=height(left)−height(right)
 The AVL property requires: −1≤balance factor≤1
 If this condition is violated, the tree rebalances itself.
AVL Tree

 What Does AVL Guarantee?

 Because of strict balancing:
 Tree height is always O(log n)
 Search → O(log n)
 Insert → O(log n)
 Delete → O(log n)
 These guarantees hold in the worst case, not just on average.
AVL Tree

 How AVL Trees Maintain Balance

 After:
 Insertion
 Deletion
 The tree:
 Updates heights
 Computes balance factors
 Applies rotations to restore balance
AVL Tree

 Rotations: The Key Idea

 Rotations are local restructuring operations that:
 Preserve BST order
 Reduce height imbalance
 There are four cases:
 LL (Left-Left)
 RR (Right-Right)
 LR (Left-Right)
 RL (Right-Left)
AVL Tree

 AVL vs Normal BST

Feature BST AVL

Ordering
Balance (strict)
Height Uncontrolled O(log n)
Worst-case search O(n) O(log n)
Rotations
Balance Factor Computation (AVL
Trees)
 Node Structure
class Node:
def __init__(self, value):
[Link] = value
[Link] = None
[Link] = None
[Link] = 1

 Height Function

def height(node):
if node is None:
return 0
return [Link]
Balance Factor Computation (AVL
Trees)
 Height computed recursively

def height(node):
if node is None:
return 0
return 1 + max(height([Link]), height([Link]))
Balance Factor Computation (AVL
Trees)
 Balance Factor Function

def balance_factor(node):
if node is None:
return 0
return height([Link]) - height([Link])

 For a node N: 𝐵𝐹 𝑁 = ℎ 𝑙𝑒𝑓𝑡 𝑠𝑢𝑏𝑡𝑟𝑒𝑒 − ℎ(𝑟𝑖𝑔ℎ𝑡 𝑠𝑢𝑏𝑡𝑟𝑒𝑒)

 Interpretation
 BF = 0 → perfectly balanced
 BF = +1 → left-heavy
 BF = -1 → right-heavy
 |BF| > 1 → AVL violation
Balance Factor Computation (AVL
Trees)
 Balance factor is computed after insertion or deletion
 It depends on stored heights
 Rotations are triggered only when |BF| > 1
AVL Tree Rotations

 LL (Left–Left) Rotation
 An LL imbalance happens when:
1. A node N becomes left-heavy: BF(N)>1
2. The imbalance is caused by insertion into the left subtree of N’s left child.
 𝐵𝐹 𝑁 = +2
 𝐵𝐹 𝑁𝑙𝑒𝑓𝑡 ≥ 0
AVL Tree Rotations: LL (Left–Left) Rotation

 Structural Situation (Before Rotation)

 We perform a single right rotation around N.

 After Rotation
AVL Tree Rotations: LL (Left–Left) Rotation

 Implementation

def right_rotate(N):
L = [Link]
T2 = [Link]

# Perform rotation
[Link] = N
[Link] = T2

# Update heights
[Link] = 1 + max(height([Link]), height([Link]))
[Link] = 1 + max(height([Link]), height([Link]))

return L
AVL Trees — RR (Right–Right) Rotation

 An RR imbalance happens when:

1. A node N becomes right-heavy: BF(N)<−1
2. The imbalance is caused by insertion into the right subtree of N’s right child.
 𝐵𝐹 𝑁 = −2
 𝐵𝐹 𝑁𝑟𝑖𝑔ℎ𝑡 ≤ 0
AVL Trees — RR (Right–Right) Rotation

 Structural Situation (Before Rotation)

 We perform a single left rotation around N.

 After Rotation
AVL Trees — RR (Right–Right) Rotation

 Left Rotation Code (RR Rotation)

def left_rotate(N):
R = [Link]
T2 = [Link]

# Perform rotation
[Link] = N
[Link] = T2

# Update heights
[Link] = 1 + max(height([Link]), height([Link]))
[Link] = 1 + max(height([Link]), height([Link]))

return R
AVL Trees — LR (Left–Right) Rotation

 An LR imbalance happens when:

1. A node N becomes left-heavy: BF(N)>1
2. The imbalance is caused by insertion into the right subtree of N’s left child.
 𝐵𝐹 𝑁 = +2
 𝐵𝐹 𝑁𝑙𝑒𝑓𝑡 < 0
AVL Trees — LR (Left–Right) Rotation

 Structural Situation (Before Rotation)

 An LR rotation is a double rotation:

1. Left rotation on L
2. Right rotation on N
Step 1: Left Rotation on L Step 2: Right Rotation on N
AVL Trees — LR (Left–Right) Rotation

 Python Code (LR Rotation)

 Assuming left_rotate() and right_rotate() are already defined:

def lr_rotate(N):
[Link] = left_rotate([Link])
return right_rotate(N)
AVL Trees — RL (Right–Left) Rotation

 An RL imbalance happens when:

1. A node N becomes right-heavy: BF(N)<−1
2. The imbalance is caused by insertion into the left subtree of N’s right child.
 𝐵𝐹 𝑁 = −2
 𝐵𝐹 𝑁𝑟𝑖𝑔ℎ𝑡 > 0
AVL Trees — RL (Right–Left) Rotation

 Structural Situation (Before Rotation)

 An RL rotation is a double rotation:

1. Right rotation on R
2. Left rotation on N
Step 1: Right rotation on R Step 2: Left rotation on N
AVL Trees — RL (Right–Left) Rotation

 Python Code (RL Rotation)

 Assuming left_rotate() and right_rotate() are already defined:

def rl_rotate(N):
[Link] = right_rotate([Link])
return left_rotate(N)
AVL Tree Insertion

 AVL insertion consists of four steps:

1. Insert the key as in a normal BST
2. Update the height of each node
3. Compute the balance factor
4. Restore balance using rotations if needed
 AVL Tree Insertion — Complete
Algorithm # 3. Compute balance factor
bf = height([Link]) - height([Link])
def insert(root, key): # 4. Rebalancing — USING ONLY left_rotate / right_rotate
# LL case
# 1. Normal BST insertion if bf > 1 and key < [Link]:
if root is None: return right_rotate(root)
return Node(key)
# RR case
if key < [Link]: if bf < -1 and key > [Link]:
[Link] = insert([Link], key) return left_rotate(root)
elif key > [Link]:
[Link] = insert([Link], key) # LR case
else: if bf > 1 and key > [Link]:
return root # duplicates ignored [Link] = left_rotate([Link])
return right_rotate(root)
# 2. Update height
[Link] = 1 + max(height([Link]), height([Link])) # RL case
if bf < -1 and key < [Link]:
[Link] = right_rotate([Link])
return left_rotate(root)

return root
AVL Tree Deletion

 Same philosophy as insertion, but harder, because:

 imbalance can propagate upward
 balance depends on subtree heights, not the deleted key
 BST Deletion (inside AVL delete)
 We reuse the same 3 BST deletion cases:
 No child
 One child
 Two children (using inorder successor or predecessor)
AVL Deletion Function
AVL Tree

How can a Binary Search Tree (BST) be

transformed into an AVL tree?
Red-Black Trees

 AVL trees have a drawback:

 Insertions and deletions may trigger many rotations
 This makes updates relatively expensive
 In systems with frequent updates, strict balance is not always ideal
 This raises a fundamental question:
Do we really need a tree to be perfectly balanced,
or is “balanced enough” sufficient to guarantee logarithmic time?
 Red-Black Trees were created to answer this question.
 fewer rotations
 simpler update behavior
 excellent worst-case guarantees
Red-Black Trees

 A Red-Black Tree (RBT) is a binary search tree that maintains balance using
coloring rules instead of explicit height constraints.
 Each node is colored either: Red or Black
 These colors impose structural constraints that indirectly control the height
of the tree.
Fundamental Red-Black Tree Rules

 Rule 1 — Node Coloring: Every node is either red or black.

 Rule 2 — Root Property: The root is always black. This prevents imbalance
propagating from the top.
 Rule 3 — Leaf Property: All NIL (null) leaves are considered black.
 Rule 4 — Red Property: A red node cannot have a red parent or a red child.
No two red nodes may be adjacent. This rule prevents long chains of nodes
on one side.
 Rule 5 — Black-Height Property: For any node, every path from that node to
its descendant NIL leaves contains the same number of black nodes. This is
the core balancing rule.
Fundamental Red-Black Tree Rules

 What These Rules Guarantee

 From Rules 4 and 5, we obtain:
 The longest root-to-leaf path is at most twice the shortest
 Tree height is bounded by:

ℎ ≤ 2𝑙𝑜𝑔2 (𝑛 + 1)
 Where n is the total number of nodes.
 Therefore:
 Search → O(log n)
 Insertion → O(log n)
 Deletion → O(log n)
All in the worst case.
Coloring Logic (Insertion Intuition)

 Key Design Principle

 New nodes are always inserted RED.
 Why?
 Inserting a black node would increase black height
 Red insertion preserves Rule 5 initially
 Only local violations may occur
 After insertion:
 BST ordering is preserved
 The tree may violate Rule 4 (red–red conflict)
 So rebalancing focuses on fixing color conflicts, not height differences.
Coloring Logic (Insertion Intuition)

 Red-Black Insertion Situations

 Let:
 N = newly inserted node (red)
 P = parent of N
 G = grandparent
 U = uncle (sibling of P)
Coloring Logic (Insertion Intuition)
Case 1 — Parent Is Black
 No violation
 Tree is valid
 Stop
Coloring Logic (Insertion Intuition)
Case 2 — Parent Is Red and Uncle Is Red

 Rule 4 violated
 Fix (recoloring only):
 P → Black
 U → Black
 G → Red
 Then continue checking from G.
 No rotations
 Balance preserved
 Violation may propagate upward
Coloring Logic (Insertion Intuition)
Case 3 — Parent Is Red and Uncle Is Black

 This case requires rotations.

 It has four structural subcases: LL, RR, LR, RL.
 Rotations in Red-Black Trees
 Important Distinction
 AVL trees rotate due to height imbalance
 Red-Black trees rotate due to color violations

 However: The rotation operations themselves are identical.

Coloring Logic (Insertion Intuition)
Case 3 — Parent Is Red and Uncle Is Black

 LL (Left–Left)
 Fix:
1. Right rotation on G
2. Recolor:
 P → Black
 G → Red

 RR (Right–Right)
 Fix:
1. Left rotation on G
2. Recolor:
 P → Black
 G → Red
Coloring Logic (Insertion Intuition)
Case 3 — Parent Is Red and Uncle Is Black
 LR (Left–Right)
 Fix:
1. Left rotation on P
2. Right rotation on G
3. Recolor:
 N → Black
 G → Red

 RL (Right–Left)
 Fix:
1. Right rotation on P
2. Left rotation on G
3. Recolor:
 N → Black
 G → Red
Coloring Logic (Insertion Intuition)

Situation Action
Parent black, Uncle any Do nothing
Parent red, Uncle red Recolor
LL Right rotation + recolor
RR Left rotation + recolor
LR Left + Right rotation + recolor
RL Right + Left rotation + recolor
Red-Black Tree Deletion

 Deletion in a Red-Black Tree follows the standard Binary Search Tree

deletion process, but may violate the Red-Black properties when a black
node is removed.
 In particular, the black-height property may be broken, leading to a
double-black condition.
 To restore the Red-Black invariants, the algorithm applies a sequence of
recoloring operations and structural rotations, which may propagate
toward the root.
 Despite its complexity, Red-Black Tree deletion maintains a worst-case time
complexity of O(log n) and generally requires fewer rotations than deletion
in AVL trees.
Red-Black Tree Insertion
implementation-level
 node structure:

RED = "RED"
BLACK = "BLACK"

class Node:
def __init__(self, key):
[Link] = key
[Link] = RED # new nodes are RED
[Link] = None
[Link] = None
[Link] = None
Red-Black Tree Insertion
implementation-level
 Checking a Coloring Violation:
 In Red-Black insertion, the only initial violation is: A red node having a red
parent

def has_red_red_violation(node):
return (
node is not None and
[Link] is not None and
[Link] == RED and
[Link] == RED
)
 Red-Black Tree Insertion
implementation-level
 Fixing Coloring Violations (Insertion Fix-Up)
# Case 1: Uncle is RED → recolor
if uncle is not None and [Link] == RED:
[Link] = BLACK
[Link] = BLACK
def fix_insert(root, node): [Link] = RED
node = grandparent
while node != root and [Link] == RED: else:
# Case 2: LR → rotate left on parent
parent = [Link] if node == [Link]:
grandparent = [Link] node = parent
root = left_rotate(root, node)
# Parent is left child
if parent == [Link]: # Case 3: LL → rotate right on grandparent
uncle = [Link] [Link] = BLACK
[Link] = RED
root = right_rotate(root, grandparent)
 Red-Black Tree Insertion
implementation-level
 Fixing Coloring Violations (Insertion Fix-Up)
else:
# Case 2 (mirror): RL → rotate right on
# Parent is right child (mirror case) parent
else: if node == [Link]:
uncle = [Link] node = parent
root = right_rotate(root, node)
# Case 1 (mirror): Uncle is RED
if uncle is not None and [Link] == RED: # Case 3 (mirror): RR → rotate left on
[Link] = BLACK grandparent
[Link] = BLACK [Link] = BLACK
[Link] = RED [Link] = RED
node = grandparent root = left_rotate(root, grandparent)

# Rule 2: Root must be black

[Link] = BLACK
return root
Red-Black Tree Insertion
implementation-level
 Red-Black insert wrapper

def rb_insert(root, key):

new_node = Node(key) # new node is RED by default

# Step 1: BST insert

root = bst_insert(root, new_node)

# Step 2: Fix Red-Black violations

root = fix_insert(root, new_node)

return root
Red-Black Tree Deletion

 In insertion, we add a red node and may violate:

 Rule 4 (red–red)
 In deletion, we may remove a black node, which is worse because it can
violate:
 Rule 5 (equal black height on all paths)
 Deletion affects global balance, not just a local color conflict.
 Black Height
 Every path from a node to its descendant NIL leaves must contain the same
number of black nodes. This number is called the black height.
Red-Black Tree Deletion
Case A — Deleting a RED node
 Safe
 No rule is violated
 No fixing needed
Red-Black Tree Deletion
Case B — Deleting a BLACK node
 Dangerous
 Black height decreases on one path
 Tree becomes invalid
 This is the only problematic case.
 The “Double Black” Concept
 When a black node is deleted:
 One path has one less black
 We represent this imbalance as a double-black node
Red-Black Tree Deletion
Case B — Deleting a BLACK node
 Let:
 DB = double-black node (or NIL)
 P = parent
 S = sibling of DB

 The entire fix process depends on the sibling S.

Red-Black Tree Deletion
Case B — Deleting a BLACK node
 Case 0 — x is the root
 Condition
 x is the root
 Action
 Remove the extra black
 Color root BLACK
 STOP
Red-Black Tree Deletion
Case B — Deleting a BLACK node
 Case 1 — Sibling is RED
 Fix
1. Recolor:
 S → BLACK
 P → RED

2. Rotate toward DB (here: left rotation on P)

 Result (after fix)
 DB still exists
 But sibling is now black
 We reduced the problem to Case 2, 3, or 4
 Continue fixing
Red-Black Tree Deletion
Case B — Deleting a BLACK node
 Case 2 — Sibling s is BLACK and both children are BLACK
 This is the case that can propagate DB upward.
 Before

 Fix
1. Recolor: s → RED
2. Move the “extra black” up: set x = p
 After
 Now two subcases:
 If original p was RED, then when it becomes DB you can simply make it BLACK
and STOP.
 If original p was BLACK, DB continues upward (loop repeats).
Red-Black Tree Deletion
Case B — Deleting a BLACK node
 Case 3 — Sibling s is BLACK, near child is RED, far child is BLACK
 For x on the left:
 near child = SL
 far child = SR
 Before
 Fix (convert to Case 4)
1. Recolor: c → BLACK, s → RED
2. Rotate right at s
 After
 Now the new sibling of x is c(B), and it has a far red child (the red is on the
“outside” after conversion), so we are in Case 4 next.
 (That “(.)” is the subtree that was between c and s; it doesn’t affect the
case logic.)
Red-Black Tree Deletion
Case B — Deleting a BLACK node
 Case 4 — Sibling s is BLACK, far child is RED
 This is the final resolving case (it eliminates DB).
 Before
 Fix
1. [Link] = [Link]
2. [Link] = BLACK
3. [Link] = BLACK
4. Rotate left at p
5. DB is removed (x becomes normal black / NIL)

 After
 DB is gone, tree satisfies all Red-Black properties again, STOP.
Splay Trees

 A Splay Tree is a:
 Binary Search Tree (BST)
 Self-adjusting
 Not explicitly balanced
 Key idea:
 Every time you access a node, you move it to the root
 This operation is called splaying.
Splay Trees

 Splay trees are designed to:

 Exploit temporal locality
 Make frequently accessed elements faster
 Avoid storing balance information (unlike AVL / Red-Black)
 They are good when:
 Some keys are accessed much more often than others
 Access patterns are non-uniform
Splay Trees

 Splaying = moving a node x to the root using rotations.

 This happens after:
 Search
 Insert
 Delete
Splaying cases

 Assume:
 x = accessed node
 p = parent
 g = grandparent
 Case 1: ZIG
 x has no grandparent (parent is root)
 Single rotation
Splaying cases

 Case 2: ZIG–ZIG
 x and p are both left children(or both right children)
 Two rotations (same direction)
Splaying cases

 Case 3: ZIG–ZAG
 x is left child, p is right child (or vice versa)
 Two rotations (opposite directions)
Splay Trees Search operation

 Steps:
1. Perform normal BST search
2. Splay the accessed node to the root
 Result:
 Recently searched node becomes root
 Frequently used nodes stay near top
 Amortized time: O(log n)
Splay Trees Insert operation

 Steps:
1. Insert like normal BST
2. Splay the inserted node to the root
 Effect:
 New elements become fast to access
 Tree reorganizes automatically
Splay Trees Delete operation

 Steps:
1. Splay the node to delete to the root
2. Remove the root
3. Join left and right subtrees:
 Splay the maximum of left subtree
 Attach right subtree
Splay Trees POS

 Why Splay Trees work

 Frequently accessed nodes move upward
 Rarely used nodes sink downward
 Tree adapts to real usage, not theoretical balance
 This is called Self-adjusting behavior
 When to use Splay Trees
 Access pattern is repetitive
 Memory overhead must be minimal
 Amortized performance is acceptable
Example: Splay Tree with Frequent
Access
 Initial tree
 Insert the following keys in this order: 50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45
 Resulting BST:

 Frequently accessed nodes:

 We will repeatedly access: 25 and 45
Example: Splay Tree with Frequent
Access
 Access 1: search(25) → splay(25)
 25 is right child of 20
 20 is left child of 30 → ZIG–ZAG
 Then ZIG with 50
 Result (25 MUST be root)
Example: Splay Tree with Frequent
Access
 Access 2: search(45) → splay(45)
 45 right of 40
 40 right of 30 → ZIG–ZIG
 Then ZIG–ZAG with 50
 Then ZIG with 25
 Result (45 MUST be root)
Example: Splay Tree with Frequent
Access
 Access 3: search(25) → splay(25)
 25 is left child of root → ZIG
Example: Splay Tree with Frequent
Access
 Access 4: search(45) → splay(45)
 45 is right child of root → ZIG
Example: Splay Tree with Frequent
Access
 After every access, the accessed node is root
 Frequently accessed nodes (25 and 45) stay near the surface
 Only one rotation is needed when they are already shallow
 No balance information stored
 Tree adapts strictly to access pattern
B-trees
 A B-Tree is a balanced multi-way search tree (not binary) designed to keep
the tree very short by storing many keys in each node.
 Why this matters:
 On disk (databases, file systems), reading one node often means reading one
disk block/page.
 Disk I/O is expensive.
 So B-Trees pack many keys into one node → fewer levels → fewer disk reads.
 All leaves are at the same depth (perfect height balance).
 B-trees

 In a B-Tree, each node contains multiple sorted keys:

 Those keys act like separators that split the number line into ranges.
 The fundamental separator rule: If a node contains k keys, then it has k + 1 children.
 Example:

 C0 contains keys < 10

 C1 contains keys 10 < key < 20
 C2 contains keys 20 < key < 30
 C3 contains keys > 30
B-trees

 A B-Tree is defined by a fixed integer t ≥ 2, called the minimum degree.

 It controls how full a node is allowed to be.
 It prevents nodes from becoming too empty.
 It guarantees balance and small height.
 Maximum keys in any node: maxKeys = 2t − 1
 Minimum keys in any non-root node: minKeys = t − 1
 Maximum children: maxChildren = 2t
 Minimum children in any non-root internal node: minChildren = t
 Root is special:
 root may have fewer than t−1 keys (it can have 1 key even if t is bigger).
 root can be a leaf (tree with one node).
B-Tree properties

 A tree is a valid B-Tree of minimum degree t if:

1. Each node stores keys in sorted order.
2. If a node has k keys, it has k+1 children (unless it is a leaf).
3. All leaves are at the same depth.
4. Every node has at most 2t−1 keys.
5. Every non-root node has at least t−1 keys.
6. Every internal non-root node has at least t children.
7. The root has at least 1 key (unless the tree is empty).
 These rules are what keep the tree balanced and shallow.
Concrete capacity example (fix t = 3)

 Let’s choose: t = 3
 Then:
 maxKeys = 2t − 1 = 5
 minKeys = t − 1 = 2 (for non-root nodes)
 maxChildren = 2t = 6
 minChildren = t = 3 (for internal non-root nodes)
 So each node can contain:
 2 to 5 keys (except root can have 1 to 5 keys)
 Example nodes:
Search in a B-Tree

 To search for a key x:

 At each node:
1. Compare x with the node’s keys (binary search inside the node is common).
2. If found → success.
3. If not found:
1. Determine which interval x belongs to,
2. Follow that child pointer,
3. Repeat.
Example search (t = 3)

 Suppose root is:

 Searching for 45:
 45 is between 30 and 60 → go to middle child.
 Middle child:
 45 found.
 Cost
 Height is 𝑂(𝑙𝑜𝑔𝑡 𝑛)(base depends on branching factor).
 Searching inside each node is 𝑂(𝑙𝑜𝑔2 (2𝑡)) (binary search).
Insertion in B-Trees

 Core principle Never descend into a full child.

 Because if the child is already full and you go down into it, you might get
stuck when you need to insert.
 Standard insertion strategy (“split on the way down”)
1. If root is full, split it (tree height increases by 1).
2. Starting from root:
 Before descending into a child, if that child is full → split it.
 Then choose the correct child and descend.

3. Insert into a non-full leaf.

 This guarantees you will always have space when you reach the leaf.
Insertion in B-Trees

 What “splitting a node” means

 Assume t = 3 → max keys = 5.
 A full node has 5 keys:
 Split operation:
1. Middle key k3 moves up to the parent.
2. Left node keeps the smallest t−1 = 2 keys:
3. Right node keeps the largest t−1 = 2 keys:

 So splitting:
 promote 30
 left: [10|20]
 right: [40|50]
Full insertion example (t = 3)

 We will insert these keys in order: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
 Step A: Insert first 5 keys (fit in root)
 After inserting 10,20,30,40,50:
 Step B: Insert 60 (root is full → split root first)
 Split root: promote 30
 Tree becomes:
 Now insert 60:
 60 > 30 → go right
 right node [40|50] has space → insert into it:
Full insertion example (t = 3)

 Step C: same for 70 and 80 Insertion:

 Step D: Insert 90 (must split the full child before descending)

 Before inserting 90, the right child is full → split it.
 Split [40|50|60|70|80]:
1. promote 60 into parent
2. left child: [40|50]
3. right child: [70|80]

 Parent was [30], becomes [30|60]:

Full insertion example (t = 3)

 Now insert 90:

 90 > 60 → go to rightmost child [70|80]
 Insert

 Step F: Insert 100

 go rightmost child, insert:

 This is a valid B-Tree (t=3), height is small, leaves are same level.
B-Trees are always balanced

 Insertion happens at leaves.

 When a node overflows, it splits.
 The split may push a key upward, possibly causing parent overflow.
 This overflow can propagate up to the root.
 If the root splits, height increases by exactly 1.
B-Tree deletion rules

 Rule 0 (the golden rule): “Fix before you go down”

 Before descending into a child C, if C has t−1 keys (for t=2 → 1 key), you must first
make sure C will have at least t keys (for t=2 → 2 keys) by doing:
 Borrow from a sibling (if possible), otherwise
 Merge with a sibling.

 This prevents underflow later.

B-Tree deletion rules

 Rule 1: Deleting a key from a LEAF (easy case)

 If the key is in a leaf and the leaf has ≥ t keys (for t=2 → at least 2 keys), delete it
directly.
 Example
 Leaf has 2 keys: [ 3 5 ]
 Delete 5: [ 3 ]
B-Tree deletion rules

 Rule 2: Borrow from LEFT sibling (before descending into a minimal child)
 You want to descend into the right child (minimal) to delete ⟦7⟧.
 Before (delete ⟦7⟧ is inside right child):
 Borrow from left sibling:
 parent key 6 goes down to the right child
 left sibling max (5) goes up to parent
 After borrow (now proceed to delete ⟦7⟧):
 Now delete ⟦7⟧ in the leaf:
B-Tree deletion rules

 Rule 3: Borrow from RIGHT sibling (before descending into a minimal child)
 You want to descend into the left child (minimal) to delete ⟦4⟧.
 Before:

 Borrow from right sibling.

 After borrow

 Delete ⟦4⟧:
B-Tree deletion rules

 Rule 4: Merge (when you cannot borrow)

 You want to delete ⟦4⟧ from the left child, but both children are minimal so
you must merge first.
 Before

 Merge: [⟦4⟧] + 6 + [7] → [ ⟦4⟧ 6 7 ] (parent becomes empty; if parent is root,

height shrinks)
 After merge:

 Now delete ⟦4⟧:

B-Tree deletion rules

 Rule 5: Deleting a key from an INTERNAL node (3 subcases)

 5A: Replace internal key by PREDECESSOR (left child has ≥ 2 keys)
 Delete internal key ⟦10⟧:
 Before:

 Left child has 3 keys, so predecessor is 9. Replace ⟦10⟧ by 9, then delete 9 in left
leaf:
 After:
B-Tree deletion rules

 5B: Replace internal key by SUCCESSOR (right child has ≥ 2 keys)

 Before:

 Right child has 3 keys, successor is 11. Replace ⟦10⟧ by 11, then delete 11 in right
leaf:
 After:
B-Tree deletion rules

 5C: Merge children with internal key (both children minimal)

 Delete internal key ⟦10⟧:
 Before:

 Both children minimal → merge: [8] + ⟦10⟧ + [12] → [ 8 ⟦10⟧ 12 ]

 Then delete ⟦10⟧:
Treaps

 A treap (tree + heap) is a binary search tree (BST) where every node also
has a priority, and the tree is kept balanced by maintaining a heap
property on priorities
 Treap rules
 Each node stores: (key, priority)
 BST property (by key)
 Left subtree keys < key
 Right subtree keys > key

 Heap property (by priority)

 Common choice: min-heap on priority
 A node’s priority is ≤ its children’s priorities
(so smaller priority floats upward)

 Important: priorities are usually assigned randomly, which makes the treap
balanced on average.
Treaps

 How insertion works

1. Insert the new key like a normal BST (as a leaf).
2. If heap property is violated (new priority is too small), rotate the node
upward until the heap property is restored.
Treaps insertion example

 Full insertion example

 Use min-heap priorities (smaller = higher).
 Insert these nodes in order:
1. 50(p=50)
2. 30(p=80)
3. 70(p=60)
4. 20(p=10)
5. 40(p=30)
 Write nodes as key(priority)
Treaps insertion example

 Insert 50(50)

 Insert 30(80) (BST left of 50, heap ok)

 Insert 70(60) (BST right of 50, heap ok)

 Insert 20(10) (BST: 20 < 50 < 30 ⇒ left of 30)

Treaps insertion example

 Heap violation: 20(10) has smaller priority than parent 30(80) ⇒ rotate right
at 30:

 Still violation: 20(10) priority < 50(50) ⇒ rotate right at 50:

 Now heap + BST both correct.

Treaps insertion example

 Insert 40(30)
 BST path: 20 → right to 50 → left to 30 → right (since 40 > 30)
 Before fixing heap:

 Heap violation: 40(30) priority < 30(80) ⇒ rotate left at 30:

Treaps insertion example

 Heap violation again: 40(30) priority < 50(50) ⇒ rotate right at 50:

 Final treap after all insertions.

 What you should notice
 We inserted by key (BST), then fixed by priority (heap).
 Nodes with small priority rise toward the root.
 If priorities are random, treap height is O(log n) expected.
Trees with partial rebuilding

 These are search trees that do not rebalance after every update (like AVL /
Red-Black). Instead, they:
 allow the tree to become somewhat unbalanced, and
 when imbalance becomes “too much,” they rebuild only a part of the tree (a
subtree) into a perfectly balanced form.
 That’s why it’s called partial rebuilding: you rebuild a subtree, not the whole
tree, and not every time.
Trees with partial rebuilding:
Scapegoat Tree
 The main example: Scapegoat Tree
 A scapegoat tree is a BST that keeps balance using occasional subtree
rebuilds.
1
 It chooses a constant α (alpha) with: <𝛼<1
2
2
 (common: 𝛼 = 3)

 For any node u, define: size(u) = number of nodes in subtree rooted at u

 A node is “too unbalanced” if one side is too heavy, e.g.:
𝑠𝑖𝑧𝑒 𝑙𝑒𝑓𝑡 𝑢 > 𝛼. 𝑠𝑖𝑧𝑒(𝑢) or 𝑠𝑖𝑧𝑒 𝑟𝑖𝑔ℎ𝑡 𝑢 > 𝛼. 𝑠𝑖𝑧𝑒(𝑢)
 When this happens, u is a scapegoat.
 Fix: rebuild the subtree of u into a perfectly balanced BST.
Trees with partial rebuilding:
Scapegoat Tree
 What “rebuilding a subtree” means
 If a scapegoat subtree has m nodes:
1. Do an inorder traversal → get keys in sorted order (O(m))
2. Build a balanced BST from that sorted list (O(m))
3. Replace the old subtree with the new balanced one
 So rebuilding cost is: O(m)
How do I build a perfectly balanced
BST from a sorted list?
 Idea
 To get a perfectly (as balanced as possible) BST from a sorted list:
1. Pick the middle element as the root.
2. Recursively build:
 left subtree from the left half
 right subtree from the right half
 This guarantees the height is minimal (balanced).
Implementation

buildBalancedBST(arr, l, r):
if l > r: return null
mid = (l + r) // 2
node = new Node(arr[mid])
[Link] = buildBalancedBST(arr, l, mid-1)
[Link] = buildBalancedBST(arr, mid+1, r)
return node
Example

 Build a balanced BST from the sorted list: 1 2 3 4 5 6 7 8 9 10

5
/ \
2 8
/ \ / \
1 3 6 9
\ \ \
4 7 10
Amortized analysis

 A rebuild can be expensive (maybe O(n) sometimes).

 But amortized analysis proves:
 Over a long sequence of operations, the average cost per operation is still small
(typically O(log n)).
 A subtree rebuild of size m happens only after many insertions/deletions
made that subtree heavy on one side again.
 So the rebuild cost can be “paid for” by charging a small extra cost to
those many operations.
 That’s the amortized idea: rare expensive operations are spread out across
many cheap ones.
Skip lists: randomized data structure

 A skip list is a sorted linked-list structure that uses random “levels” so

search/insert/delete become O(log n) expected, like a balanced tree but
simpler.
 What a skip list is:
 Start with a normal sorted linked list (Level 0).
 Then add “express lanes” above it:
 Level 1 skips more nodes
 Level 2 skips even more
 … until a sparse top level
 Each element appears in Level 0, and with probability 1/2 it also appears in
Level 1, with probability 1/4 in Level 2, etc. (coin flips).
Skip lists: randomized data structure

 Small example structure

 Keys: 1, 3, 4, 7, 9, 12, 15, 18
 Assume random levels assigned like this (just an example):
 1: height 1 (only L0)
 3: height 2 (L0, L1)
 4: height 1
 7: height 3 (L0, L1, L2)
 9: height 1
 12: height 2
 15: height 1
 18: height 2
Skip lists: randomized data structure

 How SEARCH works

 Search for 15:
 Start at top-left (L2 at -∞).
 On L2
 Can we go right to 7? yes (7 ≤ 15) → move to 7
 Next on L2 is +∞, too big → go down to L1 at key 7
 On L1 (at 7)
 Move right to 12 (12 ≤ 15) → go to 12
 Next is 18 (18 > 15) → go down to L0 at key 12
 On L0 (at 12)
 Move right: 15 → found.
 That’s why it’s fast: you skip big chunks using higher levels.
Skip lists: randomized data structure

 INSERT (how levels are created)

 To insert a key x:
 Do a search-like walk to find where x belongs (keep track of “update pointers” at
each level).
 Insert x into Level 0.
 Flip a coin:
 heads → also insert into Level 1
 heads again → also insert into Level 2
 stop when tails appears

 That random height keeps the structure balanced “on average”.

 DELETE
 To delete x : Find it by search path
 Remove it from every level where it appears