search - 在AVL树中找到两个数字之间的最小间隔

Question

我有一个数据结构作业，除了常规的AVL树函数外，我还必须添加一个函数，该函数返回AVL树中任何两个数字之间的最小间距(AVL中的节点实际上代表数字)。

假设我们在AVL树中有数字(作为节点)1 5 12 20 23 21，该函数应返回任意两个数字之间的最小距离。在这种情况下，应返回“1”，即| 20-21 |。或| 21-20 |。

它应该在O(1)中完成。

试图思考很多，我知道有一个窍门，但找不到，我已经花了数小时。

还有另一个任务是找到最大间隙，这很容易，这是最小数量和最大数量之间的差。

Answer 1

您需要扩展数据结构，否则将无法获得构成树的数字之间的最小间隙的O(1)搜索。

您还有其他限制，不能增加插入/删除/搜索功能的时间复杂度，并且我想您也不想增加空间复杂度。

让我们考虑一个通用节点 r ，其左子树 r.L 和右子树 r.R ；我们将扩展节点 r 中附加信息 r.x 中的信息，该值定义为以下两者之间的最小值:

(仅当r.L不为空时)r值和r.L上最右边的叶子的值

(仅当r.L大于1时)r.L根节点的x值

(仅当r.R不为空时)r值和r.R上最左边的叶子的值

(仅当r.R大于1时)r.R根节点的x值

(如果是叶节点，则如果先前的条件均无效，则为undefined)

另外，为了快速插入/删除，我们需要在每个内部节点中添加对其最左侧和最右侧叶节点的引用。

您可以通过以下添加看到:

空间复杂度仅增加一个常数因子

insert/delete函数需要更新x值以及每个更改后的子树的根的最左边和最右边的叶子，但是以不需要超过O(log(n))

的方式实现是微不足道的

树根的x值是函数需要返回的值，因此可以在O(1)中实现

树中的最小间隙是根节点的 x 值，更具体地说，对于每个子树，子树元素中的最小间隙仅是子树根 x 值。

该语句的证明可以通过递归进行:
让我们考虑一棵以节点 r 为根的树，左子树 r.L 和右子树 r.R 。
归纳假设是 r.L 和 r.R x 值的根是子树节点值之间的最小间隙值。
显然，可以仅考虑值对列表中具有相邻值的节点对来找到最小间隙；由 r.L 的节点存储的值形成的对在 r.L 根 x 值中具有最小的间隙，考虑正确的子树也是如此。鉴于( r.L 中的节点的任何值)< L 根节点的值<( r.R 中的节点的任何值)，唯一不考虑的相邻值对是两个:

由根节点值和较高的 r.L 节点值

组成的对

由根节点值和较低的 r.R 节点值

组成的对

值较高的 r.L 节点是AVL树属性的最右叶子，值较低的 r.R 节点是其最左边的叶子。
分配给 rx 值四个值之间的最小值(rL根x值，rR根x值，(r-rL根)间隙，(r-rR根)间隙)是相同的，以分配连续之间的较小间隙整个树中的节点值，等于任何可能的一对节点值之间的较小间隙。
子树中的一两个是空的情况是微不足道的。
一棵仅由一个或三个节点组成的树的基本情况，可以很容易地看到树根的x值是最小间隙值。