Dynamic Pointer-Based Binary Search Trees.
So, Whats the best data structure we know? is it BST's with log n? or is it hash tables with constant time in most cases, well hash tables are good, collisions are bad!! so why not just find a way to store data with another layer which reduces time complexity. so the idea of DPB-BSTs is that, we have a linked list L, containg Nodes N, so each N has a BST B, with capacity C, such that the binary search tree in a previous node stores n*2 more nodes then the previous N. it creates a dynamic time complexity of O (2 * floor(log of number your loooking for))
Institutions
- Saint Joseph's University (US)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2024-10-07
- DOI
- https://doi.org/10.5281/zenodo.13899127
- Primary Topic
- Algorithms and Data Compression
- Type
- article
- Field-Weighted Citation Impact
- 0.00