To give an example, let’s say we create a tree with 6 points and leafsize=1 for simplicity:
Note that in NearestNeighbors.jl, we always fill “from the left” and at most one leaf node will not have a completely filled “bucket”.
The black numbers are the numer of the nodes. The green ones are the number of the leaf nodes. The “cross node” is 8 which is the node where the leaf nodes start (but note that the node number for leaf node 1 is higher than the node number for leaf node 5. Doing this in the package:
julia> tree = KDTree(rand(3,6); leafsize=1);
# nodes 1-5 are internal (non-leaf)
julia> tree.tree_data.n_internal_nodes
5
# 8 is the "cross" node where the leaf nodes start
julia> tree.tree_data.cross_node
8
# The range of the leaf nodes for node 8
julia> NearestNeighbors.get_leaf_range(tree.tree_data, 8)
1:1
# The range of leaf nodes for node 6
julia> NearestNeighbors.get_leaf_range(tree.tree_data, 6)
5:5
# and the size of the last (possible unfilled) node bucket is here of course 1
julia> tree.tree_data.last_node_size
1
You can try create a tree with 11 nodes and a leafsize of 2 to see how the last bucket will now be half full.