找到AVL树中两个数字之间的最小间隙

Question

我有一个数据结构作业,除了常规的AVL树函数,我还要添加一个函数,它返回AVL树中任意两个数字之间的最小间隙(AVL中的节点实际上代表数字.)

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

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

试图思考很多,我知道有一个伎俩但是找不到它,我已经花了好几个小时.

还有另一项任务是找到最大间隙,这很容易,它是最小和最大数之间的差异.

Answer 1

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

你有额外的约束,不会增加插入/删除/搜索功能的时间复杂性,我认为你也不想增加空间复杂性.

让我们考虑一个通用节点r,左子树rL和右子树rR ; 我们将扩展节点r中的信息附加数rx定义为最小值:

• (仅当rL不为空时)r值和rL上最右边叶子的值
• (仅当rL深于1时)rL根节点的x值
• (仅当rR不为空时)r值和rR上最左边叶子的值
• (仅当rR深于1时)rR根节点的x值

(如果以前的条件都不是有效的,则为undefined,如果是叶节点)

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

你可以看到这些添加:

• 空间复杂度仅以恒定因子增加
• 插入/删除函数需要更新x值以及每个已更改子树的根的最左边和最右边的叶子,但是以一种不需要超过O(log(n))的方式实现它是微不足道的
• 树根的x值是函数需要返回的值,因此可以在O(1)中实现它

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

这种陈述的证明可以通过递归来实现:让我们考虑一个以节点r为根的树,左子树rL和右子树rR.归纳假设是rL和rR x值的根是子树的节点值之间的最小间隙的值.很明显,只考虑值排序列表中具有相邻值的节点对,可以找到最小间隙; 由rL节点存储的值形成的对在rL根x值中具有最小间隙,考虑到右子树也是如此.鉴于(rL中的节点的任何值)< L根节点的值<(rR中的节点的任何值),不考虑的唯一相邻值对是两个:

1. 由根节点值和较高rL节点值组成的对
2. 由根节点值和下rR节点值组成的对

具有较高值的rL节点是AVL树属性的最右边叶子,具有较低值的rR节点是其最左边的叶子.将rx值分配给四个值(rL根x值,rR根x值,(r -rL根)间隙,(r -rR root)间隙)之间的最小值是相同的,以指定连续节点值之间的较小间隙在整个树中,这相当于任何可能的节点值对之间的较小间隙.子树中的一个或两个为空的情况是微不足道的.只有一个或三个节点组成的树的基本情况,看到树根的x值是最小间隙值是微不足道的.