b树算法导论

㈠ B树算法难么

感觉挺难。

B树的定义
假设B树的度为t（t>=2），则B树满足如下要求：（参考算法导论）
（1） 每个非根节点至少包含t-1个关键字，t个指向子节点的指针；至多包含2t-1个关键字，2t个指向子女的指针（叶子节点的子女为空）。
（2） 节点的所有key按非降序存放，假设节点的关键字分别为K[1], K[2] … K[n], 指向子女的指针分别为P[1], P[2]…P[n+1]，其中n为节点关键字的个数。则有：
P[1] <= K[1] <= P[2] <= K[2] …..<= K[n] <=P[n+1] // 这里P[n]也指其指向的关键字
（3） 若根节点非空，则根节点至少包含两个子女；
（4） 所有的叶子节点都在同一层。
B树的搜索，search（root, target）
从root出发，对每个节点，找到大于或等于target关键字中最小的K[i]，如果K[i]与target相等，则查找成功；否则在P[i]中递归搜索target，直到到达叶子节点，如仍未找到则说明关键字不在B树中，查找失败。
B树的插入，insert(root,target)
B树的插入需要沿着搜索的路径从root一直到叶节点，根据B树的规则，每个节点的关键字个数在[t-1, 2t-1]之间，故当target要加入到某个叶子时，如果该叶子节点已经有2t-1个关键字，则再加入target就违反了B树的定义，这时就需要对该叶子节点进行分裂，将叶子以中间节点为界，分成两个包含t-1个关键字的子节点，同时把中间节点提升到该叶子的父节点中，如果这样使得父节点的关键字个数超过2t-1，则要继续向上分裂，直到根节点，根节点的分裂会使得树加高一层。
上面的过程需要回溯，那么能否从根下降到叶节点后不回溯就能完成节点的插入呢？答案是肯定的，核心思想就是未雨绸缪，在下降的过程中，一旦遇到已满的节点（关键字个数为2t-1），就就对该节点进行分裂，这样就保证在叶子节点需要分裂时，其父节点一定是非满的，从而不需要再向上回溯。
B树的删除，delete(root,target)
在删除B树节点时，为了避免回溯，当遇到需要合并的节点时就立即执行合并，B树的删除算法如下：从root向叶子节点按照search规律遍历：
（1） 如果target在叶节点x中，则直接从x中删除target，情况（2）和（3）会保证当再叶子节点找到target时，肯定能借节点或合并成功而不会引起父节点的关键字个数少于t-1。
（2） 如果target在分支节点x中：
（a） 如果x的左分支节点y至少包含t个关键字，则找出y的最右的关键字prev，并替换target，并在y中递归删除prev。
（b） 如果x的右分支节点z至少包含t个关键字，则找出z的最左的关键字next，并替换target，并在z中递归删除next。
（c） 否则，如果y和z都只有t-1个关键字，则将targe与z合并到y中，使得y有2t-1个关键字，再从y中递归删除target。
（3） 如果关键字不在分支节点x中，则必然在x的某个分支节点p[i]中，如果p[i]节点只有t-1个关键字。
（a） 如果p[i-1]拥有至少t个关键字，则将x的某个关键字降至p[i]中，将p[i-1]的最大节点上升至x中。
（b） 如果p[i+1]拥有至少t个关键字，则将x个某个关键字降至p[i]中，将p[i+1]的最小关键字上升至x个。
（c） 如果p[i-1]与p[i+1]都拥有t-1个关键字，则将p[i]与其中一个兄弟合并，将x的一个关键字降至合并的节点中，成为中间关键字。

㈡ 关于算法导论

概念：

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。

背景和术语：
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。所有数据块都存储在节点中。这些节点中的某一个节点总是担当启始位置的功能，它不是任何节点的儿子；我们称之为根节点或根。它有最多两个"儿子"，都是它连接到的其他节点。所有这些儿子都可以有自己的儿子，以此类推。这样根节点就有了把它连接到在树中任何其他节点的路径。

如果一个节点没有儿子，我们称之为叶子节点，因为在直觉上它是在树的边缘上。子树是从特定节点可以延伸到的树的某一部分，其自身被当作一个树。在红黑树中，叶子被假定为 null 或空。

