计算机专业英语Chapter3课件.ppt

1、内容内容l正文lBalanced Tree Data Structures lQuicksort l阅读材料lLinked List lNew Algorithms for Maintaining All-Pairs Shortest Paths 1 Balanced Tree Data Structures lComputer sizes and power lSupercomputer and Mainframe lMinicomputer lWorkstation lPersonal computer Key Wordslred-black tree红黑树,是一种平衡树lbranchin

2、g factor分支因子lbranchinessn.分支性lasymptoticadj.趋近lworst case最差状况lsingle pass单遍，单次lanalogousadj.同样功能的lbinary tree二叉树linventoryn.目录、存货清单lterabyte1 Terabyte=1024 GBldisburse支付,支出NoteslFor example,a b-tree with a height of 2 and a branching factor of 1001 can store over one billion keys but requires at mos

3、t two disk accesses to search for any node.lIf t is this minimization factor,every node must have at least t-1 keys.Under certain circumstances,the root node is allowed to violate this property by having fewer than t-1 keys.例如，一个高度为2、分支因子为1001的树可以储存高达十亿个键，而最多只需要访问磁盘两次就可以访问到任意一个节点。如果t是最小因子,每个节点都必须有至少

4、t-1个键。在特定的环境下，根节点的键少于t-1并不违反这个属性。NoteslIf the node is not full prior to the insertion,no special action is required;however,if the node is full,the node must be split to make room for the new key.lSince each access to a node may correspond to a costly disk access,it is desirable to avoid the second

5、pass by ensuring that the parent node is never full.To accomplish this,the presented algorithm splits any full nodes encountered while descending the tree.如果结点在插入前不满，则不需要做特殊处理。但是，如果结点是满的，为了给新的键提供空间，就需要将结点拆分。由于每一次对结点的存取都可能导致高成本的磁盘存取，因此应该尽量使父结点永不满以避免第二次访问。为了达到这个目的，以上算法在向下遍历树结构时拆分所有已满的结点。2 Quicksort Ke

6、y Wordslsorting algorithm排序算法lquadraticadj.二次的ldivide and conquer strategy分而治之lpivotn.中心点lpartitionn.分割lpseudocoden.伪码lsequentiallyadv.连续地lauxiliaryadj.辅助的lnested call嵌套调用 Key Wordslrecurrencen.循环,递归ltheoremn.定理lyieldv.产生lflip a coinv.(为作出决定而)掷硬币linfinitesimallyadv.微不足道地lpermutationn.排列lelidv.修正lnot

7、-in-place不在原来的地方lvariantn.不同版本NoteslThe additional memory allocations required can also drastically impact speed and cache performance in practical implementations.lA new thread is started as soon as a sublist is available for it to work on and it does not communicate with other threads.When all thr

8、eads complete,the sort is done.在实现中，所需的额外内存分配也会严重的影响速度和缓存的性能。当一个子列表可用时，一个新的线程就会被立即启动去处理它，并且这个线程不会与其他线程交换信息.当所有线程都结束后，排序完成。Reading Material 1 Linked List Reading Material 1 Linked List Reading Material 2 New Algorithms for Maintaining All-Pairs Shortest Paths Exercises 1.For an ideal balanced tree wi

9、th n nodes in it,the height will be _.2.Unlike a binary-tree,each node of a b-tree may have a variable number of _ and _.3.A b-tree has a minimum number of allowable children for each node known as the _.4.For n1,the height of an n-key b-tree T with minimum degree of t will be no more than _.5.The _

10、 operation creates an empty b-tree by allocating a new root node that has no keys and is a leaf node.6.Quicksort sorts by employing a divide and conquer strategy to divide a _ into two _.7.The disadvantage of the simple version above is that it requires_ extra storage space,which is as bad as merges

11、ort.8.The version of quicksort with _ partitioning uses only constant additional space before making any recursive call.9.Once we know a worst-case O(n)selection algorithm is available,we can use it to find the ideal pivot(the median)at every step of quicksort,producing a _ with worst-case O(n log n)running time.