折扣网站怎么做,wordpress 显示视频,巩义网站推广优化,创建qq网站吗一、基本术语
二、线性结构
ASL#xff1a;平均查找长度
1、顺序查找
1.1、代码实现
typedef struct {int* elem;int TableLen;
}SSTable;int Search_Seq(SSTable ST, int key) {ST.elem[0] key; //哨兵#xff0c;使得循环不用判断数组是否会越界int i;for (i ST…一、基本术语
二、线性结构
ASL平均查找长度
1、顺序查找
1.1、代码实现
typedef struct {int* elem;int TableLen;
}SSTable;int Search_Seq(SSTable ST, int key) {ST.elem[0] key; //哨兵使得循环不用判断数组是否会越界int i;for (i ST.TableLen; ST.elem[i] ! key; i--);return i;
} 1.2、优缺点 缺当n较大时平均查找长度较大效率低 优对数据元素的存储没有要求顺序存储或链式存储都可以对链表只能顺序查找 对有序线性表的顺序查找查找失败时不需要完整遍历整个线性表从而降低查找失败的平均查找长度。
1.3、应用-有序顺序表上的顺序查找判定树 到达失败节点时所查找的长度等于它上面的一个圆形节点的所在层数
2、折半查找
2.1、代码实现
int Binary_Search(SSTable L, int key) {int low 0, high L.TableLen - 1, mid;while (low high) {mid (low high) / 2;if (L.elem[mid] key)return mid;else if (L.elem[mid] key)high mid - 1;else low mid 1;}return -1;
} 2.2、折半查找判定树
①结点的值为该记录的关键字值树的叶节点为方形表示查找失败的区间。
②查找成功时的查找长度为从根结点到目的结点的路径上的结点数
③查找失败时的查找长度为从根节点到对应失败节点的父节点的路径上的结点数
④若有序序列有n个元素则对应判定树有n个圆形叶节点和n1个方型的叶节点
⑤若则对于任何一个结点右子树结点数-左子树结点数0或1即右子树结点个数多于或等于左子树结点个数。下取反之
⑥折半查找的判定树是一棵平衡二叉树
⑦元素个数为n时树高为比较次数最多不会超过树高
3、分块查找
又称索引顺序查找块内无序块间有序(第一个块中的最大关键字小于第二个块中的所有记录)
typedef struct {int MaxValue;int low, high;//区间范围
};
顺序查找 长度为n分为b块每块s个记录
若平均查找长度取到最小值
三、树形查找
1、二叉排序树
1.1、目的及定义 ①目的提高查找插入和删除关键字的速度 ②定义左(右)子树上的所有节点均小于(大于)根节点的值 (对二叉排序树进行中序遍历可以得到一个递增的有序序列)
1.2、二叉排序树的查找
//非递归
BiTNode* BTS_Search(BiTree T, int key) {while (T T-data ! key) {if (key T-data)T T-lchild;else T T-rchild;}return T;
}
//递归
BiTNode* BTS_Search(BiTree T, int key) {if (T NULL)return;if (T-data key)return T;else if (T-data key)return BTS_Search(T-lchild, key);else return BTS_Search(T-rchild, key);
}
1.3、二叉排序树的插入
二叉排序树是一种动态树表其特点是树的构造通常不是一次生成的而是在查找过程中当树不存在关键字值等于给定值的结点时再进行插入
int BTS_Insert(BiTree T, int key) {if (T NULL) {T (BiTNode*)malloc(sizeof(BiTNode));T-data key;T-lchild NULL;T-rchild NULL;return 1;}else if (T-data key)return 0;//插入失败else if (T-data key)return BTS_Insert(T-lchild, key);elsereturn BTS_Insert(T-rchild, key);
}
1.4、二叉排序树的构造
void Creat_BST(BiTree T, int str[], int n) {T NULL;int i 0;while (i n) BTS_Insert(T, str[i]);
}
1.5、二叉排序树的删除
删除某结点后该树必须还是一棵二叉排序树
步骤①若被删的结点z是叶节点直接删除 ②若结点z只有一棵左子树或者右子树让z的子树成为z父节点的子树代替z的位置 ③若结点z有两棵子树让z的直接后继(右子树的min右子树左走到头)(或直接前驱(左子树max左子树右走到头))代替z然后从二叉排序树中删除这个直接后继(或直接前驱)从而转化为①②
1.6、查找效率分析
取决于树的高度。若二叉排序树的左右子树的高度只差的绝对值不超过1则。若该树为单支树则ALSO(n)
1.7、二分查找判定树和二叉排序树的区别
①查找过程差不多
②平均时间性能差不多
③唯一性二分判定树唯一但二叉排序树不唯一
④维护表的有序性二叉排序树无需移动结点只需修改指针即可完成插入和删除平均执行时间为二分查找的对象是有序顺序表插入删除平均执行时间为O(n)
⑤若有序表是静态查找表宜用顺序表作为存储结构而采用二分查找实现查找
⑥若有序表是动态查找便采用二叉排序树作为逻辑结构
2、平衡二叉树AVL
2.1、目的及定义 ①目的避免树的高度增长过快降低二叉排序树的性能适用于以查为主很少删/插的场景 ②定义左子树和右子树的高度之差的绝对值不超过1
2.2、平衡二叉树的插入
若插入导致了不平衡则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A再对以A为根的子树调整。
调整方法
①LL(A的L的L插入新结点导致不平衡)右旋一次将A的左孩子B作为根而A成为B的右孩子B原来的右子树作为A的左子树
②RR(A的R的R插入新结点导致不平衡)左旋一次将A的右孩子B作为根而A成为B的左孩子B原来的左子树作为A的右子树
③LR(A的L的R插入新结点导致不平衡)先左旋再右旋。左旋以A的左子树B为根进行一次左旋操作使B的右孩子C提升到B的位置。再进行右旋使C提升到A的位置
④RL(A的R的L插入新结点导致不平衡)先右旋再左旋。右旋以A的右子树B为根进行一次右旋操作使B的左孩子C提升到B的位置。再进行左旋使C提升到A的位置
2.3、平衡二叉树的构造
在构造过程中不断调整使树平衡
2.4、平衡二叉树的删除
先以二叉排序树的方法对结点z删除
步骤①若被删的结点z是叶节点直接删除 ②若结点z只有一棵左子树或者右子树让z的子树成为z父节点的子树代替z的位置 ③若结点z有两棵子树让z的直接后继(右子树的min右子树左走到头)(或直接前驱(左子树max左子树右走到头))代替z然后从二叉排序树中删除这个直接后继(或直接前驱)从而转化为①② ④若导致了不平衡对结点z向上回溯找到第一个不平衡的结点w再进行调整
2.5、平衡二叉树的查找
①与二叉排序树相同进行关键字的比较次数不超过树的高度
②深度为h的平衡二叉树中含有最少结点数其中n00,n11,n22,n34,n47......
③含有n个结点的平衡二叉树的最大高度为因此平均查找效率为
3、红黑树
3.1、目的及定义
①目的为了保持AVL树的平衡性在插入和删除操作后会非常频繁地调整全树整体拓扑结构代价较大为放款条件而引入。适用于频繁删/插操作
②定义一棵红黑树是满足红黑性质的二叉排序树 根节点是黑色的 虚构的外部节点是黑色的(null结点) 不存在两个相邻的红结点 对每个结点从该结点到任意一个外部节点的简单路径上所含黑节点的数量相同 引入n1个外部节点保证每个内部节点子树非空 黑高(bh)从某结点出发(不包含该结点)到达一个外部节点的任意一个简单路上上的黑节点的总数
3.2、结论
①从根到外部节点的最长路径不大于最短路径的2倍
②有n个内部节点的红黑树的高度
③根节点黑高为h的红黑树中内部结点至少有多少个 最少总共h层黑节点的满树
3.3、红黑树的插入
先以二叉排序树的方法对结点z插入然后调整新插入的结点初始为红色
①如果z的父节点是黑色无需调整
②如果z是根节点z为黑色树的黑高增1
③如果z不是根节点且父节点z.p为红色 Ⅰ、z的叔结点y是黑色且z是一个右孩子LR左旋再右旋 或 RL右旋再左旋 Ⅱ、z的叔结点y是黑色且z是一个左孩子LL右旋一次 或 RR左旋一次。以上两者旋转后将z的爷父结点交换颜色 Ⅲ、z的叔结点u是红色父叔都是红色的爷是黑色的。先将父叔染为黑色爷染为红色。然后把爷结点作为z重复循环指针z在树上上移两层。知道满足z为根节点或ⅠⅡ的情况
3.4、红黑树的删除
4、B树和B树
四、散列表
