(1) 定义：二叉排序树或者是一棵空树, 或者是具有如下性质的二叉树。
① 若它的左子树非空，则左子树上所有结点的值均小于根结点的值。
② 若它的右子树非空, 则右子树上所有结点的值均大于根结点的值。
③ 它的左右子树也分别为二叉排序树。
二叉排序树的特性：中序遍历的结果为一个递增的有序序列。逆中序遍历的结果为一个递减的有序序列。
(2) 存储结构描述
typedef struct node {
KeyType key;
struct node *lchild,*rchild;
} BSTNode,*BSTree;
二叉排序树的插入与创建
(1) 二叉排序树的插入
插入关键字key的算法思想：
若二叉排序树是空树，则key成为二叉排序树的根。
否则，则将key与二叉排序树的根进行比较：
如果key的值小，则将key插入左子树。
如果key的值大，则将key插入右子树。
例：在二叉排序树插入28
二叉排序树插入一个结点，一定是叶子结点。不需要移动其他记录。
时间复杂度：O(log2n)
(2) 二叉排序树的创建
首先，将二叉排序树初始化空树。
依次读入key的值，并插入到二叉排序树。
例1：输入顺序
45,24,53,12,28,90
例2：输入顺序
24,53,90,12,28,45
二叉排序树的形态与关键字的输入序列有关。时间复杂度：O(nlog2n)
(1) 算法思想
若二叉排序树是空树，则查找失败。
否则，则将key与二叉排序树的根进行比较：
如果相等，则返回根结点地址。
如果key的值小，则在左子树查找。
如果key的值大，则在右子树查找。
ASL1=(1+2+2+3+3+3)/6=14/6
ASL2=(1+2+3+4+5+6)/6=21/6
(2) 平均查找长度
在二叉排序树进行查找时，ASL与二叉排序树的形态有关。查找效率取决于树的深度。
最坏形态：二叉排序树蜕化为深度为n的单支树，查找蜕化为单链表的顺序查找，ASL=(n+1)/2。
最佳形态：分支均衡，ASL=O(log2n)。
平衡二叉排序树
(1) 删除一个结点的含义
从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。
(2) 算法思想
首先查找要删除的结点，看是否在二叉排序树中，若不在，则不做任何操作; 否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子(右孩子的情况类似)。
下面分三种情况讨论。
① 若p为叶结点
方法：直接将其删除
f->lchild = NULL;
free§;
删除前中序遍历：P、F、FR
删除后中序遍历：F、FR
② 若p结点只有左子树，或只有右子树
方法：将p的左子树或右子树直接改为其双亲结点f的左子树
f->lchild=p->lchild;
或f->lchild=p->rchild;
free§;
删除前中序遍历：CL、C、CR、P、F、FR
删除后中序遍历：CL、C、CR、F、FR
删除前中序遍历：P、CL、C、CR、F、FR
删除后中序遍历：CL、C、CR、F、FR
③ 若p既有左子树, 又有右子树
方法1：(分布法)
将p的左子树改为f的左子树; 将p的右子树改为s的右子树。
f->lchild=p->lchild;
s->rchild=p->rchild;
free§;
删除前中序遍历：CLC…QLQSLSPPRFFR
删除后中序遍历：CLC…QLQSLSPRFFR
方法2：(替代法)
将用s结点替代p结点，原s结点的左子树改为s的双亲结点q的右子树
p->data=s->data;
q->rchild=s->lchild;
free(s);
CLC…QLQSLSPPRFFR
CLC…QLQSLSPRFFR
平衡二叉排序树又称AVL树。一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
① 左子树和右子树的高度之差的绝对值小于等于1
② 左子树和右子树也是平衡二叉树。
结点的平衡因子：结点的左子树深度与右子树深度之差。
AVL树结点平衡因子值域：-1、0、1。
LL平衡旋转
RR平衡旋转
LR平衡旋转
RL平衡旋转
LL平衡旋转：左单旋
以B为轴，对A做一次顺时针旋转
RR平衡旋转：右单旋
以B为轴，对A做一次逆时针旋转
LR平衡旋转：左右双旋
以C为轴，对A做一次顺时针旋转，对B做一次逆时针旋转。
RL平衡旋转：右左双旋
以C为轴，对A做一次逆时针旋转，对B做一次顺时针旋转。
LL例：A的左子树B的左子树上插入15
RR例：A的右子树B的右子树上插入70
LR例：A的左子树B的右子树上插入45
RL例：A的右子树B的左子树上插入55
调整：平衡最下面失衡子树
域bf：平衡二叉排序树结点平衡因子域
约定：用来表示结点的字母，同时也用来表示指向该结点的指针。如新结点S，失衡结点A。
FA：结点A的父指针。
fp：结点p的父指针。
(1) LL型
失衡特点：A->bf=2,B->bf=1
调整操作：
A->lchild=B->rchild;
B->rchild=A;
A->bf=0;
B->bf=0;
(2) RR型
失衡特点：A->bf=-2,B->bf=-1
调整操作：
A->rchild=B->lchild;
B->lchild=A;
A->bf=0;
B->bf=0;
(3) LR型
失衡特点：A->bf=2,B->bf=-1
调整操作：
B->lchild=C->lchild;
A->rchild=C->rchild;
C->lchild=B; C->rchild=A;
平衡因子调整情形1：在CL下插入S
if(S->keykey)
{A->bf=-1; B->bf=0; C->bf=0;}
平衡因子调整情形2：在CR下插入S
if(S->key>C->key)
{A->bf=0; B->bf=1; C->bf=0;}
平衡因子调整情形3：C就是S
if(S->key==C->key)
{A->bf=0; B->bf=0;}
失衡特点：A->bf=-2,B->bf=1
调整操作：
B->lchild=C->rchild;
A->rchild=C->lchild;
C->lchild=A; C->rchild=B;
平衡因子调整情形1：在CL下插入S
if(S->keykey)
{A->bf=0; B->bf=-1; C->bf=0;}
平衡因子调整情形2：在CR下插入S
if(S->key>C->key)
{A->bf=1; B->bf=0; C->bf=0;}
平衡因子调整情形3：C就是S
if(S->key==C->key)
{A->bf=0; B->bf=0;}
m叉排序树又称m路查找树。
例如：一棵3路查找树,查找关键字35
B-tree即B树或B-树，是一棵平衡的m阶查找树，它或者是空树，或者是满足如下性质的树：
每个结点最多有m棵子树
根结点至少有两棵子树
除根结点之外的所有非叶结点至少有[m/2]棵子树
叶结点(失败结点)：处于同一层，不含信息，是不存在的虚结点，父指针为空。
例如：一棵4阶B树,查找关键字58
组成：父指针、关键字个数n、子树指针、关键字
例：具有n个非叶结点的m阶B树，至少含有多少个关键字？
1+([m/2]-1) ×(n-1)
例：已知一棵3阶B树含有2047个关键字，那么包括叶结点(失败结点)层，该B树的最大深度是多少？
分析：
根结点：至少有2棵子树
其它非叶结点：至少有[m/2]棵子树，而m=3+1，即[4/2]=2。
所以，该树是满二叉树。
深度=log22048=11
考虑失败结点层：最大深度=12
例如：
哈希表长度m=12
哈希函数：h0=H(key)=key%11
冲突处理：hi=(h0+di)%m i=1,2,…n
记录关键字：60、26、47、69
查找则是直接计算的地址的过程
欢迎大家加我微信交流讨论（请备注csdn上添加）
