二叉排序树删除节点

二叉排序树是一种特殊的二叉树，它的每个节点都含有一个关键字值且满足左子树上所有节点的关键字值都小于该节点的关键字值，右子树上所有节点的关键字值都大于该节点的关键字值。在这种树中，删除某个节点比在普通二叉树中更为复杂，因为节点关键字的大小关系会影响到父节点、子节点和兄弟节点的结构。

删除方法

在二叉排序树中删除一个节点需要分以下几个步骤来进行：

1.查找要删除的节点，同时记录节点的父节点和在父节点左子树还是右子树。

2.如果该节点是叶子节点，直接删除即可。

3.如果该节点只有一个子节点，将该节点子节点的值覆盖到该节点上，并删除该节点的子节点。

4.如果该节点有两个子节点，需要寻找该节点的右子树中的最小值，将该最小值替换删除节点的值，再删除右子树中的最小节点。

举例来说，考虑一个二叉排序树，其结构如下所示：

50

/ \

20 60

/ \ / \

18 30 55 70

删除节点值为20的节点，可以按照以下步骤来进行：

1.查找节点20，其父节点为50，因此要从50的左边删除节点20。

2.Node20是有两个子节点的节点，需要在右子树(30, 55, 70)中找到最小值并将其删除，将55作为最小值替换到节点20上，删除节点55。

3.删除节点55后，右子树结构变为 30 -> 70。

删除节点20后，二叉排序树的结构变为：

50

/ \

30 60

\ / \

18 55 70

接下来分别从多个角度分析二叉排序树删除节点的技术细节。

节点不存在的情况

在二叉排序树删除节点时，如果要删除的节点不存在，则根据二叉排序树的性质可知，根本就没有该节点，因此无须删除。可以对代码进行修改，在删除节点的同时，判断一下节点是否存在，如不存在，则返回删除失败的标志。

代码片段：

BST_Node* BST_Delete(BST_Node* node, BST_Value value)

{

if(node == NULL)

return NULL; //节点不存在，无需删除

if(value == node->value)

{

...

}

else if(value < node->value)

node->left = BST_Delete(node->left, value);

else if(value > node->value)

node->right = BST_Delete(node->right, value);

}

搜索操作的复杂度

二叉排序树最主要的用途就是能够搜索节点。在二叉排序树中搜索节点的复杂度是O(logn)。需要注意的一点是，由于二叉排序树的节点并不是平衡的，因此有极端情况会导致时间复杂度变为线性的O(n)。

需要注意的是，对于具有重复节点值的二叉排序树，删除节点时要考虑是否只删除一个节点，还是删除所有节点。如果只删除一个节点，那么在查找到该节点时，删除该节点并结束查找；如果要删除所有节点，可以在删除时往后继续查找是否还有相同节点值的节点，直到没有为止。