B-Tree Implementation with Primality Testing

This repository contains a comprehensive implementation of a B-Tree data structure with integrated primality testing functionality, developed as part of FIT3155 Assignment 3.

Overview

The implementation consists of three main components:

1. Probabilistic Primality Testing using the Miller-Rabin algorithm
2. B-Tree Data Structure with full insertion, deletion, and query operations
3. Command-Line Interface for executing various tree operations

Table of Contents

• Core Components
  • Probabilistic Primality Testing
  • B-Tree Implementation
  • Command Processing
• Data Structures
• Key Algorithms
• Usage
• Supported Operations
• File Structure
• Examples

Core Components

Probabilistic Primality Testing

The implementation includes a robust primality testing function using the Miller-Rabin algorithm:

def probabilistic_primality_test(n: int, k: int = 100) -> bool

Features:

• Quick filtering: Performs initial checks for small primes and even numbers
• Modular exponentiation: Efficiently computes large powers using exponentiation by squaring
• Miller-Rabin algorithm: Probabilistic test with configurable iterations (default: 100)
• High accuracy: With k=100 iterations, the probability of error is negligible

Algorithm Steps:

1. Handle special cases (2, 3, even numbers, numbers < 2)
2. Test divisibility by small primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
3. Apply Miller-Rabin test for remaining candidates
4. Use modular exponentiation for efficient computation

B-Tree Implementation

The B-Tree is implemented as a generalized balanced search tree with configurable minimum degree t.

Key Properties:

• Minimum degree t: Each node has at least t-1 keys (except root)
• Maximum keys: Each node has at most 2t-1 keys
• Balanced structure: All leaf nodes are at the same level
• Sorted order: Keys within nodes are sorted, supporting efficient range queries

Classes:

BtreeElem

Represents individual elements/keys in the tree:

class BtreeElem:
    def __init__(self, key: int = None):
        self.key = key                    # The stored value
        self.left_subtree = None          # Left child pointer
        self.right_subtree = None         # Right child pointer

BtreeNode

Represents nodes in the B-tree:

class BtreeNode:
    def __init__(self, t):
        self.t = t                        # Minimum degree
        self.arr = [None] * (2 * t - 1)   # Array of BtreeElem objects
        self.degree = 0                   # Current number of keys
        self.is_leaf = True               # Leaf node flag

Btree

Main B-tree class with all operations:

class Btree:
    def __init__(self, t = 2):
        self.root = self.BtreeNode(t)     # Root node
        self.t = t                        # Minimum degree
        self.num_keys = 0                 # Total key count

Command Processing

The main program (a3() function) processes commands from input files:

Input Format:

• t: Minimum degree for B-tree
• keystoinsert.txt: Keys to insert (one per line)
• keystodelete.txt: Keys to delete (one per line)
• commands.txt: Operations to execute

Execution Flow:

1. Parse command-line arguments
2. Read input files
3. Create B-tree with specified minimum degree
4. Insert all keys from input file
5. Delete specified keys
6. Execute commands and write results to output.txt

Data Structures

B-Tree Node Structure

BtreeNode (t=3 example):
┌─────────────────────────────────┐
│  [key1] [key2] [key3] [key4]    │  ← Array of BtreeElem (max 2t-1 = 5)
│     │     │     │     │        │
│    ptr   ptr   ptr   ptr       │  ← Child pointers in BtreeElem
└─────────────────────────────────┘
     │     │     │     │
     ▼     ▼     ▼     ▼
   child child child child        ← Child BtreeNode references

Memory Layout

Each BtreeElem contains:

• key: Integer value
• left_subtree: Pointer to left child node
• right_subtree: Pointer to right child node

Key Algorithms

1. Insertion Algorithm

Process:

1. Search for insertion point: Use binary search to find correct position
2. Handle full nodes: Split nodes that exceed 2t-1 keys before insertion
3. Split operation:
   • Create new right node
   • Move upper half of keys to new node
   • Promote median key to parent
4. Insert into leaf: Place key in correct sorted position

Time Complexity: O(log n) where n is the number of keys

2. Deletion Algorithm

Implements three main cases following B-tree deletion rules:

Case 1: Key in leaf node

• Simply remove the key and shift remaining keys

Case 2: Key in internal node

• Case 2a: Left child has ≥ t keys → Replace with predecessor
• Case 2b: Right child has ≥ t keys → Replace with successor
• Case 2c: Both children have t-1 keys → Merge children with key

Case 3: Key not in current node

• Case 3a: Child to descend has t-1 keys, sibling has ≥ t keys → Borrow from sibling
• Case 3b: Child and siblings have t-1 keys → Merge child with sibling

