查找查找定义循序查找二分查找分块查找二叉排序树BST平衡二叉树AVL)红黑树RBT)B树多路平衡查找树B树散列表Hash表查找定义查找表包括关键字和元素。查找表常见操作查找、插入和删除静态和动态。查找长度查找时需要对比关键字的次数对每个关键字的查找长度求平均为平均查找长度ASL。循序查找字面意思从头到尾查找用于线性表。哨兵预留线性表的0位置查找时设置为需要查找的关键字从后往前查找找到时返回对应位置找不到返回0位置。ASL失败 n/2 n/(n1)二分查找排好序的顺序表包含左指针右指针中指针不断判断需查找的关键字位于左区间还是右区间更新左指针或右指针。因为计算m中指针时是向下取整左区间要么比右区间少一个要么相等二分查找的判定树一定是平衡二叉树且满足二叉排序树时间复杂度O(log2n)intlower_binary(vectorinta,intk){intl0,ra.size()-1;intml(r-l)/2;while(lr){if(mk)//查找的在左区间rm-1;else//查找的在右区间lm;intml(r-l)/2;}}分块查找包含索引表和顺序表块内无序块间有序先索引二分查找再块内顺序查找若索引顺序查找块长度都为sASLs22sn/ (2s)当s根号n时ASL最小。顺序分块查找链式分块查找动态查找表二叉排序树BST定义左子树值 根值 右子树值查找从根节点出发需查找的值大于节点值时再比较右子节点否则找左子节点。插入从根节点出发若大于节点值判断右子节点值否则判断左子节点值直到插入到叶子节点删除先找到删除后再衔接前后节点当需删除的节点同时存在左右子树时让最接近它值的直接前驱或者直接后继来代替这个节点。树越矮胖平均查找长度越小TreeNode*creatBST(vectorinta){TreeNode*rootnewTreeNode(a[0]);for(inti1;ia.size();i){TreeNode*noderoot;while(nodenullptr){if(a[i]node-val)nodenode-right;elsenodenode-left;}nodenewTreeNode(a[i]);}returnroot;}平衡二叉树AVL)定义左子树和右子树高度差不超过1且为排序的平衡因子 左子树高度 - 右子树高度从插入点依次往上求平衡因子找首次平衡因子大于1或小于-1的树即为最小不平衡子树对于不平衡二叉树或插入时每次只用调整最小不平衡子树。(1)情况1A-left BR;B-right A;lastNode-right B2情况2平衡二叉树的最少节点数当高度为1时n1 1当高度为2时n2 2当高度为x时nx nx-1 nx-2 1。删除先仿照二叉排序数删除的操作之后调整平衡。红黑树RBT)数为排序的。每个节点为红或黑根节点和外部节点为黑红节点不相邻从根到外节点任意路径黑色数量相等。左根右根叶黑不红红黑路同黑高从某一个节点出发不包含节点本身到外部节点路径上黑节点数量。性质1从根节点到外部节点的最长路径不大于最短路径的2倍2有n个内部节点的红黑树高度h ≤ 2log2n1)3若根节点黑高为h内部节点最少为2h-1满二叉树插入1根为黑2新节点先为红若违反不红红则看父和叔节点3若父和叔节点都为红则父、叔、爷节点变色并判断爷节点是否违法不红红4若叔节点为黑则根据插入的位置按照平衡二叉树插入一样进行左旋或右旋。具体过程可访问https://www.cs.usfca.edu/~galles/visualization/RedBlack.html删除仿照二叉排序树删除节点再调整节点颜色和位置B树多路平衡查找树平衡二叉树的升级版允许多叉如5叉排序树每个节点最多4个关键字5个子节点除根节点外其他节点至少包含[m/2]个子节点如5/2向上取整得3至少有[m/2]-1个关键字如下图n关键字数p0第一指针k1第一关键字任意节点子树的高度都相同绝对平衡叶节点在同一行含n个关键字的m阶B树m叉最小高度logm(n1)最大高度log[m/2](n1)/21n个关键字的B树必有n1个失败节点插入以5叉为例从根节点插入每当节点的关键字数量到5个开始分裂中间的关键字放到父节点中若父节点关键字到5继续分裂删除1终端节点可直接删除其他节点找直接前驱或直接后继代替2若删除后不够[m/2]则找兄弟节点平移一个过来父节点也相应更改若兄弟节点也不够则合并两兄弟节点B树分块查找用B树实现块的最大值作为父节点的关键字关键字全在叶子节点实际信息位于叶子节点的后面B树的实际信息位于每个节点上。MySQL就是用B树索引但是节点的子树个数和关键字个数相等与B树的区间选取不一样如下图散列表Hash表直接根据关键字找到实际信息实现通过一个固定除数对数据取余将数据存放于余数的索引中冲突的同义词依次排在后面装填因子 表中记录数 / 散列表长度拉链法链表数组对数据取余后排在对应链表后面。查找也是取余后遍历。力扣706:设计哈希映射开放定址法取余后发现冲突可以在此基础上加个增量值二次取余增量值选取1线性探测法d 1不断判读冲突位置后的其他位置是否空缺查找时若一次取余找不到则多次取余删除用逻辑删除2平方探测法第一次增量d1 1第二次d2 -1d3 4d4 -4d5 9。表长度必须是4x3的质数则冲突可以遍历满所有空间3伪随机序列法每次增量值为位随机数再散列法多准备几个散列函数多准备几个除数常见散列函数1除留余数法除数选取不大于表长的最大质数如表长15则选取13作为除数2直接定址法如数据是0-100中随机的就设置一个105长度的数组会存在空间浪费。3数字分析法选取数字分布较均匀若干位作为散列地址如手机号选取后四位作为散列地址9999长度的数组4平方取中法取关键字的平方的中间几位作为散列地址取中间三位则需要999长度的链表数组。如身份证hash存储平方后取中间5位。拉链法中冲突的数据链表如果有序排列可以查找的更快。//拉链法实现hashMapclassMyHashMap{public:vectorlistpairint,intdata;inthash;MyHashMap():data(599){//设置除数hash599;}//插入hash表voidput(intkey,intvalue){inthkey%hash;for(autoitdata[h].begin();it!data[h].end();it){if(it-firstkey){it-secondvalue;return;}}data[h].push_back(make_pair(key,value));}//查找intget(intkey){inthkey%hash;for(autoitdata[h].begin();it!data[h].end();it){if(it-firstkey){returnit-second;}}return-1;}//删除voidremove(intkey){inthkey%hash;for(autoitdata[h].begin();it!data[h].end();it){if(it-firstkey){data[h].erase(it);return;}}}}; 数据结构学习笔记8_查找（C++实现）
查找查找定义循序查找二分查找分块查找二叉排序树BST平衡二叉树AVL)红黑树RBT)B树多路平衡查找树B树散列表Hash表查找定义查找表包括关键字和元素。查找表常见操作查找、插入和删除静态和动态。查找长度查找时需要对比关键字的次数对每个关键字的查找长度求平均为平均查找长度ASL。循序查找字面意思从头到尾查找用于线性表。哨兵预留线性表的0位置查找时设置为需要查找的关键字从后往前查找找到时返回对应位置找不到返回0位置。ASL失败 n/2 n/(n1)二分查找排好序的顺序表包含左指针右指针中指针不断判断需查找的关键字位于左区间还是右区间更新左指针或右指针。因为计算m中指针时是向下取整左区间要么比右区间少一个要么相等二分查找的判定树一定是平衡二叉树且满足二叉排序树时间复杂度O(log2n)intlower_binary(vectorinta,intk){intl0,ra.size()-1;intml(r-l)/2;while(lr){if(mk)//查找的在左区间rm-1;else//查找的在右区间lm;intml(r-l)/2;}}分块查找包含索引表和顺序表块内无序块间有序先索引二分查找再块内顺序查找若索引顺序查找块长度都为sASLs22sn/ (2s)当s根号n时ASL最小。顺序分块查找链式分块查找动态查找表二叉排序树BST定义左子树值 根值 右子树值查找从根节点出发需查找的值大于节点值时再比较右子节点否则找左子节点。插入从根节点出发若大于节点值判断右子节点值否则判断左子节点值直到插入到叶子节点删除先找到删除后再衔接前后节点当需删除的节点同时存在左右子树时让最接近它值的直接前驱或者直接后继来代替这个节点。树越矮胖平均查找长度越小TreeNode*creatBST(vectorinta){TreeNode*rootnewTreeNode(a[0]);for(inti1;ia.size();i){TreeNode*noderoot;while(nodenullptr){if(a[i]node-val)nodenode-right;elsenodenode-left;}nodenewTreeNode(a[i]);}returnroot;}平衡二叉树AVL)定义左子树和右子树高度差不超过1且为排序的平衡因子 左子树高度 - 右子树高度从插入点依次往上求平衡因子找首次平衡因子大于1或小于-1的树即为最小不平衡子树对于不平衡二叉树或插入时每次只用调整最小不平衡子树。(1)情况1A-left BR;B-right A;lastNode-right B2情况2平衡二叉树的最少节点数当高度为1时n1 1当高度为2时n2 2当高度为x时nx nx-1 nx-2 1。删除先仿照二叉排序数删除的操作之后调整平衡。红黑树RBT)数为排序的。每个节点为红或黑根节点和外部节点为黑红节点不相邻从根到外节点任意路径黑色数量相等。左根右根叶黑不红红黑路同黑高从某一个节点出发不包含节点本身到外部节点路径上黑节点数量。性质1从根节点到外部节点的最长路径不大于最短路径的2倍2有n个内部节点的红黑树高度h ≤ 2log2n1)3若根节点黑高为h内部节点最少为2h-1满二叉树插入1根为黑2新节点先为红若违反不红红则看父和叔节点3若父和叔节点都为红则父、叔、爷节点变色并判断爷节点是否违法不红红4若叔节点为黑则根据插入的位置按照平衡二叉树插入一样进行左旋或右旋。具体过程可访问https://www.cs.usfca.edu/~galles/visualization/RedBlack.html删除仿照二叉排序树删除节点再调整节点颜色和位置B树多路平衡查找树平衡二叉树的升级版允许多叉如5叉排序树每个节点最多4个关键字5个子节点除根节点外其他节点至少包含[m/2]个子节点如5/2向上取整得3至少有[m/2]-1个关键字如下图n关键字数p0第一指针k1第一关键字任意节点子树的高度都相同绝对平衡叶节点在同一行含n个关键字的m阶B树m叉最小高度logm(n1)最大高度log[m/2](n1)/21n个关键字的B树必有n1个失败节点插入以5叉为例从根节点插入每当节点的关键字数量到5个开始分裂中间的关键字放到父节点中若父节点关键字到5继续分裂删除1终端节点可直接删除其他节点找直接前驱或直接后继代替2若删除后不够[m/2]则找兄弟节点平移一个过来父节点也相应更改若兄弟节点也不够则合并两兄弟节点B树分块查找用B树实现块的最大值作为父节点的关键字关键字全在叶子节点实际信息位于叶子节点的后面B树的实际信息位于每个节点上。MySQL就是用B树索引但是节点的子树个数和关键字个数相等与B树的区间选取不一样如下图散列表Hash表直接根据关键字找到实际信息实现通过一个固定除数对数据取余将数据存放于余数的索引中冲突的同义词依次排在后面装填因子 表中记录数 / 散列表长度拉链法链表数组对数据取余后排在对应链表后面。查找也是取余后遍历。力扣706:设计哈希映射开放定址法取余后发现冲突可以在此基础上加个增量值二次取余增量值选取1线性探测法d 1不断判读冲突位置后的其他位置是否空缺查找时若一次取余找不到则多次取余删除用逻辑删除2平方探测法第一次增量d1 1第二次d2 -1d3 4d4 -4d5 9。表长度必须是4x3的质数则冲突可以遍历满所有空间3伪随机序列法每次增量值为位随机数再散列法多准备几个散列函数多准备几个除数常见散列函数1除留余数法除数选取不大于表长的最大质数如表长15则选取13作为除数2直接定址法如数据是0-100中随机的就设置一个105长度的数组会存在空间浪费。3数字分析法选取数字分布较均匀若干位作为散列地址如手机号选取后四位作为散列地址9999长度的数组4平方取中法取关键字的平方的中间几位作为散列地址取中间三位则需要999长度的链表数组。如身份证hash存储平方后取中间5位。拉链法中冲突的数据链表如果有序排列可以查找的更快。//拉链法实现hashMapclassMyHashMap{public:vectorlistpairint,intdata;inthash;MyHashMap():data(599){//设置除数hash599;}//插入hash表voidput(intkey,intvalue){inthkey%hash;for(autoitdata[h].begin();it!data[h].end();it){if(it-firstkey){it-secondvalue;return;}}data[h].push_back(make_pair(key,value));}//查找intget(intkey){inthkey%hash;for(autoitdata[h].begin();it!data[h].end();it){if(it-firstkey){returnit-second;}}return-1;}//删除voidremove(intkey){inthkey%hash;for(autoitdata[h].begin();it!data[h].end();it){if(it-firstkey){data[h].erase(it);return;}}}};