一.二叉排序树（二叉查找树）

性质：

要么是空树，要么是具有下列性质的二叉树:

①若左子树不为空，那么左子树上所有节点的值均小于根节点的值

②若右子树不为空，那么右子树上所有节点的值均大于根节点的值

③左右子树都是二叉排序树.

例如下图:

特点:

中序遍历将得到一个有序序列

存储结构：二叉链表

操作:

1.二叉排序树的查找

设要查的值为K，那么如果now指针为空，则查找失败，否则

①now->data  <  K,向now的右子树查找

②now->data > K,向now的左子树查找

2.二叉排序树的插入

先查找再插入，过程与上面差不多.now为空时则找到插入位置，插入。

值得注意的是，当有重复的值出现的时候，如果应用要求无重复，则查找失败。否则，通常插入到右子树.

3.二叉排序树的建立:插入

4.二叉排序树的删除

分情况讨论:设要删除的点为p点，其双亲为s点.

①p点为叶子结点，直接删除p点

②p点只有左子树或右子树，将左/右孩子代替p点再删除p点.

③左右子树都有,那么我们需要寻求一个最合适的节点来代替p点。两种方法，用左子树的最大值或右子树的最小值来代替p点。具体做法是走右子树，之后一直往左子树走，直至叶节点s,赋data给p,删除s点(注意s点可能有右孩子，要将s点的右孩子往上接).    还有一种情况，p点的右孩子就是右子树最小者.那么就将s的右孩子接在p点上.

(代码实现:传参数p，f代表要删除的点以及其双亲节点)

5.二叉排序树的性能分析:

斜树O(n),满二叉树O([logn] + 1);

二.平衡二叉树

前言:

从第五点可以看出,树的形态影响着排序二叉树的时间复杂度，而树的形态受输入的序列的影响，而序列的顺序是无法控制的，这自然就要求我们寻找一种动态平衡。

性质:

要么是棵空的二叉排序树，要么具有以下性质:

①根节点的左子树和右子树的深度最多相差1

②根节点的左子树和右子树都是平衡二叉树

概念:

平衡因子：左右子树深度之差.

最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树.

最小不平衡点：上述的那个节点.

平衡调整：（核心：扁担原理，子树分配）

①LL型，RR型 (多出一个子树 ):将重的孩子往上提，多出来的子树分配给原先的不平衡点(不然没地方去)

②LR型，RL型(多出两个子树)：两个步骤.将重的子树往上提，其中一个子树分配到下降的节点去，再以上面一个点为重心，将重的子树往上提，其中一颗子树分配到下降的节点去。

复杂度:O(logn)