书籍简介
第一章 字符串
1.0 本章导读
1.1 旋转字符串
1.2 字符串包含
1.3 字符串转换成整数
1.4 回文判断
1.5 最长回文子串
1.6 字符串的全排列
1.10 本章习题
第二章 数组
2.0 本章导读
2.1 寻找最小的 k 个数
2.2 寻找和为定值的两个数
2.3 寻找和为定值的多个数
2.4 最大连续子数组和
2.5 跳台阶
2.6 奇偶排序
2.7 荷兰国旗
2.8 矩阵相乘
2.9 完美洗牌
2.10 K个最小和 (UVA 11997 K Smallest Sums)
2.15 本章习题
第三章 树
3.0 本章导读
3.1 红黑树
3.2 B树
3.3 最近公共祖先LCA
3.5 R树：处理空间存储问题
3.10 本章习题
第四章 查找匹配
4.1 有序数组的查找
4.2 行列递增矩阵的查找
4.3 出现次数超过一半的数字
第五章 动态规划
5.0 本章导读
5.1 最大连续乘积子串
5.2 字符串编辑距离
5.3 格子取数
5.4 交替字符串
5.6 最长递增子序列
5.10 本章习题
第六章 海量数据处理
6.0 本章导读
6.1 关联式容器
6.2 分而治之
6.3 simhash算法
6.4 外排序
6.5 MapReduce
6.6 多层划分
6.7 Bitmap
6.8 Bloom filter
6.9 Trie树
6.10 数据库
6.11 倒排索引
6.15 本章习题
第七章 机器学习
7.1 K 近邻算法
7.2 支持向量机
附录 更多题型
附录A 语言基础
附录B 概率统计
附录C 智力逻辑
附录D 系统设计
附录E 操作系统
附录F 网络协议
3.0 本章导读 - 《程序员编程艺术：面试和算法心得》 - IT书包
网站首页
3.0 本章导读
在前面的第二章，我们介绍了数组，数组因为是下标定位，所以查找极快，而hashtable(key,value)借鉴数组O(1)定位的特点，key映射value，所以查找也相当快，只是需要耗费一定的空间存储key和value，所以是典型的空间换时间的思想。 其中，理解红黑树，先理解二叉查找树和2-3树，为何？首先，二叉查找树中的结点是2-结点（一个键两条链），引入3-结点（两个键三条链），即成2-3树；再者，将2-3树中3-结点分解，即成红黑树，故结合二叉查找树易查找和2-3树易插入的特点，便成了红黑二叉查找树，简称红黑树。 进一步，理解了2-3树，也就理解了B树、B+树、B*树，因为2-3树就是一棵3阶的B树，而一颗3阶的B树各个结点关键字数满足1-2，故结点关键字数多于2达到饱和时分裂，结点关键字数少于1时则从兄弟结点“借”关键字补充。 但为何有了红黑树，还要出现B树呢？原因是当计算机要处理的数据量一大，便无法一次性装入内存处理，于是，计算机会把大部分备用的数据存在磁盘中，有需要的时候，就从磁盘调取到在内存中处理，如果处理时修改了数据，则再次写会磁盘，如此导致了不断的磁盘IO读写，而树的高度越到，查找文件所需要的磁盘IO读写次数越多。 因此，为了进一步降低树的高度，具有多个孩子的B树的应运而生，正因为B树每一个结点可以有几个到几千个孩子，在结点数目一定的情况下，树的高度会大大降低，此外，B树的根结点和部分顶层数据在内存中，大部分下层数据在磁盘上。
上一篇：
第三章 树
下一篇：
3.1 红黑树
