algorithm

二叉搜索树的删除

Posted by ysd on August 29, 2016

结点Z没有孩子结点，那么直接删除Z就行了。
结点Z有一个孩子结点，那么删除Z，将Z的父结点与此孩子结点（子树）关联就可以了。（图中的a和b）
结点Z有两个孩子结点，删除Z该怎样将Z的父结点与这两个孩子结点关联呢？这种情况下不能直接删除Z，而是要用Z的后继（比Z的键值稍大的结点）来替代Z。实现方法就是将后继从二叉树中删除，将后继的数据覆盖到Z中。