Research Article
Shuffle Tree: A Randomized Self-Adjusting Binary Search Tree
https://doi.org/10.21203/rs.3.rs-3136752/v1
This work is licensed under a CC BY 4.0 License
posted
You are reading this latest preprint version
We present algorithms for a new self-adjusting binary search tree, which we call ashuffle tree. The tree is easy to implement and does not require parent pointers orbalancing information to be stored in tree nodes. A maximum of one rotation isapplied randomly during each traversal, which keeps the cost of balancingactivity low.
binary search trees
self-adjusting data structures
randomized algorithms
randomized data structures
No competing interests reported.
posted
You are reading this latest preprint version