• 第7章-查找

    目录

    顺序查找

    一般线性表的顺序查找

    有序表的顺序查找

    折半查找

    分块查找

    二叉排序树BST

    二叉排序树的查找

    二叉排序树的插入

    二叉排序树的构造

    二叉排序树的删除

    二叉排序树的查找效率分析

    平衡二叉树

    平衡二叉树的插入

    平衡二叉树的删除

    红黑树

    基本定义、结论

    红黑树的插入

    红黑树的删除

    待补充 

    B树

    B+树

    顺序查找

    一般线性表的顺序查找

    1. typedef struct{//查找表的数据结构 
    2. 	ElemType *elem;//元素存储空间基址，建表时按实际长度分配，0号单元留空
    3. 	int TableLen;//表的长度 
    4. }SSTable;
    5. int Search_Seq(SSTable ST,ElemType key){
    6. 	ST.elem[0]=key;//哨兵
    7. 	for(i=ST.TableLen;ST.elem[i]!=key;--i);//从后往前找
    8. 		return i;//若表中不存在关键字key的元素，将查找到i为0时退出for循环 
    9. }

    对线性的链表只能进行顺序查找。 

    ASL_{success}=\sum_{i=1}^{n}P_{i}(n-i+1)=\frac{n+1}{2}，P_{i}=\frac{1}{n}

    ASL_{fail}=n+1

    有序表的顺序查找

    查找成功的平均查找长度和一般线性表的顺序查找一样。

    ASL_{fail}=\sum_{j=1}^{n}q_{j}(l_{j}-1)=\frac{1+2+...+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}

    ~比一般顺序查找算法好一些；

    可以是链式存储结构。

    折半查找

    二分查找，仅适用于有序的顺序表。

    1. int Binary_Search(SeqList L,ElemType key){
    2. 	int low=0,high=L.Tablelen-1,mid;
    3. 	while(low
    4. 		mid=(low+high)/2;//取中间位置
    5. 		if(L.elem[mid]==key)
    6. 			return mid;//查找成功，返回所在位置
    7. 		else if(L.elem[mid]>key)//从前半部分继续查找 
    8. 			high=mid-1;
    9. 		else low=mid+1; //从后半部分继续查找 
    10. 	}
    11. 	return -1;查找失败，返回-1 
    12. }

    判定树是一个平衡二叉树。

     圆形节点是查找成功。 

    ASL_{success}=\frac{1}{n}\sum_{i=1}^{n}l_{i}=\frac{1}{n}(1\times1+2\times2+...+h\times2^{h-1} )=\frac{n+1}{n}log_{2}(n+1)-1\approx log_{2}(n+1)-1

    h是树的高度。元素个数为n的时，树高h=\left \lceil log_{2}(n+1) \right \rceil

    方形节点是查找失败。

    仅适用于顺序存储结构，不适用于链式存储结构，且要求元素按关键字有序。

    分块查找

    索引顺序查找，既有动态结构，有适于快速查找。块内的元素可以无序，但块之间是有序的。

    1  在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表

    2  在块内顺序查找

    L_{I},L_{S}分别是索引查找和块内查找的平均查找长度，将长度为n的查找表均匀地分为b块，每块有s个记录。

    ASL=L_{I}+L_{S}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^{2}+2s+n}{2s}

    若s=\sqrt{n}，则平均查找长度取最小值\sqrt{n}+1，若对索引表采用折半查找，则

    ASL=L_{I}+L_{S}=\left \lceil log_{2}(b+1) \right \rceil+\frac{s+1}{2}

    二叉排序树BST

    也称二叉查找树。对BST进行中序遍历，得到一个递增的有序序列。

    二叉排序树的查找

    二叉排序树的非递归查找算法

    1. BSTnode *BST_Search(BiTree T,ElemType key){
    2. 	while(T!=NULL&&key!=T->data){//若树空或等于根结点值，则结束循环
    3. 		if(keylchild;//小于，则在左子树上查找
    4. 		else T=T->rchild;//大于，则在右子树上查找 
    5. 	}
    6. 	return T;
    7. }

    二叉排序树的插入

    插入的结点一定是一个新添加的叶结点。

    1. int BST_Insert(BiTree &T,KeyType k){
    2. 	if(T==NULL){//原树为空，新插入的记录为根结点
    3. 		T=(BiTree)malloc(sizeof(BSTNode));
    4. 		t->data=k;
    5. 		T->lchild=T->rchild=NULL;
    6. 		return 1;//插入成功 
    7. 	}
    8. 	else if(k==T->data)//树中存在相同关键字的结点，插入失败
    9. 		return 0;
    10. 	else if(kdata)
    11. 		return BST_Insert(T->lchild,k);//插入到T的左子树 
    12. 	else 
    13. 		return BST_Insert(T->lchild,k);//插入到T的右子树 
    14. }

    二叉排序树的构造

    1. void Creat_BST(BiTree &T,KeyType str[],int n){
    2. 	T=NULL;//初始T为空
    3. 	int i=0;
    4. 	while(i//依次将每个关键字插入到二叉排序树中 
    5. 		BST_Insert(T,str[i]);
    6. 		i++;
    7. 	} 
    8. }

    二叉排序树的删除

    1. 若被删除结点z是叶子结点，则直接删除，不会破坏二叉排序树的性质。
    2. 若z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
    3. 若z右左、右两颗子树，则令z 的直接后继（或直接前驱) 替代z，然后从而差排序树中删除这个直接后继（或直接前驱)，这样就转换成了第一或者第二种情况。

    二叉排序树的查找效率分析

    二分查找的判定树唯一，二叉排序树的查找不唯一，相同关键字其插入顺序不同可能产生不同的二叉排序树

    平衡二叉树

    平衡二叉树的插入

    先找到 插入路径上 离插入结点 最近的平衡因子 的绝对值大于1 的结点A，再对以A为根的子树，调整位置，使重新达到平衡。

    LL平衡旋转（右单旋转）

    RR平衡旋转（左单旋转）

    LR平衡旋转（先左后右双旋转）

     

    RL平衡旋转（先右后左双旋转）

    平衡二叉树的删除

    与插入操作的调整方式一样，不同之处在于，插入操作仅需要对以z为根的子树进行平衡调整，而删除操作先对以为根的子树进行平衡调整，若调整后子树高度减1，则可能需要对z的祖先结点进行平衡调整，甚至回溯到根结点。

    红黑树

    基本定义、结论

    是满足条件的二叉排序树

    左根右，根叶黑

    不红红，黑路同

    每个结点是红色或黑色的

    根结点是黑色的

    叶结点是黑色的（虚构的外部结点，NULL结点）

    不存在两个相邻的红结点，（即红结点的父结点和孩子结点都是黑色的）

    对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的 数量相同

    结论： 

    • 从根到叶结点的最长路径不大于最短路径的2倍。
    • 有n个内部结点的红黑树的高度h\leq2log_{2}(n+1) 

    红黑树的插入

    结论： 

    • 新插入红黑树中的结点初始着色为红色

    用二叉查找树插入法插入，并将结点z着为红色，若结点的父结点时黑色的，无需调整。

    如果z是根结点，将z着为红色，树的高度增加1，结束。

    若z不是根结点，并且z的父结点z.p是红色，则

            1  z的叔结点y是黑色的，且z是一个右孩子（LR）

            2  z的叔结点y是黑色的，且z是一个左孩子（LL）

            3  z的叔结点y是红色的

     

     

    红黑树的删除

    用二叉查找树删除法，若待删除结点有两个孩子，找到该结点的中序后继（或前驱）填补，即右子树中最小的结点，然后转换为删除该后继结点。 

    待删除结点没有孩子

            若该结点是红色的，直接删除。无需调整。

            若该结点是黑色的， 4种情况 图7.23-7.26

    1  x的兄弟结点w是红色的

    2  x的兄弟结点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的

    3  x的兄弟结点w是黑色的，且w的右孩子是红色的

    4  x的兄弟结点w是黑色的，且w的两个孩子结点都是黑色的

     待删除结点只有右子树或左子树，则只有两种情况

     

    完整例子

    待补充 

    B树

    多路平衡查找树

    B+树

  • 相关阅读:
    彻底弄懂C#中delegate、event、EventHandler、Action、Func的使用和区别
    秋招面试！阿里、字节、美团等大厂面试我只刷这份《Java面试题》没想到还真拿下了offer！
    购物车的原理及实现
    【算法】背包问题应用
    Redis总结：缓存雪崩、缓存击穿、缓存穿透与缓存预热、缓存降级
    JS/JQ动态创建（添加）optgroup和option属性
    什么是函数库和动态链接库？
    AUTOSAR汽车电子嵌入式编程精讲300篇-汽车 CAN FD 总线应用研究
    少儿编程是智商税吗？不花钱让孩子赢在起跑线
    中等array and sorting ：count and say
  • 原文地址：https://blog.csdn.net/qq_45181299/article/details/126126338