有没有办法在O(log n)时间内更新平衡二叉搜索树的节点？
假设有一棵平衡树，每个节点都有一个与之关联的索引对象。所以节点 1 将指向对象 1，节点 2 将指向对象 2，依此类推。
如果树中有 100 个节点，如果有人决定删除第二个节点，那么我们必须更新剩余的节点，这样节点 3 现在将指向节点 2，节点 4 现在将指向节点 3，并且等等。
但是这个方法需要O(n)的时间。
如何在 O(log n) 时间内完成？
最佳答案
如果你的树是这样实现的，每个节点都有对其子节点的引用，即:
class Node<T>
Node leftChild
Node rightChild
T Data
(与数组或其他方式相反)您只需更新这些引用(例如 Wikipedia 中概述的红黑树)。
这个过程将花费 O(log n) 时间，而不是 O(n) 时间。
如果从树中删除元素 2，节点 2 也会随之删除。
关于algorithm - 在 O(log n) 时间内更新，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12357495/