RTrtheunissen·Aug 15, 2023Submission
Exploring the design space of binary search trees
I started this project many years ago when I was coming up with ideas for immutable data structures for the PHP data structures extension [1]. I wanted to support access by position in a sorted set, which led to the idea of using binary search trees for both lists and sets. However, I did not expect the scope of this project to increase as much as it did.
The more I read about binary search trees, the more I thought about them, and so down the rabbit hole I went.
When you read everything you can find about a topic for several years, eventually you develop a deep enough understanding to compose new ideas from different sources.
This project is the result of many rejected ideas and countless experiments.
I tried my best to distill everything I consider important enough to keep, and will continue to develop other ideas as they come along.
Read the rest
I had no intention to implement anything other than weight-balanced strategies to support positional access, but when I read about rank-balanced trees I knew I had to take on the challenge to implement them.
I've been in contact with various authors along the way, specifically Bob Tarjan and Salvador Roura, but have otherwise not received any feedback yet.
Implementing all the algorithms was incredibly hard work, by far the hardest work I've ever done, so I hope that others may find value in their presentation.
There is still so much work that could be done, but there comes a time when working on something alone begins to yield diminishing returns. I hope to continue this project as an open-source collaborative effort, so please feel free to ask questions or suggest changes, however small.
[1] https://github.com/php-ds/ext-ds