Best way to write a binary search tree

General Usage
1

What is the best (i.e. simple and fast) way to code a binary search tree in Julia nowadays?
(E.g. does it use Nullables? Or self-links from a node to itself to represent a missing child?)

This question has come up a few times in the past, but I haven’t been able to find a canonical, efficient answer.

3 Likes
2

You could store everything in an array like:

It might waste some space depending on how you create the tree.

This is how I store the trees in GitHub - KristofferC/NearestNeighbors.jl: High performance nearest neighbor data structures and algorithms for Julia. and it works quite well.

7 Likes
3

The containers SortedDict, SortedMultiDict and SortedSet in DataStructures.jl use two arrays, one to store the key/value pairs at the tree leaves and the other to store interior tree nodes. Each interior node stores integer indices (array subscripts) for its children and parent, and missing children are indicated by storing a 0. A leaf stores an integer index of its parent. Depending on your application, you may be able to use these data structures rather than coding your own.

3 Likes