c++ - 二叉搜索树删除而不复制

Question

在编写简单的二叉搜索树数据结构（非自平衡）时，大多数资源在删除具有两个子节点的节点时给出的建议是将数据从左子节点之一复制到要删除的节点。这是不好的做法吗？某种指针操作不会提供更快的结果吗？是否有可以概括这一点的 BST 旋转算法？

Answer 1

是的，您不想复制节点，您只想“移动”它（即更改指针）以将其放入您要删除的节点的位置。如果您不想保持平衡，则实际上不需要进行任何旋转-您只需选择左子树中最右侧的节点（或右子树中的最左侧节点-树）。您将其从当前位置删除，并将其插入您需要删除的节点的位置（所有这些都严格通过操作指针）。

Answer 2

复制数据的复杂度为 O(1)，而操作指针时可能的复杂度为 O(N)：源节点（左子树中最右边的节点或右子树中最左边的节点）可能有一个child 和它下面的子树。与单个节点插入不同，在这种情况下需要合并子树。为了避免复制开销，应该在 BST 中存储指向对象而不是对象的指针。