Optimal Binary Search Trees?

Has anyone written a fast, low memory optimal binary search tree implementation?

The data is fixed so nodes don’t need to be added or deleted, just accessed.

Are you asking about more cache-friendly memory layouts than a sorted list, for searchsorted?

Because a sorted list is an implicit binary tree that searchsorted walks, it just fails to be cache-oblivious.

1 Like

I wasn’t actually aware of searchsorted, it seems to be what I need. No wonder I couldn’t find a package that did that…