3.01
教你透彻了解红黑树 二叉查找树 由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。 二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 任意结点的左、右子树也分别为二叉查找树。 没有键值相等的结点（no duplicate nodes）。 因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）.（至于n个结点的二叉树高度为lgn的证明，可参考算法导论 第12章 二叉查找树...
3.02
B树 1.前言： 动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree/B±tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。 但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下，因此我们该想办法降低树的深度，从而减少磁盘查找存取的次数。一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。 这样我们就提出了一个新的查找树结构——平衡多路查找树，即B-tree（B-tree树即B树*，B即Balanced，平衡的意思**）**，这棵神奇的树是在Rudolf Bayer,...
3.03
最近公共祖先LCA问题 问题描述 求有根树的任意两个节点的最近公共祖先。 分析与解法 解答这个问题之前，咱们得先搞清楚到底什么是最近公共祖先。最近公共祖先简称LCA（Lowest Common Ancestor），所谓LCA，是当给定一个有根树T时，对于任意两个结点u、v，找到一个离根最远的结点x，使得x同时是u和v的祖先，x 便是u、v的最近公共祖先。（参见：http://en.wikipedia.org/wiki/Lowest_common_ancestor ）原问题涵盖一般性的有根树，本文为了简化，多使用二叉树来讨论。 举个例子，如针对下图所示的一棵普通的二叉树来讲： 结点3和结点4的最近公共祖先是结点2，即LCA（3 4）=2 。在此，需要注意到当两个结点在同一棵子树上的情况，如结点3和结点2的最近公共祖先为2，即...
3.05
R树：处理空间存储问题 R树简介 984年，加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial...
二叉树与图的经典算法问题集锦
本章堆栈树图相关的习题 1、附近地点搜索 找一个点集中与给定点距离最近的点，同时，给定的二维点集都是固定的，查询可能有很多次，例如，坐标(39.91, 116.37)附近500米内有什么餐馆，那么让你来设计，该怎么做？ 提示：可以建立R树进行二维搜索，或使用GeoHash算法解决。 2、最小操作数 给定一个单词集合Dict，其中每个单词的长度都相同。现从此单词集合Dict中抽取两个单词A、B，我们希望通过若干次操作把单词A变成单词B，每次操作可以改变单词的一个字母，同时，新产生的单词必须是在给定的单词集合Dict中。求所有行得通步数最少的修改方法。 举个例子如下： Given: A = “hit” B = “cog” Dict = [“hot”,“dot”,“dog”,“lot”,“log”] Return [ [“hit”,“hot”,“dot”,“dog”,“cog”], [“hit”,“hot”,“lot”,“log”,“cog”] ] 即把字符串A = "hit"转变成字符串B = “cog”，有以下两种可能： “hit” -> “hot”...
4.01
有序数组的查找 题目描述 给定一个有序的数组，查找某个数是否在数组中，请编程实现。 分析与解法 一看到数组本身已经有序，我想你可能反应出了要用二分查找，毕竟二分查找的适用条件就是有序的。那什么是二分查找呢？ 二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。其算法流程如下： 一开始，范围覆盖整个数组。 将数组的中间项与T进行比较，如果T比数组的中间项要小，则到数组的前半部分继续查找，反之，则到数组的后半部分继续查找。 如此，每次查找可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。 对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。 此时，可能有不少读者心里嘀咕，不就二分查找么，太简单了。 然《编程珠玑》的作者Jon...
行列递增矩阵的查找
...
4.03
出现次数超过一半的数字 题目描述 题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。 分析与解法 一个数组中有很多数，现在我们要找出其中那个出现次数超过总数一半的数字，怎么找呢？大凡当我们碰到某一个杂乱无序的东西时，我们人的内心本质期望是希望把它梳理成有序的。所以，我们得分两种情况来讨论，无序和有序。 解法一 如果无序，那么我们是不是可以先把数组中所有这些数字先进行排序（至于排序方法可选取最常用的快速排序）。排完序后，直接遍历，在遍历整个数组的同时统计每个数字的出现次数，然后把那个出现次数超过一半的数字直接输出，题目便解答完成了。总的时间复杂度为O(nlogn +...
5
本章导读 学习一个算法，可分为3个步骤：首先了解算法本身解决什么问题，然后学习它的解决策略，最后了解某些相似算法之间的联系。例如图算法中， 广搜是一层一层往外遍历，寻找最短路径，其策略是采取队列的方法。 最小生成树是最小代价连接所有点，其策略是贪心，比如Prim的策略是贪心+权重队列。 Dijkstra是寻找单源最短路径，其策略是贪心+非负权重队列。 Floyd是多结点对的最短路径，其策略是动态规划。 而贪心和动态规划是有联系的，贪心是“最优子结构+局部最优”，动态规划是“最优独立重叠子结构+全局最优”。一句话理解动态规划，则是枚举所有状态，然后剪枝，寻找最优状态，同时将每一次求解子问题的结果保存在一张“表格”中，以后再遇到重叠的子问题，从表格中保存的状态中查找（俗称记忆化搜索）。
字符串编辑距离
字符串编辑距离 题目描述 给定一个源串和目标串，能够对源串进行如下操作： 在给定位置上插入一个字符 替换任意字符 删除任意字符 写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于2000。 分析与解法 此题常见的思路是动态规划，假如令dp[i][j] 表示源串S[0…i] 和目标串T[0…j] 的最短编辑距离，其边界：dp[0][j] = j，dp[i][0] = i，那么我们可以得出状态转移方程： dp[i][j] =min{ dp[i-1][j] + 1 , S[i]不在T[0…j]中 dp[i-1][j-1] + 1/0 , S[i]在T[j] dp[i][j-1] + 1 , S[i]在T[0…j-1]中 } 接下来，咱们重点解释下上述3个式子的含义 关于dp[i-1][j] + 1, s.t....