There are a number of ways to utilize this fact in a computer simulation [Appel:85a], [Barnes:86a], [Greengard:87b], [Zhao:87a]. The methods differ in choice of data structure, level of mathematical rigor, and complexity of the fundamental interactions. We shall consider an adaptive tree data structure, and an algorithm that treats each body independently. The algorithm begins by partitioning space into an oct-tree, that is, a tree whose nodes correspond to cubical regions of space. Each node may have up to eight daughter nodes, corresponding to the eight subcubes that are obtained by dividing in half in each Cartesian direction. The tree is defined by the following properties:

- All terminal nodes of the tree have either one or zero bodies.
- All nodes with one or zero bodies are terminal.

**Figure 12.10:** (a) Expanded and (b) Flat Representation of an Adaptive Tree

**Figure 12.11:** 10,000 Body Barnes-Hut Tree

The oct-tree provides a convenient data structure which allows us to record the properties of the matter distribution on all length scales. It is especially convenient for astrophysical systems because it is adaptive. That is, the depth of the tree adjusts itself automatically to the local particle density. In order to use an approximation like Equation 12.5, we need to know certain properties of the matter distribution in each cell. In the simplest case, these properties are the mass and center-of-mass of the matter distribution, but it is possible to use quadrupole moments [Hernquist:87a], or higher-order moments [Salmon:90a] for added accuracy. All of these properties may be computed by a bottom-up traversal of the tree, combining the properties of the ``daughters'' of a node to get the properties of the node itself. The time required for this bottom-up traversal is proportional to the number of internal nodes in the tree, that is, .

Wed Mar 1 10:19:35 EST 1995