在二叉搜索树中删除一个节点

我正在阅读一本关于从二叉查找树中删除节点的书，本书中描述的过程似乎对我来说过于复杂。在二叉搜索树中删除一个节点

我的问题是关于删除一个既有左侧子树又有右侧子树的节点。在我看来，如果节点的左子树只有一个节点，应该用左子树中最右端的节点或左子节点替换节点。 enter image description here

在情况1中，如果我们删除40，它将被替换为30;在No.2的情况下，如果我们删除40，它将被替换35.

但是在书中，它说替换应该从节点到删除的右子树中找到，这可能涉及一些复杂的操作。

我在这里错过了什么吗？请指出。

2014-02-15 nyus2006

你指出的是正确的，被删除的节点应该被替换为或者它的后继者，它是右子树中最左边的节点或者它的最前面的节点是最右边的节点在左边的子树中。这允许树被正确地遍历。大多数二叉搜索树数据结构允许以任何一种方式执行删除，但在某些情况下，您可能希望执行删除以使树保持平衡。

更多详细信息和样例代码请见Wikipedia。

来源

2014-02-15 17:03:28 Vishal

感谢您的回答和链接。 – nyus2006

在1号的情况下，如果您删除节点40将通过50

被替换2号的情况下，如果你删除一个节点40将通过50

因此，基本上可以取代我们的时候删除任何有2个孩子的节点，然后删除应该如下。我们去节点的右边的孩子，然后是那个孩子的最左边。

下图显示了一些例子，如何从二叉搜索树中删除一个节点。这也取自一本书，但它被清楚地解释。

enter image description here

来源

2014-02-15 17:06:30 eswaat

请参阅Vishal的答案并阅读维基链接。将node-to-remove替换为左子树的最右边的子元素，或者右子树的最左子元素可以工作，只需从右子树中选择即可防止发生不平衡树，从而导致长期效率低下。 – nyus2006

感谢您花时间和美丽的图形解释。 – nyus2006

@ S.H。总是选择有序的继任者最终会导致树不平衡。如果你随机选择继承者和前任者，那么你的树不太可能变得不平衡。如果你需要一个平衡的二叉搜索树，那么你需要创建一个函数来平衡树插入和删除，如果你想查看一个这样做的例子，请看[AVL树]（http：// en.wikipedia.org/wiki/AVL_tree）。 – Vishal

在二叉搜索树中删除一个节点

回答

相关问题