datastucture 学习笔记。 advanced-data-structure边译边学 Contents Articles Introduction 1\x3cbr\x3eData structure 1\x3cbr\x3eLinked data structure 3\x3cbr\x3eSuccinct data structure 6\x3cbr\x3eImplicit data structure 8\x3cbr\x3eCompressed data structure 9\x3cbr\x3eSearch data structure 10\x3cbr\x3ePersistent data structure 11\x3cbr\x3eConcurrent data structure 18\x3cbr\x3eAbstract data types 21\x3cbr\x3eAbstract data type 21\x3cbr\x3eList 29\x3cbr\x3eStack 32\x3cbr\x3eQueue 61\x3cbr\x3eDeque 63\x3cbr\x3ePriority queue 66\x3cbr\x3eMap 70\x3cbr\x3eBidirectional map \x3cbr\x3eMultimap 74\x3cbr\x3eSet 75\x3cbr\x3eTree 80\x3cbr\x3eArrays 85\x3cbr\x3eArray data structure 85\x3cbr\x3eRow-major order 91\x3cbr\x3eDope vector 93\x3cbr\x3eIliffe vector 94\x3cbr\x3eDynamic array 95\x3cbr\x3eHashed array tree 98\x3cbr\x3eGap buffer 99\x3cbr\x3eCircular buffer 101\x3cbr\x3eSparse array 111\x3cbr\x3eBit array 112\x3cbr\x3eBitboard 117\x3cbr\x3eParallel array 121\x3cbr\x3eLookup table 123\x3cbr\x3eLists 129\x3cbr\x3eLinked list 129\x3cbr\x3eXOR linked list 145\x3cbr\x3eUnrolled linked list 147\x3cbr\x3eVList 149\x3cbr\x3eSkip list 151\x3cbr\x3eSelf-organizing list 157\x3cbr\x3eBinary trees 162\x3cbr\x3eBinary tree 162\x3cbr\x3eBinary search tree 170\x3cbr\x3eSelf-balancing binary search tree 180\x3cbr\x3eTree rotation \x3cbr\x3eWeight-balanced tree 185\x3cbr\x3eThreaded binary tree 186\x3cbr\x3eAVL tree 191\x3cbr\x3eRed-black tree 195\x3cbr\x3eAA tree 210\x3cbr\x3eScapegoat tree 215\x3cbr\x3eSplay tree 219\x3cbr\x3eT-tree 234\x3cbr\x3eRope 237\x3cbr\x3eTop Trees 242\x3cbr\x3eTango Trees 246\x3cbr\x3eVan Emde Boas tree 268\x3cbr\x3eCartesian tree 272\x3cbr\x3eTreap 277\x3cbr\x3eB-trees 281\x3cbr\x3eB-tree 281\x3cbr\x3eB+ tree 292\x3cbr\x3eDancing tree 297\x3cbr\x3e2-3 tree 2982-3-4 tree 299\x3cbr\x3eQueaps 301\x3cbr\x3eFusion tree 305\x3cbr\x3eBx-tree 309\x3cbr\x3eHeaps 312\x3cbr\x3eHeap 312\x3cbr\x3eBinary heap 315\x3cbr\x3eBinomial heap 321\x3cbr\x3eFibonacci heap 326\x3cbr\x3e2-3 heap 331\x3cbr\x3ePairing heap 331\x3cbr\x3eBeap 334\x3cbr\x3eLeftist tree 335\x3cbr\x3eSkew heap 338\x3cbr\x3eSoft heap 341\x3cbr\x3ed-ary heap 343\x3cbr\x3eTries 346\x3cbr\x3eTrie 346\x3cbr\x3eRadix tree 353\x3cbr\x3eSuffix tree 358\x3cbr\x3eSuffix array 363\x3cbr\x3eCompressed suffix array 367\x3cbr\x3eFM-index 368\x3cbr\x3eGeneralised suffix tree 371\x3cbr\x3eB-trie 372\x3cbr\x3eJudy array 372\x3cbr\x3eDirected acyclic word graph 374\x3cbr\x3eMultiway trees 376\x3cbr\x3eTernary search tree 376\x3cbr\x3eAnd–or tree 379\x3cbr\x3e(a,b)-tree 380\x3cbr\x3eLink/cut tree 381\x3cbr\x3eSPQR tree 381\x3cbr\x3eSpaghetti stack 384\x3cbr\x3eDisjoint-set data structure 385Space-partitioning trees 389\x3cbr\x3eSpace partitioning 389\x3cbr\x3eBinary space partitioning 390\x3cbr\x3eSegment tree 395\x3cbr\x3eInterval tree 399\x3cbr\x3eRange tree 404\x3cbr\x3eBin 406\x3cbr\x3ek-d tree 408\x3cbr\x3eImplicit k-d tree 416\x3cbr\x3emin/max kd-tree 419\x3cbr\x3eAdaptive k-d tree 420\x3cbr\x3eQuadtree 421\x3cbr\x3eOctree 427\x3cbr\x3eLinear octrees 429\x3cbr\x3eZ-order 429\x3cbr\x3eUB-tree 434\x3cbr\x3eR-tree 435\x3cbr\x3eR+ tree 441\x3cbr\x3eR* tree 442\x3cbr\x3eHilbert R-tree 445\x3cbr\x3eX-tree 452\x3cbr\x3eMetric tree 452\x3cbr\x3evP-tree 453\x3cbr\x3eBK-tree 454\x3cbr\x3eHashes 455\x3cbr\x3eHash table 455\x3cbr\x3eHash function 468\x3cbr\x3eOpen addressing 476\x3cbr\x3eLazy deletion 479\x3cbr\x3eLinear probing 479\x3cbr\x3eQuadratic probing 480\x3cbr\x3eDouble hashing 484\x3cbr\x3eCuckoo hashing 486\x3cbr\x3eCoalesced hashing 491\x3cbr\x3ePerfect hash function 494\x3cbr\x3eUniversal hashing 496Linear hashing 501\x3cbr\x3eExtendible hashing 502\x3cbr\x3e2-choice hashing 508\x3cbr\x3ePearson hashing 508\x3cbr\x3eFowler–Noll–Vo hash function 509\x3cbr\x3eBitstate hashing 511\x3cbr\x3eBloom filter 512\x3cbr\x3eLocality preserving hashing 523\x3cbr\x3eMorton number 524\x3cbr\x3eZobrist hashing 529\x3cbr\x3eRolling hash 530\x3cbr\x3eHash list 531\x3cbr\x3eHash tree 532\x3cbr\x3ePrefix hash tree 534\x3cbr\x3eHash trie 535\x3cbr\x3eHash array mapped trie 535\x3cbr\x3eDistributed hash table 536\x3cbr\x3eConsistent hashing 542\x3cbr\x3eStable hashing 544\x3cbr\x3eKoorde 544\x3cbr\x3eGraphs 547\x3cbr\x3eGraph 547\x3cbr\x3eAdjacency list 549\x3cbr\x3eAdjacency matrix 551\x3cbr\x3eAnd-inverter graph 554\x3cbr\x3eBinary decision diagram 556\x3cbr\x3eBinary moment diagram 560\x3cbr\x3eZero-suppressed decision diagram 562\x3cbr\x3ePropositional directed acyclic graph 563\x3cbr\x3eGraph-structured stack 564\x3cbr\x3eScene graph 565\x3cbr\x3eAppendix 570\x3cbr\x3eBig O notation 570\x3cbr\x3eAmortized analysis 581\x3cbr\x3eLocality of reference 582\x3cbr\x3eStandard Template Library 585References\x3cbr\x3eArticle Sources and Contributors 596\x3cbr\x3eImage Sources, Licenses and Contributors 605\x3cbr\x3eArticle Licenses\x3cbr\x3eLicense 610