Bit-slice Tree Variants

Bit-slice and Trie-Based Trees

Type	Description	Key Characteristic	Typical Use Case	Access Pattern	Memory Behavior	Notes
Trie	Prefix tree	Character/bit-wise branching	Dictionaries	Prefix-based	Pointer-heavy	No hashing
Radix Tree	Compressed trie	Path compression	Routing tables	Prefix-based	Pointer-based	Space efficient
X-fast Trie	Hash-assisted trie	Fast predecessor queries	Ordered sets	Bit-level	Hash + pointer	O(log w) time
Y-fast Trie	X-fast + buckets	Reduced space	Ordered sets	Bit-level	Hash + pointer	O(log w) expected
Judy Array	Sparse dynamic array	Cache optimized	High-performance maps	Indexed	Pointer-based	Language-specific
Suffix Tree	Index of suffixes	Linear-time construction	String search	Substring	Tree-based	High memory
Generalised Suffix Tree	Multiple strings	Shared suffix indexing	Text analytics	Substring	Tree-based	Multi-document
Compressed Suffix Array	Space-efficient suffix index	Succinct structure	Large text indexes	Binary search	Compact	Replaces suffix tree
FM-index	Compressed full-text index	Burrows–Wheeler based	Genomics	Backward search	Highly compact	Substring queries
Merkle Tree	Hash-based tree	Cryptographic integrity	Blockchains	Path-based	Tree-based	Tamper detection
B-tree	Multi-way search tree	Block-based nodes	Filesystems	Logarithmic	Node-based	Included for contrast