Hi there, I found two examples of binary search tree written in Solidity given below and I'm wondering if OpenZeppelin has any plan implementing a formal version of this extremely useful data structure. Thanks.
We currently don't have plans to support a binary tree data structure but are open to it if there's a demanded general use case that we can fit in the library.
Seems like the HitchensOrderStatisticTreeLib is too specialized and is unclear what the BinaryTree would be used for. Do you know concrete popular use cases of binary trees out there?
I thought Binary Search Tree is a fundamentally useful data structure in maintaining a sorted array of values such that fast verification, insertion and retrieval can be done in O(1) complexity. I could not think of a use case immediately, but given how fundamental this truly is, it may open up many use cases, just like how this sorted double linked list made the project Liquity possible.
A self-balancing binary search tree would be a very useful data structure to support.
An example use case is order books. Suppose there is a list of Prices, each Price with a linked list of outstanding quotes at that price. While traders can insert, update, and remove non-marketable limit orders in O(1), placing an immediately executable order (market orders and marketable limit orders) requires the exchange to iterate through a sorted list of Prices to fill the order at the best price. A self-balancing binary search tree would allow Prices to be sorted in O(log n).
Another example is onchain randomness. Suppose we wanted to randomly divide items in an array into two different groups. In block B, items are appended to the array. In block B+1, we hash each item using blockhash(block.number - 1), sort the bytes32 hashes, and then iterate through the sorted list, assigning the first half of items to group 1 and second half of items to group 2. A self-balancing binary search tree would allow the hashes to be sorted in O(log n).