一个结点的的儿子为 ,同时 都是偶数。
森林的每颗树的 要保证 不被使用。
Leafy Tree 显然在 merge split insert 的时候都可以做到不新建或者删除结点完成操作。
内存的好处是显然的,左右儿子是连续的,同时只需要存左儿子。
缺点是结点拷贝操作有点多。如果要维护很多东西的话,比如 的儿子是 ,用 代表 的 就不用拷贝了,代价是访问元素两次跳转。
对于 WBLT 或者是别的 Leafy Tree 比如 Aqours Tree 都适用,我之后会实际测试一下效果,毕竟 Aqours Tree 瓶颈就在内存。
当然 Treap 等 nodey 的也可以用,不过效果应该不明显。