Leafy Tree

Leafy Tree 简介

Leafy Tree 是一种依靠旋转维持重量平衡的平衡树。 通过判断一棵树的数据存储位置在每个节点上还是仅在叶子节点上，我们可以将树分为 Nodey 和 Leafy 的。Leafy Tree 被定义为一种维护的信息全部储存在叶子节点上的二叉树。 这种结构中，每个叶子存储值，每个非叶节点值负责维护树的形态而不维护树的信息，但通常会维护孩子信息，从而加速查询。线段树的结构属于一种 Leafy Tree。所以 Leafy Tree 也被称为平衡线段树。

Leafy Tree 的特点

1. 所有的信息维护在叶子节点上。
2. 类似 Kruskal 重构树的结构，每个非叶子节点一定有两个孩子，且非叶子节点统计两个孩子的信息（类似线段树上传信息），所以维护 个信息的 Leafy Tree 有 个节点。
3. 可以完成区间操作，比如翻转，以及可持久化等。

注意到，一个 Leafy 结构的每个节点必定有两个孩子。对其进行插入删除时，在插入删除叶子时必定会额外修改一个非叶节点。 常见的平衡树均属于每个节点同时维护值和结构的 Nodey Tree。如果将一个 Nodey 结构的所有孩子的空指针指向一个维护值的节点，那么这棵树将变为一个 Leafy 结构。

Leafy Tree 是一个纯函数化的数据结构，因此其在实现函数化数据结构和可持久化效率上具有先天优势，时间效率极高。

一个简单的图例如下：

基本操作

Leafy Tree 的基本操作有：旋转，插入，删除，查找。

旋转

Leafy Tree 的旋转操作类似于替罪羊树，仅需一次旋转。

插入

类似二叉树的插入过程。

删除

根据二叉搜索树的性质，找到要删除的数所在的父亲节点，再暴力枚举在左孩子还是右孩子，然后将剩下的一个节点合并到当前节点。

删除的代码如下：

查找

假设需要查找排名第 大的元素。

普通平衡树的模版代码

例题

• Luogu P2286 宠物收养场

参考资料

• WBLT 学习笔记
• Leafy Tree
• Luogu P2286[HNOI2004]宠物收养场