二叉搜索树 - 删除与插入。哪个是'faster'？
Binary Search Tree - Deletion vs Insertion. Which is 'faster'?
Investigate what must happen to delete a key from a Binary Search
Tree. Is deletion always as fast as insertion?
我在 BST 中查找了插入和删除。删除似乎更复杂，因为需要重新路由节点，这也意味着需要重新分配和重组密钥。
就速度而言，基于删除的复杂性，我假设这意味着删除不如插入快。
这是一个正确的假设吗？谢谢
虽然最初看起来插入应该更快，但我一点也不相信这是真的，至少在任何显着程度上是这样。
当我们进行插入时，我们总是将新节点作为叶节点的子节点插入。我们要遍历树到叶节点做插入。
当我们做删除的时候，我们要考虑三种情况。最简单的是我们要删除一个叶节点。在这种情况下，我们将父节点指向该叶节点的指针设置为空指针，并释放叶节点占用的内存。与插入没有什么不同。
如果要删除的节点是一个有一个子节点的non-leaf节点，任务只会稍微困难一点：我们将当前节点的父节点设置为指向要删除节点的子节点，并（再次）释放我们要删除的节点占用的内存。
我们唯一一次遇到任何可以被视为额外工作的事情是当我们必须删除一个有两个子节点的 non-leaf 节点时。在这种情况下，我们需要找到一个作为该节点子节点的叶节点——要么是其左子节点的 right-most 后代，要么是其右子节点的 left-most 后代。我们将该节点交换到我们要删除的节点的位置并释放其内存。
这里要记住的是，对于插入，我们首先遍历树到叶子，然后插入。在删除的情况下，我们有可能在before之前一直遍历到一个叶子--但即使在最坏的情况下，我们仍然只是继续遍历直到到达叶子（无论如何我们为插入所做的事情），分配指针以将该节点移动到被删除节点的位置。
这里可能会有一两个额外的赋值（主要取决于你的实现方式），但最多差别非常小。
从实际的角度来看，任何真正的性能差异都可能归结为一个问题：您使用的内存管理是试图平衡分配和删除的成本，还是偏向于其中一个（以及所以，哪个）。
简而言之，根据您的堆管理方式，最慢的部分可能很可能是为节点分配或删除内存，而树操作基本上是迷失在喧嚣中。
Investigate what must happen to delete a key from a Binary Search Tree. Is deletion always as fast as insertion?
我在 BST 中查找了插入和删除。删除似乎更复杂，因为需要重新路由节点，这也意味着需要重新分配和重组密钥。 就速度而言，基于删除的复杂性，我假设这意味着删除不如插入快。
这是一个正确的假设吗？谢谢
虽然最初看起来插入应该更快，但我一点也不相信这是真的，至少在任何显着程度上是这样。
当我们进行插入时，我们总是将新节点作为叶节点的子节点插入。我们要遍历树到叶节点做插入。
当我们做删除的时候，我们要考虑三种情况。最简单的是我们要删除一个叶节点。在这种情况下，我们将父节点指向该叶节点的指针设置为空指针，并释放叶节点占用的内存。与插入没有什么不同。
如果要删除的节点是一个有一个子节点的non-leaf节点，任务只会稍微困难一点：我们将当前节点的父节点设置为指向要删除节点的子节点，并（再次）释放我们要删除的节点占用的内存。
我们唯一一次遇到任何可以被视为额外工作的事情是当我们必须删除一个有两个子节点的 non-leaf 节点时。在这种情况下，我们需要找到一个作为该节点子节点的叶节点——要么是其左子节点的 right-most 后代，要么是其右子节点的 left-most 后代。我们将该节点交换到我们要删除的节点的位置并释放其内存。
这里要记住的是，对于插入，我们首先遍历树到叶子，然后插入。在删除的情况下，我们有可能在before之前一直遍历到一个叶子--但即使在最坏的情况下，我们仍然只是继续遍历直到到达叶子（无论如何我们为插入所做的事情），分配指针以将该节点移动到被删除节点的位置。
这里可能会有一两个额外的赋值（主要取决于你的实现方式），但最多差别非常小。
从实际的角度来看，任何真正的性能差异都可能归结为一个问题：您使用的内存管理是试图平衡分配和删除的成本，还是偏向于其中一个（以及所以，哪个）。
简而言之，根据您的堆管理方式，最慢的部分可能很可能是为节点分配或删除内存，而树操作基本上是迷失在喧嚣中。