balance

Documentation

Overview

Package balance ensures the local node subtree is properly balanced and has a minimal surface area heuristic (SAH).

Index

• func AVL(x node.N) node.N
• func BrianNoyama(n node.N) node.N
• func BrianNoyamaNoDF(n node.N) node.N
• func Rotate(x node.N) node.N
• func RotateNoDF(x node.N) node.N
• type B

Functions

func AVL

func AVL(x node.N) node.N

AVL will look a node x and conditionally optimize the local subtree for balanced node heights. That is, given the local subtree

  x
 / \
a   z
   / \
  b   y

where H(y) > H(b), this function will swap a and y so that the resultant tree looks like

  x
 / \
y   z
   / \
  b   a

Note that we are treating the BVH as an AVL tree here; that is, we assume the local tree was previously balanced (before the subtree rooted at x was mutated through an insert or delete operation). Because of this assumption, the maximum possible imbalance between the children of x (i.e. a and z) is two.

Further note that the rebalance operation is simplified because a BVH tree is invariant under sibling swaps --

  x
 / \
a   z

and

  x
 / \
z   a

Behave exactly the same, since the only property we care about in the query operation is on AABB intersections, and does not rely on the order between z and a, as is the case in e.g. a binary search tree.

In an AVL tree where in-order traversal behavior needs to be preserved and WLOG z is the right child of x, we will need to apply the standard L or RL on x, depending on if the c or b is heavier, respectively.

The returned node is the balanced input node.

See the briannoyama implementation for more details.

func BrianNoyama

func BrianNoyama(n node.N) node.N

B balances a given input node by

1. ensuring the node itself is balanced after the transformation, and 2. minimizing the SAH of the node.

Here, the avl() function is a flat tree height constraint (i.e. after calling the function,

| L.H() - R.H() | <= 1

and rotate() minimizes the SAH.

This function is based on a mix of

1. the Catto 2019 slides, 2. the briannoyama BVH implementation, and 3. Kopta et al. 2012

See the individual function docstrings for more information.

The input node is valid (i.e. its AABB and height are correctly pre-calculated), but its children may be imbalanced as a result of an insert or delete operation. That is, the height differs at most by one.

If H(n) <= 1 (where leaf nodes have a height of H(n) = 0), this function is a no-op.

The returned node has its AABB and height updated.

func BrianNoyamaNoDF

func BrianNoyamaNoDF(n node.N) node.N

func Rotate

func Rotate(x node.N) node.N

func RotateNoDF

func RotateNoDF(x node.N) node.N

RotateNoDF applies a tree cost minimization op as per Rotate, but skips the

D -> F and D -> G

checks. These checks are expensive and cause slow inserts, and at the same time, does not seem to give an appreciable broadphase speedup.

Types

type B

type B func(n node.N) node.N

B will update the subtree of the input node n. This node will have a valid cache at the end of this operation.