电子商务的门户网站,做网站是什么职业,网络推广方案的步骤有哪些?,微信公众号怎样发布wordpress目录 引出B树插入insert删除remove 红黑树(red black tree)自底向上的插入自顶向下红黑树自顶向下的删除 标准库中的集合Set与映射Map关于Set接口关于Map接口TreeSet类和TreeMap类的实现使用多个映射Map#xff1a;一个词典的案例方案一#xff1a;使用一个Map对象方案二一个词典的案例方案一使用一个Map对象方案二按照长度分组方案三按照多个字母分组 原书代码 总结 引出 1.B树阶M数据树叶上根的儿子数在2和M之间除根外非树叶节点儿子为M/2和M之间 2.B树的插入引起分裂B树的删除引起合并和领养 3.红黑树根是黑的红色节点的儿子必须是黑的所有路径的黑色节点数相同 4.红黑树的插入颜色翻转单旋转插入节点定颜色 5.java标准库的set和map使用红黑树
B树
迄今为止我们始终假设可以把整个数据结构存储到计算机的主存中。可是如果数据更多装不下主存那么这就意味着必须把数据结构放到磁盘上。此时因为大O模型不再适用所以导致游戏规则发生了变化。
在磁盘上典型的查找树执行如下设想要访问佛罗里达州公民的驾驶记录。假设有1千万项每一个关键字是32字节代表一个名字而一个记录是256个字节。假设这些数据不能都装人主存而我们是正在使用系统的20个用户中的一个因此有1/20的资源。这样在1秒内我们可以执行2500万次指令或者执行6次磁盘访问。
不平衡的二叉查找树是一个灾难。在最坏情形下它具有线性的深度从而可能需要1千万次磁盘访问。平均来看一次成功的查找可能需要1.381ogN次磁盘访问由于10g10000000≈24因此平均一次查找需要32次磁盘访问或5秒的时间。在一棵典型的随机构造的树中我们预料会有一些节点的深度要深3倍它们需要大约100次磁盘访问或16秒的时间。
AVL树多少要好一些。1.44logN的最坏情形不可能发生典型的情形是非常接近于logN。这样一棵AVL树平均将使用大约25次磁盘访问需要的时间是4秒。
我们想要把磁盘访问次数减小到一个非常小的常数比如3或4而且我们愿意写一个复杂的程序来做这件事因为在合理情况下机器指令基本上是不占时间的。由于典型的AVL树接近到最优的高度因此应该清楚的是二叉查找树是不可行的。使用二叉查找树我们不能行进到低于logN。解法直觉上看是简单的如果有更多的分支那么就有更少的高度
。这样31个节点的理想二叉树(perfect binary tree)有5层而31个节点的5叉树则只有3层如图4-59所示一棵M叉查找树(M-ary search tree)可以有M路分支。随着分支增加树的深度在减少。一棵完全二叉树(complete binary tree)的高度大约为logN,而一棵完全M叉树(complete M-ary tree) 的高度大约是logm N。 我们可以以与建立二叉查找树大致相同的方式建立M叉查找树。在二叉查找树中需要一个关键字来决定两个分支到底取用哪个分支而在M叉查找树中需要M1个关键字来决定选取哪个分支。为使这种方案在最坏的情形下有效需要保证M叉查找树以某种方式得到平衡。否则像二叉查找树它可能退化成一个链表。实际上我们甚至想要更加限制性的平衡条件即 不想要M叉查找树退化到甚至是二叉查找树因为那时我们又将无法摆脱logN次访问了。 B树、B树 图4-60显示5阶B树的一个例子。注意所有的非叶节点的儿子数都在3和5之间从而有2到4个关键字)根可能只有两个儿子。这里我们有L5(在这个例子中L和M恰好是相同的但这不是必需的)。由于L是5因此每片树叶有3到5个数据项。要求节点半满将保证B树不致退化成简单的二叉树。虽然存在改变该结构的各种B树的定义但大部分在一些次要的细节上变化而我们这个定义是流行的形式之一。 插入insert
我们首先考查插入。设想要把57插人到图4-60的B树中。沿树向下查找揭示出它不在树中。此时我们把它作为第5项添加到树叶中。注意我们可能要为此重新组织该树叶上的所有数据。然而与磁盘访问相比在这种情况下它还包含一次磁盘写这项操作的开销可以忽略不计。 当然这是相对简单的因为该树叶还没有被装满。设现在要插入55。图4-61显示一个问题55想要插入其中的那片树叶已经满了。不过解法却不复杂由于我们现在有L1项因此把它们分成两片树叶这两片树叶保证都有所需要的记录的最小个数。我们形成两片树叶每叶3项。写这两片树叶需要2次磁盘访问更新它们的父节点需要第3次磁盘访问。注意在父节点中关键字和分支均发生了变化但是这种变化是以容易计算的受控的方式处理的。最后得到的B树在图4-62中给出。虽然分裂节点是耗时的因为它至少需要2次附加的磁盘写但它相对很少发生。
例如如果L是32那么当节点被分裂时具有16和17项的两片树叶分别被建立。对于有17项的那片树叶我们可以再执行15次插入而不用另外的分裂。换句话说对于每次分裂大致存在L/2次非分裂的插人。 前面例子中的节点分裂之所以行得通是因为其父节点的儿子个数尚未满员。可是如果满员了又会怎样呢例如假设我们想要把40插入到图4-62的B树中。此时必须把包含关键字35到39而现在又要包含40的树叶分裂成2片树叶。但是这将使父节点有6个儿子可是它只能有5个儿子。因此解法就要分裂这个父节点。结果在图4-63中给出。当父节点被分裂时必须更新那些关键字以及还有父节点的父亲的值这样就招致额外的两次磁盘写从而这次插入花费5次磁盘写)。然而虽然由于有大量的情况要考虑而使得程序确实不那么简单但是这些关键字还是以受控的方式变化。 正如这里的情形所示当一个非叶节点分裂时它的父节点得到了一个儿子。如果父节点的儿子个数已经达到规定的限度怎么办呢在这种情况下继续沿树向上分裂节点直到找到一个不需要再分裂的父节点或者到达树根。
如果分裂树根那么我们就得到两个树根。显然这是不可接受的但我们可以建立一个新的根这个根以分裂得到的两个树根作为它的两个儿子。
这就是为什么准许树根可以最少有两个儿子的特权的原因。这也是B树增加高度的唯一方式。不用说一路向上分裂直到根的情况是一种特别少见的异常事件因为一棵具有4层的树意味着在整个插入序列中已经被分裂了3次假设没有删除发生。
事实上任何非叶节点的分裂也是相当少见的。还有其他一些方法处理儿子过多的情况。一种方法是在相邻节点有空间时把一个儿子交给该邻节点领养。例如为了把29插入到图4-63的B树中可以把32移到下一片树叶而腾出一个空间。这种方法要求对父节点进行修改因为有些关键字受到了影响。然而它趋向于使得节点更满从而在长时间运行中节省空间。 删除remove
我们可以通过查找要删除的项并在找到后删除它来执行删除操作。
问题在于如果被删元所在的树叶的数据项数已经是最小值那么删除后它的项数就低于最小值了。我们可以通过在邻节点本身没有达到最小值时领养一个邻项来矫正这种状况。如果相邻结点已经达到最小值那么可以与该相邻节点联合以形成一片满叶。可是这意味着其父节点失去一个儿子。如果失去儿子的结果又引起父节点的儿子数低于最小值那么我们使用相同的策略继续进行。这个过程可以一直上行到根。根不可能只有一个儿子要是允许根有一个儿子那可就愚蠢了。如果这个领养过程的结果使得根只剩下一个儿子那么删除该根并让它的这个儿子作为树的新根。这是B树降低高度的唯一的方式。
例如假设我们想要从图4-63的B树中删除99。由于那片树叶只有两项而它的邻居已经是最小值3项了因此我们把这些项合并成有5项的一片新的树叶。结果它们的父节点只有两个儿子了。这时该父节点可以从它的邻节点领养因为邻节点有4个儿子。领养的结果使得双方都有3个儿子结果如图4-64所示。 红黑树(red black tree)
历史上AVL树流行的另一变种是红黑树(red black tree)。对红黑树的操作在最坏情形下花费O(logN)时间而且我们将看到对于插入操作的一种审慎的非递归实现可以相对容易地完成与AVL树相比。 红黑树是具有下列着色性质的二叉查找树 1.每一个节点或者着成红色或者着成黑色。 2.根是黑色的。 3.如果一个节点是红色的那么它的子节点必须是黑色的。 4.从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。
着色法则的一个结论是红黑树的高度最多是2log(N1)。因此查找操作保证是一种对数的操作。 自底向上的插入 前面已经提到如果新插入的项的父节点是黑色那么插入完成。因此将25插入到图12-9的树中是简单的操作。 如果父节点是红色的那么有几种情形每种都有一个镜像对称需要考虑。首先假设这个父节点的兄弟是黑色的我们采纳约定u11节点都是黑色的。这对于插人3或8是适用的但对插入99不适用。令X是新添加的树叶P是它的父节点S是该父节点的兄弟若存在)G是祖父节点。在这种情形只有X和P是红色的G是黑色的否则就会在插入前有两个相连的红色节点违反了红黑树的法则。采用伸展树的术语X,P和G可以形成一个一字形链或之字形链两个方向中的任一个方向。
图12-10指出当P是一个左儿子时注意有一个对称情形)我们应该如何旋转该树。即使X是一片树叶我们还是画出较一殷的情形使得X在树的中间。后面我们将用到这个较一般的旋转。 自顶向下红黑树 上滤的实现需要用一个栈或用一些父链保存路径。我们看到如果使用一个自顶向下的过程则伸展树会更有效事实上我们可以对红黑树应用自顶向下的过程而保证S不会是红色的。
这个过程在概念上是容易的。在向下的过程中当看到一个节点X有两个红儿子的时候可使X呈红色而让它的两个儿子是黑的。如果X是根则在颜色翻转后它将是红色但是为恢复性质2可以直接着成黑色)
图12-11显示这种颜色翻转的现象只有当X的父节点P也是红的时候这种翻转将破坏红黑的法则。但是此时可以应用图12-10中适当的旋转。如果X的父节点的兄弟是红色会如何呢这种可能已经被从顶向下过程中的行动所排除因此X的父节点的兄弟不可能是红色
特别地如果在沿树向下的过程中我们看到一个节点Y有两个红儿子那么我们知道Y的孙子必然是黑的由于Y的儿子也要变成黑的甚至在可能发生的旋转之后因此我们将不会看到两层上另外的红节点。这样当我们看到X,若X的父节点是红的则X的父节点的兄弟不可能也是红色的。 例如假设要将45插入到图12-9中的树上。在沿树向下的过程中我们看到50有两个红儿子。因此我们执行一次颜色翻转使50为红的40和55是黑的。现在50和60都是红的。在60和70之间执行单旋转使得60是30的右子树的黑根而70和50都是红的。如果我们在路径上看到另外的含有两个红儿子的节点那么我们继续执行同样的操作。当我们到达树叶时把45作为红节点插入由于父节点是黑的因此插入完成。最后得到如图12-12所示的树。 如图12-12所示所得到的红黑树常常平衡得很好。经验指出平均红黑树大约和平均AVL树一样深从而查找时间一般接近最优。红黑树的优点是执行插入所需要的开销相对较低另外就是实践中发生的旋转相对较少。
自顶向下的删除
红黑树中的删除也可以自顶向下进行。每一件工作都归结于能够删除树叶。这是因为要删除一个带有两个儿子的节点用右子树上的最小节点代替它该节点必然最多有一个儿子然后将该节点删除。只有一个右儿子的节点可以用相同的方式删除而只有一个左儿子的节点通过用其左子树上最大节点替换而被删除然后再将该节点删除。注意对于红黑树我们不要使用绕过带有一个儿子的节点的情形的方法因为这可能在树的中部连接两个红色节点增加红黑条件实现的困难。
当然红色树叶的删除很简单。然而如果一片树叶是黑的那么删除操作会复杂得多因为黑色节点的删除将破坏条件4。解决方法是保证从上到下删除期间树叶是红的。在整个讨论中令X为当前节点T是它的兄弟而P是它们的父亲。开始时我们把树的根涂成红色。当沿树向下遍历时我们设法保证X是红色的。当到达一个新的节点时我们要确信P是红的归纳地我们试图继续保持这种不变性并且X和T是黑的因为不能有两个相连的红色节点)。这存在两种主要的情形。首先设X有两个黑儿子。
此时有三种子情况如图12-17所示。如果T也有两个黑儿子那么可以翻转X、T和P的颜色来保持这种不变性。否则T的儿子之一是红的。根据这个儿子节点是哪一个我们可以应用图12-17所示的第二和第三种情形表示的旋转。特别要注意这种情形对于树叶将是适用的因为nul1Node被认为是黑的。
其次X的儿子之一是红的。在这种情形下我们落到下一层上得到新的X、T和P。如果幸运X落在红儿子上则我们可以继续向前进行。如果不是这样那么我们知道T将是红的而X和P将是黑的。我们可以旋转T和P,使得X的新父亲是红的当然X及其祖父将是黑的。此时我们可以回到第一种主情况。 标准库中的集合Set与映射Map
List容器即ArrayList和LinkedList用于查找效率很低。因此Collections API提供了两个附加容器Set和Map,它们对诸如插入、删除和查找等基本操作提供有效的实现。
关于Set接口
Set接口代表不允许重复元的Collection。由接口SortedSet给出的一种特殊类型的Set保证其中的各项处于有序的状态。因为一个Set IS-A Collection,所以用于访问继承Collection的list的项的方法也对Set有效。
由Set所要求的一些独特的操作是一些插入、删除以及有效地执行基本查找的能力。对于Set,add方法如果执行成功则返回true,否则返回false,因为被添加的项已经存在。保持各项以有序状态的Set的实现是TreeSet。TreeSet类的基本操作花费对数最坏情形时间。
关于Map接口
Map是一个接口代表由关键字以及它们的值组成的一些项的集合。关键字必须是唯一的但是若干关键字可以映射到一些相同的值。因此值不必是唯一的。在SortedMap接口中映射中的关键字保持逻辑上有序状态。SortedMap接口的一种实现是TreeMap类。Map的基本操作包括诸如isEmpty、clear、size等方法而且最重要的是包含下列方法 get返回Map中与key相关的值或当key不存在时返回null。如果在Map中不存在null值那么由get返回的值可以用来确定key是否在Map中。然而如果存在nul1值那么必须使用containsKey。方法put把关键字/值对置入Map中或者返回null,或者返回与key相联系的老值。
通过一个Map进行迭代要比Collection复杂因为Map不提供迭代器而是提供3种方法将Map对象的视图作为Collection对象返回。由于这些视图本身就是Collection,因此它们可以被迭代。所提供的3种方法如下 方法keySet和values返回简单的集合这些关键字不包含重复元因此以一个Set对象的形式返回)。这里的entrySet方法是作为一些项而形成的Set对象被返回的由于关键字是唯一的因此不存在重复项)。每一项均由被嵌套的接口Map.Entry表示。对于类型Map.Entry的对象其现有的方法包括访问关键字、关键字的值以及改变关键字的值 TreeSet类和TreeMap类的实现 Java要求TreeSet和TreeMap支持基本的add、remove和contains操作以对数最坏情形时间完成。因此基本的实现方法就是平衡二叉查找树。一般说来我们并不使用AVL树而是经常使用一些自顶向下的红黑树。 实现TreeSet和TreeMap的一个重要问题是提供对迭代器类的支持。当然在内部迭代器保留到迭代中“当前”节点的一个链接。困难部分是到下一个节点高效的推进。存在几种可能的解决方案其中的一些方案叙述如下
1.在构造迭代器时让每个迭代器把包含诸TreeSet项的数组作为该迭代器的数据存储。这有不足因为我们还可以使用toArray,并不需要迭代器。
2.让迭代器保留存储通向当前节点的路径上的节点的一个栈。根据该信息可以推出迭代器中的下一个节点它或者是包含最小项的当前节点右子树上的节点或者包含其左子树当前节点的最近的祖先。这使得迭代器多少有些大并导致迭代器的代码臃肿。
3.让查找树中的每个节点除存储子节点外还要存储它的父节点。此时迭代器不至于那么大但是在每个节点上需要额外的内存并且迭代器的代码仍然臃肿。
4.让每个节点保留两个附加的链一个通向下一个更小的节点另一个通向下一个更大的节点。这要占用空间不过迭代器做起来非常简单并且保留这些链也很容易。
5.只对那些具有nu11左链或nul1右链的节点保留附加的链。通过使用附加的布尔变量使得这些例程判断是一个左链正在被用作标准的二叉树左链还是一个通向下一个更小节点的链类似地对右链也有类似的判断。这种做法叫作线索树(threaded tree),用于许多平衡二叉查找树的实现中。
使用多个映射Map一个词典的案例
许多单词都和另外一些单词相似。例如通过改变第1个字母单词wine可以变成dine、fine、line、mine、nine、pine或vine通过改变第3个字母wine可以变成wide、wife、wipe或wire。通过改变第4个字母wine可以变成wind、wing、wink或wins。这样我们就得到l5个不同的单词它们仅仅通过改变wine中的一个字母而得到。实际上存在20多个不同的单词其中有些单词更生僻。我们想要编写一个程序以找出通过单个字母的替换可以变成至少15个其他单词的单词。
假设我们有一个词典由大约89000个不同长度的不同单词组成。大部分单词在6~11个字母之间。其中6字母单词有8205个7字母单词有11989个8字母单词13672个9字母单词13014个10字母单词11297个11字母单词8617个实际上最可变化的单词是3字母、4字母和5字母单词不过更长的单词检查起来更耗费时间)。
方案一使用一个Map对象
最直接了当的策略是使用一个Map对象其中的关键字是单词而关键字的值是用1字母替换能够从关键字变换得到的一列单词。
该算法的问题在于速度慢在我们的计算机上花费75秒的时间。一个明显的改进是避免比较不同长度的单词。我们可以把单词按照长度分组然后对各个分组运行刚才提供的程序。为此可以使用第2个映射此时的关键字是个整数代表单词的长而值则是该长度的所有单词的集合。我们可以使用一个List存储每个集合然后应用相同的做法。程序所示。第9行是第2个Map的声明第13行和第14行将分组置入该Map,然后用一个附加的循环对每组单词迭代。与第1个算法比较第2个算法只是在边际上编程困难其运行时间为16秒大约快了5倍。 package com.tianju.book.jpa.mapLearn;import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;public class WordDemo {private static ListString wordList Arrays.asList(wine, dine, fine, line, mine, nine, pine, vine, wide,wife, wipe, wire, wind, wing, wink, wins);/*** 当两个单词长度相等并且只有1个字母不同时返回true*/private static boolean isOneCharDiff(String word1,String word2){if (word2.length()!word1.length()){return false; // 长度不同返回false}int diff 0;for (int i0;iword1.length();i){if (word1.charAt(i)!word2.charAt(i)){if (diff1){return false;}diff diff 1;}}return diff 1;}// {mine[wine, dine, fine, line, nine, pine, vine], wins[wine, wind, wing, wink],/*** 自己实现的方式比大佬的要多一半的循环次数* getAdjWords方法的for循环次数96* computeAdjacentWordsSlow方法的for循环次数48* param words* return*/public static MapString,ListString getAdjWords(ListString words){MapString,ListString adjMap new HashMap();int forTimes 0;for (int i0;iwords.size();i){for (int j0;jwords.size();j){
// System.out.println(words.get(i) -- words.get(j));if (isOneCharDiff(words.get(i), words.get(j))){ // 只有一个单词不同ListString stringList adjMap.get(words.get(i));if (stringListnull){stringList new ArrayList();adjMap.put(words.get(i),stringList);}stringList.add(words.get(j));forTimes;}}}System.out.println(getAdjWords方法的for循环次数forTimes);return adjMap;}// Computes a map in which the keys are words and values are Lists of words// that differ in only one character from the corresponding key.// Uses a quadratic algorithm (with appropriate Map).public static MapString,ListString computeAdjacentWordsSlow( ListString theWords ){MapString,ListString adjWords new HashMap( );String [ ] words new String[ theWords.size( ) ];int forTimes 0;theWords.toArray( words );for( int i 0; i words.length; i )for( int j i 1; j words.length; j )if( isOneCharDiff( words[ i ], words[ j ] ) ){update( adjWords, words[ i ], words[ j ] );update( adjWords, words[ j ], words[ i ] );forTimes;}System.out.println(computeAdjacentWordsSlow方法的for循环次数forTimes);return adjWords;}private static KeyType void update( MapKeyType,ListString m, KeyType key, String value ){ListString lst m.get( key );if( lst null ){lst new ArrayList( );m.put( key, lst );}lst.add( value );}public static void main(String[] args) {/*** 第一种方式把单词作为键把只需要变换1个单词就能得到新单词的所有单词的List作为该键的值*/System.out.println(isOneCharDiff(dog, dop));MapString, ListString adjWords getAdjWords(wordList);System.out.println(adjWords);MapString, ListString listMap computeAdjacentWordsSlow(wordList);System.out.println(listMap);}
}方案二按照长度分组
一个明显的改进是避免比较不同长度的单词。我们可以把单词按照长度分组然后对各个分组运行刚才提供的程序。为此可以使用第2个映射此时的关键字是个整数代表单词的长而值则是该长度的所有单词的集合。我们可以使用一个List存储每个集合然后应用相同的做法。程序所示。第9行是第2个Map的声明第13行和第14行将分组置入该Map,然后用一个附加的循环对每组单词迭代。与第1个算法比较第2个算法只是在边际上编程困难其运行时间为16秒大约快了5倍。 package com.tianju.book.jpa.mapLearn;import java.util.*;public class WordDemo2 {private static ListString wordList Arrays.asList(wine, dine, fine, line, mine, nine, pine, vine, wide,wife, wipe, wire, wind, wing, wink, wins);/*** 当两个单词长度相等并且只有1个字母不同时返回true*/private static boolean isOneCharDiff(String word1,String word2){if (word2.length()!word1.length()){return false; // 长度不同返回false}int diff 0;for (int i0;iword1.length();i){if (word1.charAt(i)!word2.charAt(i)){if (diff1){return false;}diff diff 1;}}return diff 1;}/*** 把单词按照长度进行分组*/public static MapString,ListString getAdjWords(ListString wordList){MapString,ListString adjMap new HashMap();// 先按照单词长度进行分组MapInteger,ListString wordsByLength new HashMap( );for (String word:wordList) {ListString lst wordsByLength.get(word.length());if (lstnull){lst new ArrayList();wordsByLength.put(word.length(), lst);}lst.add(word);}System.out.println(wordsByLength);// 获得分组之后的单词再进行操作对每组单词进行迭代避免对比不同长度的单词for (ListString groupWords:wordsByLength.values()){int forTimes 0;System.out.println(groupWords);ListString words groupWords;for (int i0;iwords.size();i){for (int j i1;jwords.size();j){if (isOneCharDiff(words.get(i), words.get(j))){update(adjMap, words.get(i), words.get(j));update(adjMap,words.get(j),words.get(i));forTimes;}}}System.out.println(forTime: forTimes);}return adjMap;}private static KeyType void update( MapKeyType,ListString m, KeyType key, String value ){ListString lst m.get( key );if( lst null ){lst new ArrayList( );m.put( key, lst );}lst.add( value );}public static void main(String[] args) {System.out.println(getAdjWords(wordList));}
}方案三按照多个字母分组
第3个算法更复杂使用一些附加的映射和前面一样将单词按照长度分组然后分别对每组运算。
为理解这个算法是如何工作的假设我们对长度为4的单词操作。这时首先要找出像wine和nine这样的单词对它们除第1个字母外完全相同。
对于长度为4的每一个单词一种做法是删除第1个字母留下一个3字母单词代表。这样就形成一个M即其中的关键字为这种代表而其值是所有包含同一代表的单词的一个List。例如在考虑4字母单词组的第1个字母时代表“ine”对应“dine”“fine”“wine”“nine”“mine”“vine”“pine”“line”。代表“oot”对应“boot”“foot”“hoot”“loot”“soot”“zoot”。
每一个作为最后的Map的一个值的List对象都形成单词的一个集团其中任何一个单词均可以通过单字母替换变成另一个单词因此在这个最后的Map构成之后很容易遍历它以及添加一些项到正在计算的原始Map中。然后我们使用一个新的Map再处理4字母单词组的第2个字母。此后是第3个字母最后处理第4个字母。 代码初步理解 package com.tianju.book.jpa.mapLearn;import java.util.*;public class WordDemo3 {private static ListString wordList Arrays.asList(wine, dine, fine, line, mine, nine, pine, vine, wide,wife, wipe, wire, wind, wing, wink, wins);// Computes a map in which the keys are words and values are Lists of words// that differ in only one character from the corresponding key.// Uses an efficient algorithm that is O(N log N) with a TreeMap, or// O(N) if a HashMap is used.public static MapString,ListString computeAdjacentWords( ListString words ){MapString,ListString adjWords new TreeMap( );MapInteger,ListString wordsByLength new TreeMap( );// Group the words by their lengthfor( String w : words )update( wordsByLength, w.length( ), w );// Work on each group separatelyfor( Map.EntryInteger,ListString entry : wordsByLength.entrySet( ) ){ListString groupsWords entry.getValue( );int groupNum entry.getKey( );// Work on each position in each groupfor( int i 0; i groupNum; i ){// Remove one character in specified position, computing representative.// Words with same representative are adjacent, so first populate// a mapMapString,ListString repToWord new HashMap( );for( String str : groupsWords ){String rep str.substring( 0, i ) str.substring( i 1 );update( repToWord, rep, str );}// and then look for map values with more than one stringfor( ListString wordClique : repToWord.values( ) )if( wordClique.size( ) 2 )for( String s1 : wordClique )for( String s2 : wordClique )if( s1 ! s2 ) // must be same string; equals not neededupdate( adjWords, s1, s2 );}}return adjWords;}private static KeyType void update( MapKeyType,ListString m, KeyType key, String value ){ListString lst m.get( key );if( lst null ){lst new ArrayList( );m.put( key, lst );}lst.add( value );}public static void main(String[] args) {MapString, ListString map computeAdjacentWords(wordList);System.out.println(map);}}该算法的一种实现其运行时间改进到4秒。虽然这些附加的Map使得算法更快而且句子结构也相对清晰但是程序没有利用到该Map的关键字保持有序排列的事实
同样有可能一种支持Map的操作但不保证有序排列的数据结构可能运行得更快因为它要做的工作更少。第5章将探索这种可能性并讨论隐藏在另一种Map实现背后的想法这种实现叫作HashMap。HashMap将实现的运行时间从1秒减少到0.8秒。
原书代码
package com.tianju.book.jpa.mapLearn;import java.io.*;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.HashMap;
import java.util.Queue;/*
DISTRIBUTION OF DICTIONARY:
Read the words...88984
1 1
2 48
3 601
4 2409
5 4882
6 8205
7 11989
8 13672
9 13014
10 11297
11 8617
12 6003
13 3814
14 2173
15 1169
16 600
17 302
18 107
19 53
20 28
Elapsed time FAST: 2.8 vs 3.8
Elapsed time MEDIUM: 50.9 vs 50.5
Elapsed time SLOW: 95.9 vs 96.1 (H vs T)
**/public class WordLadder
{public static ListString readWords( BufferedReader in ) throws IOException{String oneLine;ListString lst new ArrayList( );while( ( oneLine in.readLine( ) ) ! null )lst.add( oneLine );return lst;}// Returns true is word1 and word2 are the same length// and differ in only one character.private static boolean oneCharOff( String word1, String word2 ){if( word1.length( ) ! word2.length( ) )return false;int diffs 0;for( int i 0; i word1.length( ); i )if( word1.charAt( i ) ! word2.charAt( i ) )if( diffs 1 )return false;return diffs 1;}private static KeyType void update( MapKeyType,ListString m, KeyType key, String value ){ListString lst m.get( key );if( lst null ){lst new ArrayList( );m.put( key, lst );}lst.add( value );}// Computes a map in which the keys are words and values are Lists of words// that differ in only one character from the corresponding key.// Uses a quadratic algorithm (with appropriate Map).public static MapString,ListString computeAdjacentWordsSlow( ListString theWords ){MapString,ListString adjWords new HashMap( );String [ ] words new String[ theWords.size( ) ];theWords.toArray( words );for( int i 0; i words.length; i )for( int j i 1; j words.length; j )if( oneCharOff( words[ i ], words[ j ] ) ){update( adjWords, words[ i ], words[ j ] );update( adjWords, words[ j ], words[ i ] );}return adjWords;}// Computes a map in which the keys are words and values are Lists of words// that differ in only one character from the corresponding key.// Uses a quadratic algorithm (with appropriate Map), but speeds things up a little by// maintaining an additional map that groups words by their length.public static MapString,ListString computeAdjacentWordsMedium( ListString theWords ){MapString,ListString adjWords new HashMap( );MapInteger,ListString wordsByLength new HashMap( );// Group the words by their lengthfor( String w : theWords )update( wordsByLength, w.length( ), w );// Work on each group separatelyfor( ListString groupsWords : wordsByLength.values( ) ){String [ ] words new String[ groupsWords.size( ) ];groupsWords.toArray( words );for( int i 0; i words.length; i )for( int j i 1; j words.length; j )if( oneCharOff( words[ i ], words[ j ] ) ){update( adjWords, words[ i ], words[ j ] );update( adjWords, words[ j ], words[ i ] );}}return adjWords;}// Computes a map in which the keys are words and values are Lists of words// that differ in only one character from the corresponding key.// Uses an efficient algorithm that is O(N log N) with a TreeMap, or// O(N) if a HashMap is used.public static MapString,ListString computeAdjacentWords( ListString words ){MapString,ListString adjWords new TreeMap( );MapInteger,ListString wordsByLength new TreeMap( );// Group the words by their lengthfor( String w : words )update( wordsByLength, w.length( ), w );// Work on each group separatelyfor( Map.EntryInteger,ListString entry : wordsByLength.entrySet( ) ){ListString groupsWords entry.getValue( );int groupNum entry.getKey( );// Work on each position in each groupfor( int i 0; i groupNum; i ){// Remove one character in specified position, computing representative.// Words with same representative are adjacent, so first populate// a mapMapString,ListString repToWord new HashMap( );for( String str : groupsWords ){String rep str.substring( 0, i ) str.substring( i 1 );update( repToWord, rep, str );}// and then look for map values with more than one stringfor( ListString wordClique : repToWord.values( ) )if( wordClique.size( ) 2 )for( String s1 : wordClique )for( String s2 : wordClique )if( s1 ! s2 ) // must be same string; equals not neededupdate( adjWords, s1, s2 );}}return adjWords;}// Find most changeable word: the word that differs in only one// character with the most words. Return a list of these words, in case of a tie.public static ListString findMostChangeable( MapString,ListString adjacentWords ){ListString mostChangeableWords new ArrayList( );int maxNumberOfAdjacentWords 0;for( Map.EntryString,ListString entry : adjacentWords.entrySet( ) ){ListString changes entry.getValue( );if( changes.size( ) maxNumberOfAdjacentWords ){maxNumberOfAdjacentWords changes.size( );mostChangeableWords.clear( );}if( changes.size( ) maxNumberOfAdjacentWords )mostChangeableWords.add( entry.getKey( ) );}return mostChangeableWords;}public static void printMostChangeables( ListString mostChangeable,MapString,ListString adjacentWords ){for( String word : mostChangeable ){System.out.print( word : );ListString adjacents adjacentWords.get( word );for( String str : adjacents )System.out.println( str );System.out.println( ( adjacents.size( ) words) );}}public static void printHighChangeables( MapString,ListString adjacentWords,int minWords ){for( Map.EntryString,ListString entry : adjacentWords.entrySet( ) ){ListString words entry.getValue( );if( words.size( ) minWords ){System.out.print( entry.getKey( ) ) words.size( ) ): );for( String w : words )System.out.print( w );System.out.println( );}}}// After the shortest path calculation has run, computes the List that// contains the sequence of word changes to get from first to second.public static ListString getChainFromPreviousMap( MapString,String prev,String first, String second ){LinkedListString result new LinkedList( );if( prev.get( second ) ! null )for( String str second; str ! null; str prev.get( str ) )result.addFirst( str );return result;}// Runs the shortest path calculation from the adjacency map, returning a List// that contains the sequence of words changes to get from first to second.public static ListString findChain( MapString,ListString adjacentWords, String first, String second ){MapString,String previousWord new HashMap( );QueueString q new LinkedList( );q.add( first );while( !q.isEmpty( ) ){String current q.element( ); q.remove( );ListString adj adjacentWords.get( current );if( adj ! null )for( String adjWord : adj )if( previousWord.get( adjWord ) null ){previousWord.put( adjWord, current );q.add( adjWord );}}previousWord.put( first, null );return getChainFromPreviousMap( previousWord, first, second );}// Runs the shortest path calculation from the original list of words, returning// a List that contains the sequence of word changes to get from first to// second. Since this calls computeAdjacentWords, it is recommended that the// user instead call computeAdjacentWords once and then call other findChar for// each word pair.public static ListString findChain( ListString words, String first, String second ){MapString,ListString adjacentWords computeAdjacentWords( words );return findChain( adjacentWords, first, second );}public static void run(String[] args) throws IOException {long start, end;FileReader fin new FileReader( D:\\Myprogram\\springboot-workspace\\spring-book-store\\spring-book-store\\src\\main\\java\\com\\tianju\\book\\jpa\\mapLearn\\dict.txt );BufferedReader bin new BufferedReader( fin );ListString words readWords( bin );System.out.println(words);MapString,ListString adjacentWords;adjacentWords computeAdjacentWordsSlow( words );System.out.println(adjacentWords);}public static void main( String [ ] args ) throws IOException{long start, end;FileReader fin new FileReader( D:\\Myprogram\\springboot-workspace\\spring-book-store\\spring-book-store\\src\\main\\java\\com\\tianju\\book\\jpa\\mapLearn\\dict.txt );// FileReader fin new FileReader( dict.txt );BufferedReader bin new BufferedReader( fin );ListString words readWords( bin );System.out.println( Read the words... words.size( ) );MapString,ListString adjacentWords;start System.currentTimeMillis( );adjacentWords computeAdjacentWords( words );end System.currentTimeMillis( );System.out.println( Elapsed time FAST: (end-start) );start System.currentTimeMillis( );adjacentWords computeAdjacentWordsMedium( words );end System.currentTimeMillis( );System.out.println( Elapsed time MEDIUM: (end-start) );start System.currentTimeMillis( );adjacentWords computeAdjacentWordsSlow( words );end System.currentTimeMillis( );System.out.println( Elapsed time SLOW: (end-start) );// printHighChangeables( adjacentWords, 15 );System.out.println( Adjacents computed... );ListString mostChangeable findMostChangeable( adjacentWords );System.out.println( Most changeable computed... );printMostChangeables( mostChangeable, adjacentWords );BufferedReader in new BufferedReader( new InputStreamReader( System.in ) );for( ; ; ){System.out.println( Enter two words: );String w1 in.readLine( );String w2 in.readLine( );ListString path findChain( adjacentWords, w1, w2 );System.out.print( path.size( ) ... );for( String word : path )System.out.print( word );System.out.println( );}}
} 总结
1.B树阶M数据树叶上根的儿子数在2和M之间除根外非树叶节点儿子为M/2和M之间 2.B树的插入引起分裂B树的删除引起合并和领养 3.红黑树根是黑的红色节点的儿子必须是黑的所有路径的黑色节点数相同 4.红黑树的插入颜色翻转单旋转插入节点定颜色 5.java标准库的set和map使用红黑树
