硬质：AVL树

Question

有人问我这个问题，我个人觉得很难。

创建一个数据结构，可以：

插入元素,删除元素,搜索元素,在O(log n)的时间里

此外，它还应该有以下两个函数，它们的工作时间为O(1)。

1. next(x):给定一个指向值x的节点的指针，返回一个指向比x大的最小值的节点的指针。

2. previous(x)给定一个指向值x的节点的指针，返回一个指向比x的值最小的节点的指针。

Answer 1

如果每个节点都包含一个指向它的后继者的指针和一个指向它的前继者的指针，或者等价--如果你同时维护一个双链的列表和一棵树，树上的每个节点都指向列表中的等价节点，反之亦然--你就会得到你想要的。在insertdelete上更新列表是O(1)(在找到树中最接近的节点之后)。搜索是在树上进行的。继任者前辈是在列表上进行的。

Answer 2

评论中@RogerLindsjö的想法很好。本质上，保持一个常规的、平衡的BST，然后在节点中穿行一个双链路列表，保持它们的排序顺序。这样一来，给定一个指向树中某个节点的指针，你就可以简单地按照每个节点的下一个或上一个指针找到比它小的最大值或比它大的最小值。

你可以通过插入和删除来维护这个列表，而不会改变插入或删除的整体运行时间。例如，下面是你如何插入一个元素x。

1. 做一个标准的BST继任者查询 来找到树上比x大的最小值 然后再做一个标准的BST前置查询 来找到树上比x小的最大值。每次搜索完成需要时间O(log n)。
2. 做一个常规的BST插入来插入x，然后，将其下一个和上一个指针设置为上一步找到的两个元素，并更新这些节点指向你的新节点x，这也需要时间O(log n)。

那么插入的总时间是 O(log n)，符合平衡树所能提供的功能。

我让你去想办法删除，它同样可以维护链接列表指针，而不改变操作的整体成本。

Answer 3

和大多数自平衡树一样，一个 B+树 提供插入、删除和搜索操作，并提供 O(log n) 的时间复杂度。

在一棵B+树中，一个叶子节点在一个数组中承载了多个键，所以 "指向节点的指针与值 "的概念 x"其实并不存在，但我们可以将其定义为元组（指针，索引），其中指针是指节点，索引是指其中的槽位。x 是存储的。

在B+树中，最底层的节点包含了所有的键，这些节点通常是链接的，通常只在前进方向上（即向右），但也完全可以在相反的方向上保持链接，而不增加上述操作的时间复杂度。

考虑到这两点，prev-next操作显然可以执行在 O(1) 时间。

Answer 4

如果你的元素是整数，你可以使用 y-fast trie 支持所有上述操作，耗时O(log log m)。另外，几乎所有的搜索树都可以在O(log n)时间内完成这些操作，只需先上后下就可以了(不过需要非常集中精力，不要把顺序弄乱了)