二叉排序树
二叉排序树或者是一颗空树或者是具有如下特性的二叉树
1.若它的左子树不空，则左子树上所有结点的值均小于根结点的值
2.若它的右子树不空，则右子树上所有结点的值均大于根结点的值
3.它的左右子树也都分别是二叉排序树
通常使用二叉链表作为二叉树的存储结构
二叉排序树的查找：若给定值等于根结点的关键字，则查找成功；若小于，则取左子树找；若大于，则取右子树找。
平均查找长度与高度有关，高度越高，花的时间越长。AVL树是最矮的平衡二叉树，所有其查找时间也最短。
BSTNode *BST_Search(BItTree T,ElemType key,BSTNode *&P){
P = NULL;//p指向被查找结点的双亲结点
while(T!=NULL&&key!=T->data){
p =T;
if(key < T -> data)
T = T -> lchild;
else
T = T -> rchild;
}
return T;
}
二叉排序树的插入：“插入”是在查找不成功是进行的
直接上代码吧
Int BST_Insert(BiTree &T,keyType k){
If(T == NULL){
T = (BiTree)malloc(sizeof(BSTNode));
T -> key = k;
T ->lchild = T ->rchild =NULL;
Reutrn 1;//success
}
Else if(k==T ->key)
Return 0;//树中有相同结点，不插了
Else if(k < T -> key)
Return BST_Insert(T -> lchild,k);
Else if(k > T -> key)
Return BST_Insert(T -> rchild,k);
}
二叉排序树的删除
要求删除二叉树上某个结点之后，仍然保持二叉排序树的特性
分三种情况讨论：
1.被删除的结点是叶子结点
直接删了就行了
2.被删除的结点只有左子树或只有右子树
让双亲指向该结点的指针直接指向其子树即可
3.被删除的结点既有左子树，也有右子树
在右子树中寻找中序第一个子女填报，就把问题转换成了删另一个结点了，以此类推
平衡二叉树（AVL树）
树中每个结点的左、右子树深度之差的绝对值不大于1，也是一种特殊的二叉查找树
插入算法思想
1.按照二叉排序树的定义，将结点s插入
2.在查找结点s的插入位置过程中，记录离结点s最近且平衡因子不为0的结点a，若该结点不存在，则结点a指向根结点
3.修改结点a好结点s路径上所有结点的平衡因子
4.判断是否产生不平衡，若不平衡，则确定旋转类型并做相应调整
插入之后分别有四种型：LL,RR,LR,RL
LL:右单旋转
RR:左单旋转
LR:先左后右双旋转
RL:先右后左双旋转
举一个例子吧，按5、4、2、8、6、9顺序来插入
先插入5
再插入4，形成
5
4
再插入2
5
4
2
5这个点不平衡，是LL型
右旋转
4
2 5
插入6
4
2 5
6
插入8
4
2 5
6
8
5这个点不平衡,RR型
左旋转
4
2 6
5 8
插入9
4
2 6
5 8
9
此时4点不平衡，为RR型
左旋转
6
4 8
2 5 9
AVL树的查找：含n个结点的平衡二叉树的最大深度为O(log2n)，其平均查找长度也是O(log2n)
B-树
B-树的查找过程
从根结点触发，沿指针搜索结点和在结点内进行顺序查找，两个过程交叉进行。
若查找成功，则返回指向被查找关键字所在结点的指针和关键字在结点中的位置。
B-树的插入与分裂
由于每个结点能盛放的数据是有限制的，所以在超过所能盛放的上限后，会进行分裂。
主要做法是把中间的数据往上提
B-树的删除
若删除之后不影响该树，则直接删掉
若影响，分两种情况
1.兄弟可借，从兄弟拉一个到父结点，从父结点拉一个下来
2.兄弟不可借，让一个父结点和一个兄弟结点合并
B+树
B-树和B+树的主要区别
1.若一个结点有n棵子树，则必含有n个关键字
2.所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接
3.所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大（或最小）关键字
网友评论