二叉树-详解二叉排序树

BST查找时间复杂度

h: 树的高度

$O(h)$

最坏情况下：n个结点，高度为n的树，时间复杂度 $O(n)$

BST删除结点

遍历的时候，用pre记录下查找结点的父结点，用于删除结点

考虑三种情况：

1. 要删除的结点是叶节点

   父节点指向NULL，删除当前节点，

2. 要删除的结点是非叶节点，有一个孩子

   直接将子节点连接至父节点，删除当前结点

   

3. 要删除的结点是非叶节点，有两个孩子

   找中序后继，覆盖当前结点的值，删除中序前驱