删除节点与树的退化

复习

　　二叉搜索树的查找、插入都很顺，但删除要麻烦一些。麻烦在哪？在于删掉一个节点后，还得维持那条“左小右大”的规则。

　　删除一个节点，按它的孩子情况分三种：

　　如果一个节点既有左孩子又有右孩子，直接删掉就会留下两个“孤儿”，接替位置的规则也说不清。

　　常见的做法是：找一个合适的节点来替代它。通常选中序后继（右子树里最小的那个），或者中序前驱（左子树里最大的那个）。把这个替代节点的值搬到要删的位置，再把它自己按前两种情况删掉。

　　为什么选中序后继？因为它比左子树都大、又比其他右子树都小，放到原位刚好满足规则。找到正确的“接班人”，是删除能保持有序的关键。

　　不过，二叉搜索树有一个隐患：它的形状，完全取决于插入顺序。

　　如果数据恰好按从小到大（或从大到小）的顺序插入，每个新节点都会一路往同一个方向挂，树就长成了一条斜线——退化成了链表。

　　一旦退化成链表，高度变成 O(n)，查找也就成了 O(n)。原本 O(log n) 的优势荡然无存。同样的数据，换个插入顺序，性能可能一个天上一个地下。

　　这说明：二叉搜索树的效率，并不由数据本身保证，而“树够不够平衡”才是关键。怎样在插入删除的过程中，始终把树维持得矮而匀称？下一章来解决。

思考题 1

　　删除一个有两个子节点的 BST 节点，为什么不能直接删掉？

思考题 2

　　在什么情况下，二叉搜索树会退化成链表？

　　因为它有两个子节点，直接删会留下两棵子树无人接替，而且需要维持“左小右大”的规则。正确做法是找一个合适的节点（如中序后继）来顶替其值，再把这个顶替节点本身删掉。

　　当插入的数据基本有序时，每个新节点都会沿着同一个方向挂上去，树会变成一条斜线，也就是退化成链表。这时高度为 O(n)，查找也随之变为 O(n)。

设计师 | 南国微雪