1、二叉排序树删除节点P

假设节点P是节点F的左子树

1）节点P无子节点

      直接删除，其他节点不动。

2）节点P只有左子节点Pl或者右子节点Pr

      删除P，将Pl或者Pr挂载为F节点的左子树。如果P为F的右子树，则挂载为F的右子树。这样也不会破坏二叉排序树的特性（指排序的变化）。

3）节点P既有左子树Pl，又有右子树Pr

      这种情况下，有两种操作方法：一、将左子树Pl挂载为F的左子树，右子树Pr挂载为Pl的最大值子节点S的右子树（最初最大值子节点S一定没有右子树），；二、将Pr的最大子节点S直接替换到P的位置，然后S的左子树（假如有的话）挂载为S的双亲节点的右子树。

      假如P是节点F的右子树：一、将Pr挂载为F的右子树，Pl挂载到Pr的最小值节点Smin的左子树（即Pr的最左边）；二：用Smin替换P，Smin的右子节点挂载为Smin的双亲节点的左子树。

      方法二，是用直接前驱替代P，可以用直接后驱替代P。也会有样的效果。

以上描述显得难以理解，翻译成自己的理解：删除P后，P的左子树Pl和右子树Pr重新组合为一个二叉排序树，然后挂载为F的左子树。删除P后有4个子节点Pl的根节点、最大值节点S，Pr的根节点、最小值节点Smin，依次以这4个子节点为新的二叉排序树的根节点来进行组合，其中S和Smin作为根节点需要移动位置。

二叉排序树