Implement Fusion Tree for Fast Integer Key Search

Description

Fusion Trees are advanced search trees optimized for integer keys, achieving O(log log n) search time using word-level parallelism. Unlike traditional balanced trees, Fusion Trees use bitwise operations, sketching, and parallel comparisons to speed up searches. Implementing Fusion Trees in pydatastructs would provide a highly efficient alternative to AVL and Red-Black Trees for large datasets with integer keys.

Tasks

• Implement a Fusion Tree with insert, search, and delete operations.
• Optimize the tree using bitwise sketching for compressed key comparisons.
• Implement multiplication-based fingerprinting for parallel search.
• Add unit tests to verify correctness and performance.

References

• Fusion Tree - Wikipedia
• Fredman & Willard (1990): “Fusion Trees”