algorithm - 在 O(log n) 时间内更新

Question

有没有办法在 O(log n) 时间内更新平衡二叉搜索树的节点？

假设有一棵平衡树，使得每个节点都有一个与之关联的索引对象。所以节点 1 将指向对象 1，节点 2 将指向对象 2，依此类推。

如果树中有 100 个节点，并且如果有人决定删除第二个节点，那么我们必须更新剩余的节点，使节点 3 现在指向节点 2，节点 4 现在将指向节点 3，依此类推。

但是这种方法需要 O(n) 时间。

如何在 O(log n) 时间内完成？

Answer 1

如果您的树的实现使得每个节点都有对其子节点的引用，即：

class Node<T>
  Node leftChild
  Node rightChild
  T Data

（与数组或其他方式相反）您所要做的就是更新这些引用（例如，在Wikipedia上概述的红黑树）。

此过程将花费 O(log n) 时间，而不是 O(n) 时间。

如果从树中删除元素 2，节点 2 将随之而来。

Answer 2

该属性听起来更像是一个链接列表而不是树。但是二叉搜索树中的删除是O(h)，树的高度。因为它是平衡的O(log n)。