所以我得到了这个任务来建议一个AVL树，它能够在O(1)：中执行剩余的两个操作
继承人取得(1)-返回继承人。前置机获取(1)-返回前置机
在尝试想出解决方案后，我有点不知所措。有什么想法吗？
我认为，与其说是修改树或实现任何复杂的前置器/后续器查找逻辑，以便能够在恒定时间内物理遍历树以查找后续器/前置器节点，不如说是简单地向树中的每个节点添加succ和pred链接，在predecessor(n)和successor(n)函数中使用它们，以及通过插入和删除操作来维护这些链接。
为了确保successor(n)和predecessor(n)实际上是O(1)，使用这种方法所需要注意的是，维护succ/pred链接的时间复杂性不会超过需要更新链接的操作的复杂性。例如，因为将新节点插入平衡树是一个O(lg n)操作，所以在插入后更新后续/前任链接不能超过O(lgn)(否则，从技术上讲，后续查找的分摊工作量将大于O(1))。
为了维护pred和succ链接，在每次插入和删除操作中必须采取的步骤实际上非常简单，值得庆幸的是，重新平衡操作给AVL树带来的复杂性并没有真正影响它们，因为虽然重新平衡会改变树的结构，但它不会影响树的顺序，因此也不会影响前序/后继关系。
在平衡BST(AVL树保证是)中查找给定节点的后继节点和前导节点是O(lg n)，在逻辑上与在常规BST中查找前导节点和后继节点的操作没有区别。因此，在将新节点n插入AVL后，只需查找n的后继节点或前导节点并更新适当的链接：
insert(n) {
...
# normal AVL insert and rebalance logic
...
predecessor, successor = findPredAndSucc(n)
if (predecessor) predecessor.succ = n
if (successor) successor.pred = n
n.pred = predecessor
n.succ = successor
}
当删除n时，你还必须找到n的前任和继任者，并更新链接，如所示
delete(n) {
# save these values first so they aren't lost when n is deleted
predecessor, successor = findPredAndSucc(n)
...
# normal AVL delete and rebalance logic
...
if (predecessor) predecessor.succ = successor
if (successor) successor.pred = predecessor
}
我稍微混淆了节点n和n的值(如果按值插入/删除，则必须遍历树才能首先找到n)，但你已经明白了。
按照这种方法，在每次插入和删除之后，每个节点将具有到其前任/继任者节点的直接链接，并且由于AVL树的自平衡特性，在插入和删除之后查找相关节点以更新这些链接所花费的时间不会给这些操作增加任何额外的复杂性(查找前置节点和后续节点不需要每个超过2个O(h)＝O(lg n)遍历，其复杂性与插入和删除本身相同，因此不会改变整体复杂性)，因此如果我们的successor(n)和predecessor(n)函数只是遵循我们设置的succ和pred链接，那么它们将是整体O(1)。