Alternative representations for Hierarchy #22
Description
This is a tracking issue for alternative Hierarchy representations
The current Hierarchy component implementation contains a parent pointer on each hierarchy::NodeData. This provides O(1) access to a node's parent, but requires accessing every children during a transplantation operation where we swap a parent for another node.
- An alternative representation may only include the parent pointer on the first/last sibling, to invert the mentioned constant and linear costs.
- A middle ground compromise could use a skip list, where most operations cost
O(log n). - We could also explore replacing the intrusive linked lists by children node blocks on the parent. This would consume more memory but may end up being more efficient.