计算机专业英语 教学课件 作者 霍宏涛 Chapter3.ppt

《计算机专业英语 教学课件 作者 霍宏涛 Chapter3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ProfessionalEnglishinComputerFieldChapterThreeDataStructure内容正文BalancedTreeDataStructuresQuicksort阅读材料LinkedListNewAlgorithmsforMaintainingAll-PairsShortestPaths1BalancedTreeDataStructuresComputersizesandpowerSupercomputerandMainframeMinicomputerWorkstationPersonalcomputerKeyWordsr

2、ed-blacktree红黑树,是一种平衡树branchingfactor分支因子branchinessn.分支性asymptoticadj.趋近worstcase最差状况singlepass单遍，单次analogousadj.同样功能的binarytree二叉树inventoryn.目录、存货清单terabyte1Terabyte=1024GBdisburse支付,支出NotesForexample,ab-treewithaheightof2andabranchingfactorof1001canstoreoveronebillionkeysbutrequ

3、iresatmosttwodiskaccessestosearchforanynode.Iftisthisminimizationfactor,everynodemusthaveatleastt-1keys.Undercertaincircumstances,therootnodeisallowedtoviolatethispropertybyhavingfewerthant-1keys.例如，一个高度为2、分支因子为1001的树可以储存高达十亿个键，而最多只需要访问磁盘两次就可以访问到任意一个节点。如果t是最小因子,每个节点都必须有至少t-1个键。在特定的

4、环境下，根节点的键少于t-1并不违反这个属性。NotesIfthenodeisnotfullpriortotheinsertion,nospecialactionisrequired;however,ifthenodeisfull,thenodemustbesplittomakeroomforthenewkey.Sinceeachaccesstoanodemaycorrespondtoacostlydiskaccess,itisdesirabletoavoidthesecondpassbyensuringthattheparentnodeisneverful

5、l.Toaccomplishthis,thepresentedalgorithmsplitsanyfullnodesencounteredwhiledescendingthetree.如果结点在插入前不满，则不需要做特殊处理。但是，如果结点是满的，为了给新的键提供空间，就需要将结点拆分。由于每一次对结点的存取都可能导致高成本的磁盘存取，因此应该尽量使父结点永不满以避免第二次访问。为了达到这个目的，以上算法在向下遍历树结构时拆分所有已满的结点。2QuicksortKeyWordssortingalgorithm排序算法quadraticadj.二次的divid

6、eandconquerstrategy分而治之pivotn.中心点partitionn.分割pseudocoden.伪码sequentiallyadv.连续地auxiliaryadj.辅助的nestedcall嵌套调用KeyWordsrecurrencen.循环,递归theoremn.定理yieldv.产生flipacoinv.(为作出决定而)掷硬币infinitesimallyadv.微不足道地permutationn.排列elidv.修正not-in-place不在原来的地方variantn.不同版本NotesTheadditionalmemoryall

7、ocationsrequiredcanalsodrasticallyimpactspeedandcacheperformanceinpracticalimplementations.Anewthreadisstartedassoonasasublistisavailableforittoworkonanditdoesnotcommunicatewithotherthreads.Whenallthreadscomplete,thesortisdone.在实现中，所需的额外内存分配也会严重的影响速度和缓存的性能。当一个子列表可用时，一个新的线程就会被立即启动去处

8、理它，并且这个线程不会与其他线程交换信息.当所有线程