概念
二叉搜索树
二叉搜索树又称二叉查找树，亦称为二叉排序树。设x为二叉查找树中的一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y] <= key[x]；如果y是x的右子树的一个节点，则key[y] >= key[x]
二叉搜索树的特性
- 若左子树不空，则左子树上所有节点的值均小于它的根节点的值
- 若右子树不空，则右子树上所有节点的值均大于它的根节点的值
- 左、右子树也分别为二叉搜索树
二叉搜索树的查找
- 如果树是空的，则查找结束，无匹配。
- 如果被查找的值和节点的值相等，查找成功。
- 如果被查找的值小于节点的值，递归查找左子树
- 如果被查找的值大于节点的值，递归查找右子树
二叉搜索树的查找性能
当数据的数目为N，树的高度近似logN时，其查找性能的时间复杂度为O(logN)。当先后插入的key有序时，二叉搜索树退化为单分支的树结构，此时树的高度与数据的数目相同，因此该情况下查找平均时间复杂度退化为O(N)。
二叉搜索树的插入
- 执行查找流程，此时
- 如果已经存在则不进行插入
- 如果不存在则插入到查找结束的位置
二叉搜索树的插入性能
与二叉搜索树的查找效率相同
二叉搜索树的删除
删除节点为叶子节点
只需查找到该节点，直接删除即可
删除的节点只有左子树
删除的节点若只有左子树，将节点的左子树替代该节点位置
删除的节点只有右子树
删除的节点若只有右子树，将节点的右子树替代该节点位置
删除的节点既有左子树又有右子树
- 遍历待删除节点的左子树，找到其左子树中的最大节点，即删除节点的前驱节点
- 将最大节点代替被删除节点
- 删除左子树中的最大节点
- 左子树中待删除最大节点一定为叶子节点或者仅有左子树
- 递归执行以上过程
删除性能
删除节点时，如果节点为叶子结点，或者结点只有单一子树，则时间复杂度为O(1)。若结点既有左子树又有右子树，则需要进行递归，此时的时间复杂度为O(logN)。
平衡因子
某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子
平衡二叉树
二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序，构造的二叉搜索树可能退化为单链表，此时搜索效率降低为O(N)。平衡二叉树保证节点平衡因子的绝对值不超过1，保证了树的平衡。
平衡二叉树的查找性能
最坏情况下其时间复杂度为T(logN)，因此我们认为平衡二叉树的查找性能为O(logN)。
平衡二叉树的插入和删除性能
与查找性能相同。