为 minDiff 扩充红黑树

Question

所以我有以下问题：

您有一组数字 S，您正在将其存储在红黑树中。您正在尝试将 minDiff 添加到红黑树中，它为您提供 S 中两个最接近数字之间的绝对差值。例如，如果 S = {1, 18, 23, 62, 79, 100} minDiff 将 return 5 (|23 - 18|)

A) 展示如何扩充红黑树以有效支持此操作，同时保持插入、搜索和删除的 O(lgn) 运行时间。

B) 展示如何输出创建 MinDiff 的两个数字的值。对于上面的示例，您将输出 23 和 18。

我的困惑：

我卡在了问题的最开始部分，即要扩充什么。我可以想到简单而低效的解决方案，例如让每个节点保持其自身与其父节点之间的绝对差异。但是，似乎应该有一些优雅的解决方案，不需要您查看树的每个值来确定解决方案。

我希望我能展示更多我的作品，但我完全被难住了，不知道从哪里开始！

Answer 1

您添加到树中的信息必须满足 2 个要求：

它必须让你快速计算minDiff；和
您必须能够根据其两个子项中的信息重新计算父项信息。这使您可以快速修复受插入、删除和重新平衡操作影响的任何节点中的信息。

立即想到的答案是用其子树中节点之间的 minDiff 及其子树中的最小值和最大值来扩充树中的每个节点。

node.minVal = node.left ? node.left.minVal : node.val
node.maxVal = node.right ? node.right.maxVal : node.val
node.minDiff = min(
    node.left.minDiff,
    node.right.minDiff,
    node.val - node.left.maxVal,
    node.right.minVal - node.Val
    )

为 minDiff 扩充红黑树

Augmenting red-black tree for minDiff

algorithm

red-black-tree

binary-search-tree