数据结构 | 二叉搜索树，平衡二叉树
二叉搜索树
所有的节点都满足左子树的所有节点都比自己的小，而右子树上的所有节点都比自己大这一条件。
可高效进行如下操作：
- 查询是否包含某个数值
- 插入一个数值
- 删除某个数值
查询：
找——>找——>找
插入：
找——>找——>找
删除：
搜索删除数值->找该位置替代元素
- 需要删除的节点没有左儿子，那么就把右儿子提上去。
- 需要删除的节点的左儿子没有右儿子，那么就把左儿子提上去。
- 以上两种情况都不满足的话，就把左儿子的子孙中最大的节点提到需要删除的节点上。
二叉搜索树的时间复杂度
这三种操作，所花的时间都和树的高度成正比。
如果共有n个元素，那么平均每次操作需要O(logn)的时间复杂度。
平衡二叉树
平衡二叉树为了避免这种退化的情况发生，巧妙的使用旋转操作来保持树的平衡。
平衡二叉树： 它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
或一棵空树。
????平衡二叉树的常用实现方法：
- 红黑树
- AVL
- 替罪羊树
- Treap
- 伸展树