# Optimal Binary Search Trees?

**URL:** <https://discourse.julialang.org/t/optimal-binary-search-trees/15232>\
**Category:** General Usage\
**Created:** [September 20, 2018, 1:06pm UTC](https://discourse.julialang.org/t/optimal-binary-search-trees/15232 "2018-09-20T13:06:24Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [September 20, 2018, 1:06pm UTC](https://discourse.julialang.org/t/optimal-binary-search-trees/15232/1 "2018-09-20T13:06:24Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [September 20, 2018, 1:15pm UTC](https://discourse.julialang.org/t/optimal-binary-search-trees/15232/2 "2018-09-20T13:15:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [September 20, 2018, 1:37pm UTC](https://discourse.julialang.org/t/optimal-binary-search-trees/15232/3 "2018-09-20T13:37:55Z")

</div>

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…