# Data type for a “stupid” binary search tree

**URL:** <https://discourse.julialang.org/t/data-type-for-a-stupid-binary-search-tree/64474>\
**Category:** Performance\
**Tags:** tree\
**Created:** [July 11, 2021, 10:41pm UTC](https://discourse.julialang.org/t/data-type-for-a-stupid-binary-search-tree/64474 "2021-07-11T22:41:40Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![circonflexe](https://avatars.discourse-cdn.com/v4/letter/c/c57346/32.png) [@circonflexe](https://discourse.julialang.org/u/circonflexe)\
**Post date:** [July 11, 2021, 10:41pm UTC](https://discourse.julialang.org/t/data-type-for-a-stupid-binary-search-tree/64474/1 "2021-07-11T22:41:40Z")

</div>

I need a data type for a collection of objects (stored in a given order) which supports both _O(log n)_ insertion and deletion methods, as well as some way to perform a dichotomic search (where I provide the left-or-right test): namely, given a function `cmp`, where I promise that `map(cmp, collection)` is of the form `(false, false, false..., true, true, true...)`, find the handle for the first object `x` such that `cmp(x) == true`.

In addition, I also need some way of performing sequential traversal (for swapping objects in the collection as needed to preserve the above promise).

In other words, I need this structure to behave like a `Vector`, but with efficient insertion and deletion (at the price of _O(log n)_ lookup). This is _not_ a sorted container; namely, the data in the container is indeed sorted according to some weird ordering, but I do not need the container to know anything about this order (all the comparisons are performed by the external `cmp` function at insertion/deletion time).

This should possible in theory by using a self-balancing binary tree; `DataStructures.jl` has several such types (e.g. `BalancedTree23`, and recent versions export `RBTree`), but they apparently all use comparison functions between the stored values, which is what I want to avoid. Does there exist a data structure implementing this, or must I write it from scratch?

(For more context: my goal is to implement a variant of the [Bentley-Ottmann algorithm](https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm). The data structure stores a set of segments, represented as pairs of indices of points, and sorted by increasing intercept along a given _x = constant_ line. The comparison between those segments is _not_ done by computing the intercepts, because this would need to be redone each time a new line is chosen; instead, the correct insertion point is chosen for each new segment by computing determinants. Whenever the data becomes incorrectly-sorted in the list, this is detected and they are manually swapped).

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [July 11, 2021, 11:14pm UTC](https://discourse.julialang.org/t/data-type-for-a-stupid-binary-search-tree/64474/2 "2021-07-11T23:14:59Z")

</div>

> [@circonflexe](#):
>
> the external `cmp` function

this function only has one argument?

---

<div class="post-metadata">

**Author:** ![circonflexe](https://avatars.discourse-cdn.com/v4/letter/c/c57346/32.png) [@circonflexe](https://discourse.julialang.org/u/circonflexe)\
**Post date:** [July 12, 2021, 9:25am UTC](https://discourse.julialang.org/t/data-type-for-a-stupid-binary-search-tree/64474/3 "2021-07-12T09:25:19Z")

</div>

> [@xiaodai](#):
>
> this function only has one argument?

The one-argument form is of course an abstraction of `x->cmp(some_reference_value, x)`.

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [July 13, 2021, 3:41am UTC](https://discourse.julialang.org/t/data-type-for-a-stupid-binary-search-tree/64474/4 "2021-07-13T03:41:14Z")

</div>

I’m not sure if I understand but maybe [GitHub - andyferris/AcceleratedArrays.jl: Arrays with acceleration indices](https://github.com/andyferris/AcceleratedArrays.jl) is relevant

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [July 13, 2021, 3:59am UTC](https://discourse.julialang.org/t/data-type-for-a-stupid-binary-search-tree/64474/5 "2021-07-13T03:59:51Z")

</div>

Anyway, the description is very complicated. But I would just use existing trees structures and just overload some methods using MD

```julia
using DataStructures
tree = RBTree{Int}();

push!.(Ref(tree), 1:20)

import Base

Base.iterate(tree::RBTree) = Base.iterate(tree, 1)

function Base.iterate(tree::RBTree, pos::Integer)
    @assert pos >= 1
    if pos <= length(tree)
        return tree[pos], pos+1
    else
        return nothing
    end
end

cmp(x) = x == 2

map(cmp, tree)

function Base.findfirst(cmp::Function, tree::RBTree)
    for i = 1:length(tree)
        if cmp(tree[i])
            return tree[i]
        end
    end
    nothing
end

findfirst(cmp, tree)

```