一种内存友好的二叉森林结点编号方式,适合用于 Leafy Tree

  • 405 字

一个结点的的儿子为 x,x xor 1x,x\ \text{xor}\ 1,同时 xx 都是偶数。

森林的每颗树的 rtrt 要保证 rt xor 1rt\ \text{xor}\ 1 不被使用。

Leafy Tree 显然在 merge split insert 的时候都可以做到不新建或者删除结点完成操作。

内存的好处是显然的,左右儿子是连续的,同时只需要存左儿子。

缺点是结点拷贝操作有点多。如果要维护很多东西的话,比如 uu 的儿子是 xx,用 wxw_x 代表 uuww 就不用拷贝了,代价是访问元素两次跳转。

对于 WBLT 或者是别的 Leafy Tree 比如 Aqours Tree 都适用,我之后会实际测试一下效果,毕竟 Aqours Tree 瓶颈就在内存。

当然 Treap 等 nodey 的也可以用,不过效果应该不明显。