3. Search Algorithm

Binary Search within nodes:

def binary_search(self, key, node):
    left, right = 0, node.degree - 1
    while left <= right:
        mid = (left + right) // 2
        if node.arr[mid].key == key:
            return mid
        elif node.arr[mid].key < key:
            left = mid + 1
        else:
            right = mid - 1
    return right  # Return index of largest key < target

4. Range Query Algorithms

Keys in Range:

• Performs in-order traversal
• Collects keys within [low, high] bounds
• Optimizes by pruning subtrees outside range

Prime Keys in Range:

• Extends range query with primality testing
• Filters collected keys using probabilistic_primality_test

5. Order Statistics

Select k-th smallest:

• In-order traversal to get sorted sequence
• Return k-th element (1-indexed)

Rank of key:

• Count keys smaller than target during traversal
• Return 1-based index position

Usage

Command Line

python a3.py <t> <keystoinsert.txt> <keystodelete.txt> <commands.txt>

Parameters:

• t: Minimum degree for B-tree (integer ≥ 2)
• keystoinsert.txt: File with keys to insert (one per line)
• keystodelete.txt: File with keys to delete (one per line)
• commands.txt: File with operations to execute

Input File Formats

keystoinsert.txt:

12739121
58219403
45620117
...

keystodelete.txt:

99999959
88888888
1234567
...

commands.txt:

primesInRange 1 100
keysInRange 50000000 100000000
select 7
rank 1234567890

Supported Operations

Query Operations

Operation	Syntax	Description	Return Value
primesInRange	primesInRange low high	Find prime numbers in range [low, high]	Space-separated prime numbers or -1
keysInRange	keysInRange low high	Find all keys in range [low, high]	Space-separated keys or -1
select	select k	Find k-th smallest key (1-indexed)	Key value or -1
rank	rank target	Find rank of target key (1-indexed)	Rank value or -1

Return Values

• Success: Actual result (number or space-separated list)
• Failure/Not Found: -1
• Empty Result: -1

File Structure

B-trees/
├── submission_folder/          # Main implementation
│   ├── a3.py                  # Complete B-tree implementation
│   ├── keystoinsert.txt       # Sample input keys
│   ├── keystodelete.txt       # Sample deletion keys  
│   ├── commands.txt           # Sample commands
│   └── output.txt             # Generated output
├── 33458162/                  # Student ID folder
│   └── a3.py                  # Duplicate implementation
├── ori/                       # Original reference
│   └── b_trees_insertion.py   # Reference implementation
├── binTreeTest/               # Test files
└── misc/                      # Utility files

Examples

Example 1: Basic Operations

Input Files:

• t = 3 (minimum degree)
• Keys to insert: [10, 20, 30, 40, 50]
• Keys to delete: [20]
• Commands: select 2, rank 30

Expected Results:

• After operations: Tree contains [10, 30, 40, 50]
• select 2: Returns 30 (2nd smallest key)
• rank 30: Returns 2 (30 is at position 2)

Example 2: Range Queries

Command: keysInRange 25 45 Tree contains: [10, 30, 40, 50] Result: 30 40 (keys in range [25, 45])

Command: primesInRange 1 50 Tree contains: [10, 30, 40, 50] Result: -1 (no prime numbers in tree within range)

Example 3: Primality Testing

The Miller-Rabin test efficiently identifies primes:

• Small primes (2, 3, 5, 7, ..., 47): Direct lookup
• Larger numbers: Probabilistic testing with high confidence
• Composite numbers: Quickly identified and filtered

Time Complexity Analysis

Operation	Average Case	Worst Case	Notes
Insert	O(log n)	O(log n)	Balanced tree height
Delete	O(log n)	O(log n)	May require rebalancing
Search	O(log n)	O(log n)	Binary search + tree height
Range Query	O(k + log n)	O(n)	k = result size
Select/Rank	O(n)	O(n)	Requires traversal
Primality Test	O(log³ n)	O(log³ n)	Miller-Rabin complexity

Implementation Notes

Key Design Decisions

1. Embedded child pointers: Each key stores its own child pointers rather than separate arrays
2. Duplicate prevention: Insertion checks for existing keys to maintain uniqueness
3. Robust deletion: Implements all B-tree deletion cases for tree balance
4. Efficient primality: Combines quick filtering with probabilistic testing
5. Memory safety: Careful bounds checking and null pointer handling

Error Handling

• Invalid operations return -1
• Out-of-bounds queries return -1
• Missing keys in rank/select return -1
• Empty results return -1

This implementation provides a complete, efficient B-tree with integrated primality testing, suitable for educational purposes and practical applications requiring balanced tree operations with prime number queries.