由于红黑树也是二叉查找树，它们当中每一个节点都的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。
用途和好处：
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(real time application)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突变之后它们能保持为以前的版本。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。

红黑树是 2-3-4树的一种等同。换句话说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因，尽管 2-3-4 树在实践中不经常使用。
属性：
红黑树是每个节点都有颜色特性的二叉查找树，颜色的值是红色或黑色之一。除了二叉查找树带有的一般要求，我们对任何有效的红黑树加以如下增补要求:

1.节点是红色或黑色。

2.根是黑色。

3.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

4.从每个叶子到根的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键属性: 从根到叶子的最长的可能路径不大于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值都要求与树的高度成比例的最坏情况时间，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

在很多树数据结构的表示中，一个节点有可能只有一个儿子，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用 "null 叶子" 或"空(null)叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个儿子，尽管其中的一个或两个可能是空叶子。

操作：
在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为 O(log n) 次，但是它导致了非常复杂的操作。

㈢ 如何准备互联网公司面试（算法相关）

书籍： 《算法导论》 这本是大部头，很多人都看不完。我本人也并没有看完，它跟了我这么多年，完全是属于常看常新的牛书。每一次看，都发现会有新的收获。比如，以前并不知道求K位数或者中位数有平均为O(n)复杂度的算法。看到了别的地方的参考资料，才知道，原来《算导》上专门有一小节讲这个内容。我基本上是本科比较集中的看了一遍，研一的时候又集中的看了一遍，才算是粗略的看完。但是其实，很多理论性的，以及图论一部分依然还是没有看完。个人推荐，先从简单的开始，挑选比较熟悉的一些偏重与数据结构方面的知识作为起点。这本书的习题非常重要，要是有时间，能够全部做完，那绝对是能够神功在手了。其实，集中把，第二部分（排序），第三部分（数据结构），第四部分（高级设计，我基本主要看动态规划和贪心），第五部分（高级数据结构，B树和二项堆，并差集），第六部分（图算法，最大流部分较难，自己可以看情况掌握）。这些部分可以先从算法本身开始，伪代码全部看懂。因为算法导论讲的很详细，而且有来龙去脉，基本不会有太大难度。数学证明，推荐大家掌握，但是，突击或者第一次，可以选择性的看看。我自己是重复看，才把证明看掉的。第一次看的时候，基本都跳过了。不过，证明和习题是精髓！希望如果有时间，一定要补回来。 《编程之美》《挑战编程》 这本书绝对是将全中国企业，或者说是一部分懒惰的企业面试题库提升了一个档次的一本神书。网络面我师兄的时候，我师兄直接把有一道题的最优解答出来了。但是，那个面试官显然是不知道最优解，一直在引导我师兄答出，这本书里面的第四个解。呵呵。书很不错。全部看一遍并不难。说个不好听的，可以背下来，而且相信我，基本上绝对有用！比如说，n!后面有多少个0。我相信，你们今年面试或者笔试，一定会碰到这道题。《挑战编程》大家可以自行考虑一下吧，这个完全是针对acm竞赛的，不过，看看题也不错。 《编程珠玑》 业界神书嘛。习题全部做完就是了。其实都是些小东西，但是，基本上一步步考察你的解决问题的能力。个人觉得，最常用的就是bit map做排序或者去重，拓展一下就是bloom filter，我当时都是在这本书里面看到的。 《算法技术手册》 这本书貌似出镜不多。书很薄，代码写的非常好，其实基本上全部都是基础算法和数据结构的实现。但是，它牛逼就在于，代码写的太好了，基本上，看一遍，绝对能背下来。面试基础很重要。基本上每个笔试或者面试，都会考一个100行以内的小程序。比如，给定一棵树，以及其中一个节点x，要求出这棵树的中序遍历序列中，x的后续节点，非递归实现。这种题非常简单，但是，真正写对的，其实并不多。《STL源码剖析》《C标准库》 都不厚。挑着看一遍非常舒服。特别是，看看STL每个数据结构迭代器类型啊，红黑书如何实现啊。C标准库，最常见的，比如strcpy()和memcpy()有什么区别啊。特别是，STL，看过之后，对泛型还是能有一定了解的。《C专家编程》《Effective c++》《深度探索C++对象模型》 第一本比较简单，可以当八卦书看。后两本其实也没啥好说的，其实都是些业界公认的牛书。我再重复一遍也没什么意义。但是，的确，考察基本上也就都是这么几本书上面的东西。基本上后两本主要侧重看c++对象方面的一些指示，特别是多态相关的。 《具体数学》《组合数学》 这两本其实可以看作修身养性的书。我当时是时间比较充裕的时候看完的。纯突击，大家就可以跳过了。但是，看完真的很有用。比如说，你们就可以跟面试官扯约瑟夫环的构造解了（这道题我觉得80%会遇到），直接推推公式，就不用写模拟代码了。《组合数学》也是，很多笔试一般会有些小智力题。不过，其实一般的题目，不看这本书也可以搞定。所以，这两本仅供参考。大家有兴趣的时候，可以翻翻。《Linux内核源码剖析》《Linux环境高级编程》…… 要是有机会，能看看最好。因为很多公司都会考察Linux相关的知识。最少要会点脚本，一些简单的Linux命令，以及正则表达式什么的。要是能聊聊内核源码或者驱动开发什么的东西，面试官肯定更加喜欢了。 知识： c & c++ 首先要知道c和c++的区别。常考的有const的用法，一些生僻关键字比如extern，static的用法。 结构体与类的差别。类里面的字对齐问题，也就是说一个类到底有多大。以及一个空的类有多大。 虚函数以及多态相关的显然是重点。比如析构函数什么时候需要写成虚函数，构造函数是否可以是虚函数。 int a[10]; a 和 &a的区别。 java java我并不熟。但是基本上肯定会考一些虚拟机相关的，以及GC等知识。然后，一般招聘的java程序员都会问到很多多线程编程的东西，以及hadoop！这个绝对是重点，淘宝绝对就是问这个的。 操作系统 这个看工作岗位的实际要求。基本的进程线程区别==肯定是会问到的。要是要求高一些，就会问很多多线程编程的问题。一些竞争死锁等基础知识，一些进程调度的算法，最近的kernel好像用的是CFS调度算法。shell编程，如何读取程序堆栈，写一些core mp的读取程序等等的。 数据结构 基本上所有的排序都要会写。与树有关的操作都要会些非递归版本。图一般考的不多。Flood-Fill算法等等。查找中位数。B树和红黑书最好要掌握，不用会写，能扯扯基本就行。KMP，这个很有可能考！而且的确真的不好懂。要是实在不行，背下来吧。哈哈。 网络 这个其实比较基础了。我个人网络方面的知识并不好。但是各种协议的基础，几次握手啊，一些操作系统的api实现到底是单工还是双工用的是TCP还是UDP。我个人网络纯粹靠拼RP。 数据库 数据库非常重要。基本的SQL肯定是要会的。最常见有一道题，inner join和out join的区别。MySQL是重点，基本上很多企业都是问这个。然后，网络扯多了会跟你扯MySQL引擎 的一些东西。这些我就不太懂了。要是能准备的话，或者说的确是做这方面的，就可以着重多准备下。 大规模数据处理这一块绝对是重点！而且本身不是一个系统的学科分支。但是，基本上几家大公司都会问这方面的。推荐先读读google那几篇论文。Page Rank那一篇，然后Map Rece好像有几篇吧。Big Table什么的。推荐一个网址。这篇貌似是转载的，我以前找到的源地址现在找不到了。处理这一类问题基本上思路都是，哈希，map rece以及bit map等等的。对了，推荐看一下外排序以及相关的败者树。这些都是大规模数据处理的一些典型问题。掌握了这些其实也就够了。这块有点屠龙之技的感觉，特别是对于学生，基本没有谁能有机会把这些代码实现出来。但是，没办法，这些公司就是喜欢考。看完那篇博客的，然后再自行查找一些资料，基本就够了。万变不离其中，而且，这些东西，没办法考那么难的。 推荐一个博客吧，作者收集了100+道面试题，并且全部给出了代码。把这个全部看完，基本上很多面试笔试，都是这些原题。 推荐Top Language里面的今天我们思考系列，好几年前的了。看大牛的思考过程，非常有帮助。希望自己能多想想再看答案。注意，google group好像有时被墙。 我把发芽网的题库版块也扫了一遍。 还有好多一时想不起来了。

