O(logn) 从链表的特定位置插入和删除节点？
O(logn) to insert and delete node from specific position of linked list?
我在想是否有可能想出一个比 O(N) 更快的解决方案来从双向或单向链表的特定索引中插入或删除。我提出了 O(logN) 解决方案的一部分，但卡住了。我想知道是否有人可以继续该解决方案或表明它不起作用。
使用Self Balanced BST：节点的索引是键，链表中指向节点的指针是值。在index = X处插入BST时，在O(logn)中找到key=X，然后在这个index=X和父节点之间插入一个新节点。由于这是一个不同于正常的插入过程，我们需要更新所有子节点的权重。此外，右子树的所有内容都需要递增 1，以表示 LL 中节点的索引移位。这将花费 O(n) 时间，因此我们需要找出一种有效执行此操作的方法。
我们的想法是等到新的搜索或平衡过程以更新子项。在每个节点中保留两个额外的布尔值：一个用于确定是否所有左侧子节点都需要递增，右侧也同样如此。
现在我们已将工作推迟到执行搜索时，我们会增加密钥并根据需要更改布尔值。
问题出在平衡过程中。看起来真的很复杂，找不到具体的解决办法。此外，还有一些我不熟悉的不同风格的树木。有什么想法吗？
还有，有没有想过这个问题？
Use Self Balanced BST
是的，这就是解决方案。
the index of the nodes are keys [...] Additionally, everything to the right subtree needs to be incremented by 1 to represent the index shift of nodes in the LL. [...] The idea would be to wait ...
这个想法不对。不是存储索引，而是维护一个 size 属性，该属性存储该节点是其根的子树中的节点数。因此，如果节点是叶子，则 size 为 1（节点本身）。它有两个 children 是叶子然后它将是 3，等等
The problem is during balancing.
你的想法确实很难。使用 size 属性会更容易。
首先：查找索引的算法如下：
如果索引小于左子树的大小，则向左走，否则向右走，此时索引减去左子树的大小。
继续此过程，直到索引为 0。
如果需要插入一个新节点，将其插入那里，并增加您通过上述过程遍历的每个节点的大小属性（即在从根到插入叶的路径上).
为了平衡，您可以使用 AVL 旋转。这意味着节点还需要配备平衡因子（AVL 的标准功能）。除了标准的 AVL 旋转算法之外，您还需要更新旋转节点的 size 属性，但这只是涉及节点的 adding/subtracting 大小的问题。
我在想是否有可能想出一个比 O(N) 更快的解决方案来从双向或单向链表的特定索引中插入或删除。我提出了 O(logN) 解决方案的一部分，但卡住了。我想知道是否有人可以继续该解决方案或表明它不起作用。
使用Self Balanced BST：节点的索引是键，链表中指向节点的指针是值。在index = X处插入BST时，在O(logn)中找到key=X，然后在这个index=X和父节点之间插入一个新节点。由于这是一个不同于正常的插入过程，我们需要更新所有子节点的权重。此外，右子树的所有内容都需要递增 1，以表示 LL 中节点的索引移位。这将花费 O(n) 时间，因此我们需要找出一种有效执行此操作的方法。
我们的想法是等到新的搜索或平衡过程以更新子项。在每个节点中保留两个额外的布尔值：一个用于确定是否所有左侧子节点都需要递增，右侧也同样如此。
现在我们已将工作推迟到执行搜索时，我们会增加密钥并根据需要更改布尔值。
问题出在平衡过程中。看起来真的很复杂，找不到具体的解决办法。此外，还有一些我不熟悉的不同风格的树木。有什么想法吗？
还有，有没有想过这个问题？
Use Self Balanced BST
是的，这就是解决方案。
the index of the nodes are keys [...] Additionally, everything to the right subtree needs to be incremented by 1 to represent the index shift of nodes in the LL. [...] The idea would be to wait ...
这个想法不对。不是存储索引，而是维护一个 size 属性，该属性存储该节点是其根的子树中的节点数。因此，如果节点是叶子，则 size 为 1（节点本身）。它有两个 children 是叶子然后它将是 3，等等
The problem is during balancing.
你的想法确实很难。使用 size 属性会更容易。
首先：查找索引的算法如下：
如果索引小于左子树的大小，则向左走，否则向右走，此时索引减去左子树的大小。
继续此过程，直到索引为 0。
如果需要插入一个新节点，将其插入那里，并增加您通过上述过程遍历的每个节点的大小属性（即在从根到插入叶的路径上).
为了平衡，您可以使用 AVL 旋转。这意味着节点还需要配备平衡因子（AVL 的标准功能）。除了标准的 AVL 旋转算法之外，您还需要更新旋转节点的 size 属性，但这只是涉及节点的 adding/subtracting 大小的问题。