d3binarytree
Ported version of D3's Quadtree, to use with onedimensional data structures, by removing the y coordinate.
A binary tree recursively partitions arrays into segments, dividing each array into two equallysized halves. Each distinct point exists in a unique leaf node; coincident points are represented by a linked list. Binary trees can accelerate various spatial operations, such as the Barnes–Hut approximation for computing manybody forces, collision detection, and searching for nearby points.
See also d3quadtree and d3octree.
Installing
If you use NPM, npm install d3binarytree
. You can also load directly from the global npmJS registry, as a bundled standalone library. AMD, CommonJS, and vanilla environments are supported. In vanilla, a d3
global is exported:
<script src="https://unpkg.com/d3binarytree"></script>
<script>
var binarytree = d3.binarytree();
</script>
Try d3binarytree in your browser.
API Reference
# d3.binarytree([data[, x]]) <>
Creates a new, empty binarytree with an empty extent and the default xaccessor. If data is specified, adds the specified array of data to the binarytree. This is equivalent to:
var tree = d3.binarytree()
.addAll(data);
If x is also specified, sets the x accessor to the specified functions before adding the specified array of data to the binarytree, equivalent to:
var tree = d3.binarytree()
.x(x)
.addAll(data);
If x is specified, sets the current xcoordinate accessor and returns the binarytree. If x is not specified, returns the current xaccessor, which defaults to:
function x(d) {
return d[0];
}
The xacccessor is used to derive the xcoordinate of data when adding to and removing from the tree. It is also used when finding to reaccess the coordinates of data previously added to the tree; therefore, the xaccessor must be consistent, returning the same value given the same input.
# binarytree.extent([extent]) <>
If extent is specified, expands the binarytree to cover the specified points [[x0], [x1]] and returns the binarytree. If extent is not specified, returns the binarytree’s current extent [[x0], [x1]], where x0 is the inclusive lower bound and x1 is the inclusive upper bound, or undefined if the binarytree has no extent. The extent may also be expanded by calling binarytree.cover or binarytree.add.
Expands the binarytree to cover the specified point ⟨x⟩, and returns the binarytree. If the binarytree’s extent already covers the specified point, this method does nothing. If the binarytree has an extent, the extent is repeatedly doubled to cover the specified point, wrapping the root node as necessary; if the binarytree is empty, the extent is initialized to the extent [[⌊x⌋], [⌈x⌉]]. (Rounding is necessary such that if the extent is later doubled, the boundaries of existing segments do not change due to floating point error.)
Adds the specified datum to the binarytree, deriving its coordinates ⟨x⟩ using the current xaccessor, and returns the binarytree. If the new point is outside the current extent of the binarytree, the binarytree is automatically expanded to cover the new point.
Adds the specified array of data to the binarytree, deriving each element’s coordinates ⟨x⟩ using the current xaccessor, and return this binarytree. This is approximately equivalent to calling binarytree.add repeatedly:
for (var i = 0, n = data.length; i < n; ++i) {
binarytree.add(data[i]);
}
However, this method results in a more compact binarytree because the extent of the data is computed first before adding the data.
Removes the specified datum to the binarytree, deriving its coordinates ⟨x⟩ using the current xaccessor, and returns the binarytree. If the specified datum does not exist in this binarytree, this method does nothing.
# binarytree.removeAll(data) <>
Removes the specified data from the binarytree, deriving their coordinates ⟨x⟩ using the current xaccessor, and returns the binarytree. If a specified datum does not exist in this binarytree, it is ignored.
# binarytree.copy()
Returns a copy of the binarytree. All nodes in the returned binarytree are identical copies of the corresponding node in the binarytree; however, any data in the binarytree is shared by reference and not copied.
Returns the root node of the binarytree.
Returns an array of all data in the binarytree.
Returns the total number of data in the binarytree.
# binarytree.find(x[, radius]) <>
Returns the datum closest to the position ⟨x⟩ with the given search radius. If radius is not specified, it defaults to infinity. If there is no datum within the search area, returns undefined.
# binarytree.visit(callback) <>
Visits each node in the binarytree in preorder traversal, invoking the specified callback with arguments node, x0, x1 for each node, where node is the node being visited, ⟨x0⟩ is the lower bound of the node, and ⟨x1⟩ is the upper bound, and returns the binarytree. (Assuming that positive x is right, ⟨x0⟩ is the left boundary and ⟨x1⟩ is the right boundary; however, the coordinate system is arbitrary, so more formally x0 <= x1.)
If the callback returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited. This can be used to quickly visit only parts of the tree, for example when using the Barnes–Hut approximation. Note, however, that child segments are always visited in sibling order: left, right. In cases such as search, visiting siblings in a specific order may be faster.
# binarytree.visitAfter(callback) <>
Visits each node in the binarytree in postorder traversal, invoking the specified callback with arguments node, x0, x1 for each node, where node is the node being visited, ⟨x0⟩ is the lower bound of the node, and ⟨x1⟩ are the upper bound, and returns the binarytree. (Assuming that positive x is right, ⟨x0⟩ is the left boundary and ⟨x1⟩ is the right boundary; however, the coordinate system is arbitrary, so more formally x0 <= x1.) Returns root.
Nodes
Internal nodes of the binarytree are represented as twoelement arrays in lefttoright order:

0
 the left half, if any. 
1
 the right half, if any.
A child half may be undefined if it is empty.
Leaf nodes are represented as objects with the following properties:

data
 the data associated with this point, as passed to binarytree.add. 
next
 the next datum in this leaf, if any.
The length
property may be used to distinguish leaf nodes from internal nodes: it is undefined for leaf nodes, and 4 for internal nodes. For example, to iterate over all data in a leaf node:
if (!node.length) do console.log(node.data); while (node = node.next);
The point’s xcoordinate must not be modified while the point is in the binarytree. To update a point’s position, remove the point and then readd it to the binarytree at the new position. Alternatively, you may discard the existing binarytree entirely and create a new one from scratch; this may be more efficient if many of the points have moved.