B*-Tree
The idea
The B-tree is the O-tree's successor. It keeps the same world of compacted, pushed-to-the-lower-left packings, but records it as an ordered binary* tree. That change removes the O-tree's awkward asymmetry, where horizontal order lived in the tree and vertical order had to be recovered separately. Here both directions fall out of two crisp child rules.
Every node is a block, and the root is the block in the bottom-left corner. The two children mean different geometric things:
| relation | meaning in the packing | gives the child's |
|---|---|---|
| left child | the block immediately to the parent's right | x = parent's right edge |
| right child | the block above the parent at the same x | x = parent's x |
So the tree fixes every block's x-coordinate outright. The y-coordinate is the one thing left to compute, and it comes from dropping the block onto the contour (the skyline of everything placed so far, the same structure introduced on the O-tree page). Every compacted packing maps to exactly one B-tree and every B-tree decodes to exactly one packing: a clean bijection with no wasted encodings.
The recipe
Step 1 (root). Put the bottom-left block at the origin, x = 0, y = 0.
Step 2 (traverse). Visit the tree in preorder: node, then left subtree, then right subtree.
Step 3 (place x). A left child takes its parent's right edge as its x. A right child keeps its parent's x.
Step 4 (place y). Drop the block onto the contour over its width, then update the contour. Maintaining it as a doubly linked list makes each placement amortized constant time, so the whole decode is linear.
Step 5 (perturb). For annealing, use three tree moves: rotate a block (swap width and height), move a node to another position, or swap two nodes. Each is a constant-time surgery followed by a re-decode.
Watch it work: two child rules and a contour decode
Five blocks. The walkthrough reads the two child rules off the packing, draws the packing and its binary tree side by side, then decodes the tree in preorder, taking each x from the child rule and each y from the contour.
How it improves on the O-tree. The two representations cover the same space of compacted packings and both decode in linear time, so the gain is not asymptotic, and the B-tree is not the shorter or more balanced tree. In fact it can be taller: the O-tree is a general tree where a column of blocks sharing an x-coordinate is one node with many siblings, and the B-tree turns those siblings into a long right-going chain. Height does not matter either way, since the decode visits each node once against the contour and never walks a path from the root. The real advantages are structural:
- Fixed branching. A binary tree has at most two children per node, always. The O-tree's variable arity needs a variable bracket sequence plus a permutation and more bookkeeping in its moves. A binary tree is a simpler, more regular structure to store and mutate.
- Both axes are first-class pointers. This is where the O-tree's asymmetry is removed. The O-tree makes horizontal order explicit as parent-child links but leaves vertical order implicit in the sibling ordering. The B*-tree assigns one pointer to each axis: the left child is the x-relation (the block to the right), the right child is the y-relation (the block stacked above at the same x).
- Simpler, faster moves. Rotate, move, and swap are plain binary-tree surgeries. There is no sibling-list splicing, no bracket-sequence to re-normalize, and no wall or dummy node to special-case, because the B*-tree's root is a real block.
Why the binary tree helps. The tree is the small object the annealer searches over: a few pointers, mutated by three simple moves. The geometry is regenerated on demand, and because the encoding is a bijection onto compacted packings, the search space is exactly the set of legal floorplans, far smaller than the sequence pair's (n!)² pairs. Every decode is legal by construction and runs in linear time, so the annealer can afford to try enormous numbers of candidates.
Pros, cons, and the trade-off
Strengths
- Both axes from the tree: x from the child rule, y from the contour, with none of the O-tree's asymmetry.
- Simple moves: rotate, move, swap are all constant-time tree surgeries, ideal for annealing.
- Tight bijection: the search space is exactly the compacted packings, much smaller than the sequence pair's.
- Extends well: published variants handle fixed outlines, soft blocks, rectilinear blocks, 3D stacks, and analog symmetry.
Weaknesses
- Compacted only: like the O-tree it cannot express floorplans that need deliberate slack or fixed absolute positions.
- Fixed-outline is a bolt-on: hitting a target aspect ratio needs extra work, since the raw representation only minimizes area.
- Local moves: tree surgeries make small geometric changes, so escaping a bad basin can take many moves.
The trade-off
The B*-tree trades the sequence pair's expressiveness for a much smaller, always-legal search space. By representing only compacted packings it gets both coordinates from one binary tree, constant-time moves, and a linear decode, which is why it became the default engine for area-driven annealing. The price is that it cannot describe floorplans with intentional whitespace or fixed positions, and meeting a fixed outline needs added structure rather than falling out for free.
Is it actually used today?
The B*-tree is the most widely built non-slicing floorplan representation in the research literature.
- Academic macro floorplanners: it is the default representation for area-driven simulated-annealing packers and the baseline that new representations are measured against.
- Analog and mixed-signal placement: symmetry-island and constraint-aware B*-tree variants are a common backbone for analog device placement research.
- A family, not one algorithm: published extensions cover fixed outlines, soft and rectilinear blocks, bus-driven placement, and 3D stacking, so the same core encoding reappears across many problems.
- Note on production tools: commercial floorplanners do not publish their internal representations, so their use of a B*-tree specifically is not verifiable. The open-source and academic evidence above is what is confirmable.