㈣ 算法导论 习题

将集合排序，复杂度O(nlogn)。
从小到大遍历整个数组的每个数i，计算出X-i是否存在，复杂度O(n)。
于是就是复杂度O(nlogn) + O(n) = O(nlogn)

㈤ B树算法难么

感觉挺难。
B树的定义
假设B树的度为t（t>=2），则B树满足如下要求：（参考算法导论）
（1）
每个非根节点至少包含t-1个关键字，t个指向子节点的指针；至多包含2t-1个关键字，2t个指向子女的指针（叶子节点的子女为空）。
（2）
节点的所有key按非降序存放，假设节点的关键字分别为K[1],
K[2]
…
K[n],
指向子女的指针分别为P[1],
P[2]…P[n+1]，其中n为节点关键字的个数。则有：
P[1]
<=
K[1]
<=
P[2]
<=
K[2]
…..<=
K[n]
<=P[n+1]
//
这里P[n]也指其指向的关键字
（3）
若根节点非空，则根节点至少包含两个子女；
（4）
所有的叶子节点都在同一层。
B树的搜索，search（root,
target）
从root出发，对每个节点，找到大于或等于target关键字中最小的K[i]，如果K[i]与target相等，则查找成功；否则在P[i]中递归搜索target，直到到达叶子节点，如仍未找到则说明关键字不在B树中，查找失败。
B树的插入，insert(root,target)
B树的插入需要沿着搜索的路径从root一直到叶节点，根据B树的规则，每个节点的关键字个数在[t-1,
2t-1]之间，故当target要加入到某个叶子时，如果该叶子节点已经有2t-1个关键字，则再加入target就违反了B树的定义，这时就需要对该叶子节点进行分裂，将叶子以中间节点为界，分成两个包含t-1个关键字的子节点，同时把中间节点提升到该叶子的父节点中，如果这样使得父节点的关键字个数超过2t-1，则要继续向上分裂，直到根节点，根节点的分裂会使得树加高一层。
上面的过程需要回溯，那么能否从根下降到叶节点后不回溯就能完成节点的插入呢？答案是肯定的，核心思想就是未雨绸缪，在下降的过程中，一旦遇到已满的节点（关键字个数为2t-1），就就对该节点进行分裂，这样就保证在叶子节点需要分裂时，其父节点一定是非满的，从而不需要再向上回溯。
B树的删除，delete(root,target)
在删除B树节点时，为了避免回溯，当遇到需要合并的节点时就立即执行合并，B树的删除算法如下：从root向叶子节点按照search规律遍历：
（1）
如果target在叶节点x中，则直接从x中删除target，情况（2）和（3）会保证当再叶子节点找到target时，肯定能借节点或合并成功而不会引起父节点的关键字个数少于t-1。
（2）
如果target在分支节点x中：
（a）
如果x的左分支节点y至少包含t个关键字，则找出y的最右的关键字prev，并替换target，并在y中递归删除prev。
（b）
如果x的右分支节点z至少包含t个关键字，则找出z的最左的关键字next，并替换target，并在z中递归删除next。
（c）
否则，如果y和z都只有t-1个关键字，则将targe与z合并到y中，使得y有2t-1个关键字，再从y中递归删除target。
（3）
如果关键字不在分支节点x中，则必然在x的某个分支节点p[i]中，如果p[i]节点只有t-1个关键字。
（a）
如果p[i-1]拥有至少t个关键字，则将x的某个关键字降至p[i]中，将p[i-1]的最大节点上升至x中。
（b）
如果p[i+1]拥有至少t个关键字，则将x个某个关键字降至p[i]中，将p[i+1]的最小关键字上升至x个。
（c）
如果p[i-1]与p[i+1]都拥有t-1个关键字，则将p[i]与其中一个兄弟合并，将x的一个关键字降至合并的节点中，成为中间关键字。