[CS] Advanced Data Structure.pdf

《[CS] Advanced Data Structure.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ADVANCEDDATASTRUCTURESPETERBRASSVERSIONOF29.10.2007LASTPUBLICPRE-DELIVERYVERSIONContents0.Preface......................................10.1BasicConcepts..............................30.2CodeExamples.............................51.ElementaryStructures.............................71

2、.1Stack....................................71.2Queue...................................141.3Double-EndedQueue..........................221.4DynamicalAllocationofNodes....................221.5ShadowCopiesofArray-BasedStructures.............242.SearchTrees...........................

3、........292.1TwoModelsofSearchTrees.....................292.2GeneralPropertiesandTransformations..............322.3HeightofaSearchTree........................352.4BasicFind,Insert,andDelete....................362.5ReturningfromLeaftoRoot.....................402.6DealingwithNonuniq

4、ueKeys....................422.7QueriesfortheKeysinanInterval.................422.8BuildingOptimalSearchTrees....................442.9ConvertingTreesintoLists......................512.10RemovingaTree............................523.BalancedSearchTrees.............................533

5、.1Height-BalancedTrees.........................533.2Weight-BalancedTrees.........................633.3(a,b)-andB-Trees...........................733.4Red-BlackTreesandTreesofAlmostOptimalHeight.....863.5Top-DownRebalancingforRed-BlackTrees............98iiTableofContents3.6Treeswit

6、hConstantUpdateTimeataKnownLocation....1083.7FingerTreesandLevelLinking...................1093.8TreeswithPartialRebuilding:AmortizedAnalysis.......1143.9SplayTrees:AdaptiveDatastructures...............1173.10SkipLists:RandomizedDataStructures..............1283.11JoiningandSplittin

7、gBalancedSearchTrees...........1354.TreeStructuresforSetsofIntervals.....................1414.1IntervalTrees..............................1414.2SegmentTrees..............................1464.3TreesfortheUnionofIntervals...................1534.4TreesforSumsofWeightedIntervals......

8、..........1594.5TreesforInterval-