口碑好的定制网站建设提供商,免费足网站,网站建设必须配置,河南专业网站建设公司推荐#xff08;1#xff09; 红黑树的了解#xff08;平衡树#xff0c;二叉搜索树#xff09;#xff0c;使用 场景 把数据结构上几种树集中的讨论一下#xff1a; 1.AVLtree 定义#xff1a;最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一… 1 红黑树的了解平衡树二叉搜索树使用 场景 把数据结构上几种树集中的讨论一下 1.AVLtree 定义最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是Olog n。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 节点的平衡因子是它的左子树的高度减去它的右子树的高度有时相反。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的并需要重新平衡这个树。平衡因子可以直接存储在每个节点中或从可能存储在节点中的子树高度计算出来。 一般我们所看见的都是排序平衡二叉树。 AVLtree使用场景AVL树适合用于插入删除次数比较少但查找多的情况。插入删除导致很多的旋转旋转是非常耗时的。AVL 在linux内核的vm area中使用。 2.二叉搜索树 二叉搜索树也是一种树适用与一般二叉树的全部操作但二叉搜索树能够实现数据的快速查找。 二叉搜索树满足的条件 1.非空左子树的所有键值小于其根节点的键值 2.非空右子树的所有键值大于其根节点的键值 3.左右子树都是二叉搜索树 二叉搜索树的应用场景如果是没有退化称为链表的二叉树查找效率就是lgn效率不错但是一旦退换称为链表了要么使用平衡二叉树或者之后的RB树因为链表就是线性的查找效率。 3.红黑树的定义 红黑树是一种二叉查找树但在每个结点上增加了一个存储位表示结点的颜色可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是接近平衡的。当二叉查找树的高度较低时这些操作执行的比较快但是当树的高度较高时这些操作的性能可能不比用链表好。红黑树red-black tree是一种平衡的二叉查找树它能保证在最坏情况下基本的动态操作集合运行时间为O(lgn)。 红黑树必须要满足的五条性质 性质一节点是红色或者是黑色 在树里面的节点不是红色的就是黑色的没有其他颜色要不怎么叫红黑树呢是吧。 性质二根节点是黑色 根节点总是黑色的。它不能为红。 性质三每个叶节点NIL或空节点是黑色性质四每个红色节点的两个子节点都是黑色的也就是说不存在两个连续的红色节点 就是连续的两个节点不能是连续的红色连续的两个节点的意思就是父节点与子节点不能是连续的红色。 性质五从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。从根节点到每一个NIL节点的路径中都包含了相同数量的黑色节点。 红黑树的应用场景红黑树是一种不是非常严格的平衡二叉树没有AVLtree那么严格的平衡要求所以它的平均查找增添删除效率都还不错。广泛用在C的STL中。如map和set都是用红黑树实现的。 4.B树定义 B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树查找路径不只两个不属于二叉搜索树的范畴因为它不止两路存在多路。 B树满足的条件 1树种的每个节点最多拥有m个子节点且m2,空树除外注m阶代表一个树节点最多有多少个查找路径m阶m路,当m2则是2叉树,m3则是3叉2除根节点外每个节点的关键字数量大于等于ceil(m/2)-1个小于等于m-1个非根节点关键字数必须2;注ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)3所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子4如果一个非叶节点有N个子节点则该节点的关键字数等于N-1;5所有节点关键字是按递增次序排列并遵循左小右大原则 B树的应用场景构造一个多阶的B类树然后在尽量多的在结点上存储相关的信息保证层数尽量的少以便后面我们可以更快的找到信息磁盘的I/O操作也少一些而且B类树是平衡树每个结点到叶子结点的高度都是相同这也保证了每个查询是稳定的。 5.B树 B树是B树的一个升级版B树是B树的变种树有n棵子树的节点中含有n个关键字每个关键字不保存数据只用来索引数据都保存在叶子节点。是为文件系统而生的。 相对于B树来说B树更充分的利用了节点的空间让查询速度更加稳定其速度完全接近于二分法查找。为什么说B树查找的效率要比B树更高、更稳定我们先看看两者的区别 1B跟B树不同B树的非叶子节点不保存关键字记录的指针这样使得B树每个节点所能保存的关键字大大增加2B树叶子节点保存了父节点的所有关键字和关键字记录的指针每个叶子节点的关键字从小到大链接 3B树的根节点关键字数量和其子节点个数相等;4B的非叶子节点只进行数据索引不会存实际的关键字记录的指针所有数据地址必须要到叶子节点才能获取到所以每次数据查询的次数都一样 特点在B树的基础上每个节点存储的关键字数更多树的层级更少所以查询数据更快所有指关键字指针都存在叶子节点所以每次查找的次数都相同所以查询速度更稳定;应用场景 用在磁盘文件组织 数据索引和数据库索引。 6.Trie树字典树 trie又称前缀树是一种有序树用于保存关联数组其中的键通常是字符串。与二叉查找树不同键不是直接保存在节点中而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀也就是这个节点对应的字符串而根节点对应空字符串。一般情况下不是所有的节点都有对应的值只有叶子节点和部分内部节点所对应的键才有相关的值。 在图示中键标注在节点中值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机尽管边上的符号一般是隐含在分支的顺序中的。 键不需要被显式地保存在节点中。图示中标注出完整的单词只是为了演示 trie 的原理。 trie树的优点利用字符串的公共前缀来节约存储空间最大限度地减少无谓的字符串比较查询效率比哈希表高。缺点Trie树是一种比较简单的数据结构.理解起来比较简单,正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗非常大. 其基本性质可以归纳为 1. 根节点不包含字符除根节点外每一个节点都只包含一个字符。 2. 从根节点到某一节点路径上经过的字符连接起来为该节点对应的字符串。3. 每个节点的所有子节点包含的字符都不相同。 典型应用是用于统计排序和保存大量的字符串但不仅限于字符串所以经常被搜索引擎系统用于文本词频统计。字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。 2 红黑树在STL上的应用 STL中set、multiset、map、multimap底层是红黑树实现的而unordered_map、unordered_set 底层是哈希表实现的。 multiset、multimap 插入相同的key的时候我们将后插入的key放在相等的key的右边之后不管怎么进行插入或删除操作后加入的key始终被认为比之前的大。 3 了解并查集吗低频 什么是合并查找问题呢 顾名思义就是既有合并又有查找操作的问题。举个例子有一群人他们之间有若干好友关系。如果两个人有直接或者间接好友关系那么我们就说他们在同一个朋友圈中这里解释下如果Alice是Bob好友的好友或者好友的好友的好友等等即通过若干好友可以认识那么我们说Alice和Bob是间接好友。随着时间的变化这群人中有可能会有新的朋友关系这时候我们会对当中某些人是否在同一朋友圈进行询问。这就是一个典型的合并查找操作问题既包含了合并操作又包含了查找操作。 并查集在一些有N个元素的集合应用问题中我们通常是在开始时让每个元素构成一个单元素的集合然后按一定顺序将属于同一组的元素所在的集合合并其间要反复查找一个元素在哪个集合中。 并查集是一种树型的数据结构用于处理一些不相交集合Disjoint Sets的合并及查询问题。 并查集也是使用树形结构实现。不过不是二叉树。每个元素对应一个节点每个组对应一棵树。在并查集中哪个节点是哪个节点的父亲以及树的形状等信息无需多加关注整体组成一个树形结构才是重要的。类似森林 4 贪心算法和动态规划的区别 贪心算法局部最优划分的每个子问题都最优得到全局最优但是不能保证是全局最优解所以对于贪心算法来说解是从上到下的一步一步最优直到最后。 动态规划将问题分解成重复的子问题每次都寻找左右子问题解中最优的解一步步得到全局的最优解.重复的子问题可以通过记录的方式避免多次计算。所以对于动态规划来说解是从小到上从底层所有可能性中找到最优解再一步步向上。 分治法和动态规划类似将大问题分解成小问题但是这些小问题是独立的没有重复的问题。独立问题取得解再合并成大问题的解。 例子比如钱币分为1元3元4元要拿6元钱贪心的话先拿4再拿两个1一共3张钱实际最优却是两张3元就够了。 5 判断一个链表是否有环如何找到这个环的起 点 给定一个单链表只给出头指针h 1、如何判断是否存在环 2、如何知道环的长度 3、如何找出环的连接点在哪里 4、带环链表的长度是多少 解法1、对于问题1使用追赶的方法设定两个指针slow、fast从头指针开始每次分别前进1步、2步。如存在环则两者相遇如不存在环fast遇到NULL退出。 2、对于问题2记录下问题1的碰撞点pslow、fast从该点开始再次碰撞所走过的操作数就是环的长度s。 3、问题3有定理碰撞点p到连接点的距离头指针到连接点的距离因此分别从碰撞点、头指针开始走相遇的那个点就是连接点。(证明在后面附注) 4、问题3中已经求出连接点距离头指针的长度加上问题2中求出的环的长度二者之和就是带环单链表的长度新浪博客 6 实现一个strcpy函数或者memcpy如果 内存可能重叠呢 ——大家一般认为名不见经传strcpy函数实现不是很难流行的strcpy函数写法是 1 2 3 4 5 6 7 8 9 1. char *my_strcpy(char *dst,const char *src) 2. { 3. assert(dst ! NULL); 4. assert(src ! NULL); 5. char *ret dst; 6. while((* dst * src) ! \0) 7. ; 8. return ret; 9. } 如果注意到 1检查指针有效性 2返回目的指针des 3源字符串的末尾 ‘\0’ 需要拷贝。 内存重叠 内存重叠拷贝的目的地址在源地址范围内。所谓内存重叠就是拷贝的目的地址和源地址有重叠。 在函数strcpy和函数memcpy都没有对内存重叠做处理的使用这两个函数的时候只有程序员自己保证源地址和目标地址不重叠或者使用memmove函数进行内存拷贝。 memmove函数对内存重叠做了处理。 strcpy的正确实现应为 1 2 3 4 5 6 7 8 1. char *my_strcpy(char *dst,const char *src) 2. { 3. assert(dst ! NULL); 4. assert(src ! NULL); 5. char *ret dst; 6. memmove(dst,src,strlen(src)1); 7. return ret; 8. } memmove函数实现时考虑到了内存重叠的情况可以完成指定大小的内存拷贝 7 快排存在的问题如何优化 快排的时间复杂度 时间复杂度最快平均是Onlogn,最慢的时候是O(n2);辅助空间也是O(logn)最开始学快排时最疑惑的就是这个东西不知道怎么得来的一种是通过数学运算可以的出来还有一种是通过递归树来理解就容易多了 这张图片别人博客那里弄过来的所谓时间复杂度最理想的就是取到中位数情况那么递归树就是一个完全二叉树那么树的深度也就是最低为Logn这个时候每一次又需要n次比较所以时间复杂度nlogn当快排为顺序或者逆序时这个数为一个斜二叉树深度为n同样每次需要n次比较那那么最坏需要n2的时间 优化 1.当整个序列有序时退出算法2.当序列长度很小时根据经验是大概小于 8应该使用常数更小的算法比如插入排序等 3.随机选取分割位置4.当分割位置不理想时考虑是否重新选取分割位置5.分割成两个序列时只对其中一个递归进去另一个序列仍可以在这一函数内继续划分可以显著减小栈的大小尾递归6.将单向扫描改成双向扫描可以减少划分过程中的交换次数优化1当待排序序列的长度分割到一定大小后使用插入排序原因对于很小和部分有序的数组快排不如插排好。当待排序序列的长度分割到一定大小后继续分割的效率比插入排序要差此时可以使用插排而不是快排优化2在一次分割结束后可以把与Key相等的元素聚在一起继续下次分割时不用再对与key相等元素分割 优化3优化递归操作快排函数在函数尾部有两次递归操作我们可以对其使用尾递归优化优点如果待排序的序列划分极端不平衡递归的深度将趋近于n而栈的大小是很有限的每次递归调用都会耗费一定的栈空间函数的参数越多每次递归耗费的空间也越多。优化后可以缩减堆栈深度由原来的O(n)缩减为O(logn)将会提高性能。 8 Top K问题可以采取的方法有哪些各自优 点 1.将输入内容假设用数组存放进行完全排序从中选出排在前K的元素即为所求。有了这个思路我们可以选择相应的排序算法进行处理目前来看快速排序堆排序和归并排序都能达到O(nlogn)的时间复杂度。 2.对输入内容进行部分排序即只对前K大的元素进行排序这K个元素即为所求。此时我们可以选择冒泡排序或选择排序进行处理即每次冒泡选择都能找到所求的一个元素。这类策略的时间复杂度是O(Kn)。 3.对输入内容不进行排序显而易见这种策略将会有更好的性能开销。我们此时可以选择两种策略进行处理用一个桶来装前k个数桶里面可以按照最小堆来维护a)利用最小堆维护一个大小为K的数组目前该小根堆中的元素是排名前K的数其中根是最小的数。此后每次从原数组中取一个元素与根进行比较如大于根的元素则将根元素替换并进行堆调整下沉即保证小根堆中的元素仍然是排名前K的数且根元素仍然最小否则不予处理取下一个数组元素继续该过程。该算法的时间复杂度是O(nlogK)一般来说企业中都采用该策略处理top-K问题因为该算法不需要一次将原数组中的内容全部加载到内存中而这正是海量数据处理必然会面临的一个关卡。 b)利用快速排序的分划函数找到分划位置K则其前面的内容即为所求。该算法是一种非常有效的处理方式时间复杂度是O(n)证明可以参考算法导论书籍。对于能一次加载到内存中的数组该策略非常优秀。 9 Bitmap的使用存储和插入方法 BitMap从字面的意思 很多人认为是位图其实准确的来说翻译成基于位的映射。 在所有具有性能优化的数据结构中大家使用最多的就是hash表是的在具有定位查找上具有O(1)的常量时间多么的简洁优美。但是数据量大了内存就不够了。 当然也可以使用类似外排序来解决问题的由于要走IO所以时间上又不行。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value 而Key即是该元素。由于采用了Bit为单位来存储数据因此在存储空间方面可以大大节省。其实如果你知道计数排序的话算法导论中有一节讲过你就会发现这个和计数排序很像。 bitmap应用 1 2 1可进行数据的快速查找判重删除一般来说数据范围是int的10倍以下。 2去重数据而达到压缩数据 还可以用于爬虫系统中url去重、解决全组合问题。 BitMap应用排序示例假设我们要对0-7内的5个元素(4,7,2,5,3)排序这里假设这些元素没有重复。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数我们就只需要8个Bit1Bytes首先我们开辟1Byte的空间将这些空间的所有Bit位都置为0(如下图) 然后遍历这5个元素首先第一个元素是4那么就把4对应的位置为1可以这样操作 p(i/8)|(0×01(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况这里默认为Big-ending。不过计算机一般是小端存储的如intel。小端的话就是将倒数第5位置1,因为是从零开始的所以要把第五位置为一如下图 然后再处理第二个元素7将第八位置为1,接着再处理第三个元素一直到最后处理完所有的元素将相应的位置为1这时候的内存的Bit位的状态如下 然后我们现在遍历一遍Bit区域将该位是一的位的编号输出23457这样就达到了排序的目的。 bitmap排序复杂度分析 Bitmap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。 bitmap排序的时间复杂度不是O(N)的而是取决于待排序数组中的最大值MAX在实际应用上关系也不大比如我开10个线程去读byte数组那么复杂度为:O(Max/10)。也就是要是读取的可以用多线程的方式去读取。时间复杂度方面也是O(Max/n)其中Max为byte[]数组的大小n为线程大小。 空间复杂度应该就是O(Max/8)bytes吧 BitMap算法流程 假设需要排序或者查找的最大数MAX10000000lz:这里MAX应该是最大的数而不是int数据的总数那么我们需要申请内存空间的大小为int a[1 MAX/32]。 其中a[0]在内存中占32为可以对应十进制数0-31依次类推bitmap表为 a[0]---------0-31 a[1]---------32-63 a[2]---------64-95 a[3]---------96-127 … 我们要把一个整数N映射到Bit-Map中去首先要确定把这个N Mapping到哪一个数组元素中去即确定映射元素的index。我们用int类型的数组作为map的元素这样我们就知道了一个元素能够表示的数字个数(这里是32)。于是N/32就可以知道我们需要映射的key了。所以余下来的那个N%32就是要映射到的位数。 1.求十进制数对应在数组a中的下标 先由十进制数n转换为与32的余可转化为对应在数组a中的下标。 如十进制数0-31都应该对应在a[0]中比如n24,那么 n/320则24对应在数组a中的下标为0。又比如n60,那么n/321则60对应在数组a中的下标为 1同理可以计算0-N在数组a中的下标。 i NK % 结果就是N/(2^K) Note: map的范围是[0, 原数组最大的数对应的2的整次方数-1]。 2.求十进制数对应数组元素a[i]在0-31中的位m 十进制数0-31就对应0-31而32-63则对应也是0-31即给定一个数n可以通过模32求得对应0-31中的数。 m n ((1 K) - 1) %结果就是n%(2^K) 3.利用移位0-31使得对应第m个bit位为1 如a[i]的第m位置1a[i] a[i] | (1如将当前4对应的bit位置1的话只需要1左移4位与B[0] | 即可。 Note: 1 p(i/8)|(0×01(i%8))这样也可以 2 同理将int型变量a的第k位清0即aa~(1 BitMap算法评价 优点 1. 运算效率高不进行比较和移位2. 占用内存少比如最大的数MAX10000000只需占用内存为MAX/81250000Byte1.25M。 3. 缺点1. 所有的数据不能重复即不可对重复的数据进行排序。少量重复数据查找还是可以的用2-bitmap。 2. 当数据类似1100010万只有3个数据的时候用bitmap时间复杂度和空间复杂度相当大只有当数据比较密集时才有优势。 10 字典树的理解以及在统计上的应用 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点. 就是在海量数据中找出某一个数比如2亿QQ号中查找出某一个特定的QQ号。。 11 N个骰子出现和为m的概率 典型的可以用动态规划的思想来完成1.现在变量有骰子个数点数和。当有k个骰子点数和为n时出现次数记为f(k,n)。那与k-1个骰子阶段之间的关系是怎样的 2.当我有k-1个骰子时再增加一个骰子这个骰子的点数只可能为1、2、3、4、5或6。那k个骰子得到点数和为n的情况有 (k-1,n-1)第k个骰子投了点数1 (k-1,n-2)第k个骰子投了点数2 (k-1,n-3)第k个骰子投了点数3 … (k-1,n-6)第k个骰子投了点数6在k-1个骰子的基础上再增加一个骰子出现点数和为n的结果只有这6种情况所以f(k,n)f(k-1,n-1)f(k-1,n-2)f(k-1,n-3)f(k-1,n-4)f(k-1,n-5)f(k-1,n-6) 3.有1个骰子f(1,1)f(1,2)f(1,3)f(1,4)f(1,5)f(1,6)1。 用递归就可以解决这个问题 用迭代来完成 19 海量数据问题可参考左神的书
目前关于海量数据想到的解决办法
1.bitmap 2.桶排序外部排序将需要排序的放到外存上不用全部放到内存上
20 一致性哈希
说明
优点
1.当后端是缓存服务器时经常使用一致性哈希算法来进行负载均衡。使用一致性哈希的好处在于增减集群的缓存服务器时只有少量的缓存会失效回源量较小。
2.尽量减少数据丢失问题减少移动数据的风险
