文件名称：Data Structures Succinctly Part 2
文件大小：1.75MB
文件格式：PDF
更新时间：2016-11-03 22:42:18
Data Structures, algorithm
Data Structures Succinctly Part 2 Table of Contents The Story behind the Succinctly Series of Books ................................................................................... 9 Chapter 1 Skip Lists ................................................................................................................................. 11 Overview ................................................................................................................................................ 11 How it Works ........................................................................................................................................ 11 But There is a Problem ........................................................................................................................ 13 Code Samples ..................................................................................................................................... 15 SkipListNode Class ................................................................................................................................ 15 SkipList Class ........................................................................................................................................ 16 Add ......................................................................................................................................................... 17 Picking a Level ..................................................................................................................................... 17 Picking the Insertion Point ................................................................................................................... 19 Remove .................................................................................................................................................. 20 Contains ................................................................................................................................................. 21 Clear ....................................................................................................................................................... 23 CopyTo................................................................................................................................................... 23 IsReadOnly ............................................................................................................................................ 24 Count ...................................................................................................................................................... 24 GetEnumerator ...................................................................................................................................... 24 Common Variations ............................................................................................................................... 25 Array-Style Indexing............................................................................................................................. 25 Set behaviors ....................................................................................................................................... 26 Chapter 2 Hash Table .............................................................................................................................. 27 Hash Table Overview ............................................................................................................................. 27 Hashing Basics ...................................................................................................................................... 27 5 Overview .............................................................................................................................................. 27 Hashing Algorithms .............................................................................................................................. 29 Handling Collisions .............................................................................................................................. 33 HashTableNodePair Class..................................................................................................................... 34 HashTableArrayNode Class .................................................................................................................. 36 Add ....................................................................................................................................................... 36 Update ................................................................................................................................................. 37 TryGetValue ......................................................................................................................................... 38 Remove ................................................................................................................................................ 39 Clear .................................................................................................................................................... 40 Enumeration ......................................................................................................................................... 40 HashTableArray Class ........................................................................................................................... 42 Add ....................................................................................................................................................... 43 Update ................................................................................................................................................. 43 TryGetValue ......................................................................................................................................... 44 Remove ................................................................................................................................................ 44 GetIndex .............................................................................................................................................. 45 Clear .................................................................................................................................................... 45 Capacity ............................................................................................................................................... 46 Enumeration ......................................................................................................................................... 46 HashTable Class .................................................................................................................................... 48 Add ....................................................................................................................................................... 49 Indexing ............................................................................................................................................... 50 TryGetValue ......................................................................................................................................... 51 Remove ................................................................................................................................................ 51 ContainsKey ......................................................................................................................................... 52 ContainsValue ...................................................................................................................................... 52 6 Clear .................................................................................................................................................... 53 Count ................................................................................................................................................... 53 Enumeration ......................................................................................................................................... 54 Chapter 3 Heap and Priority Queue ....................................................................................................... 56 Overview ................................................................................................................................................ 56 Binary Tree as Array .............................................................................................................................. 57 Structural Overview.............................................................................................................................. 57 Navigating the Array like a Tree .......................................................................................................... 59 The Key Point ...................................................................................................................................... 60 Heap Class ............................................................................................................................................ 60 Add ......................................................................................................................................................... 61 RemoveMax ........................................................................................................................................... 65 Peek ....................................................................................................................................................... 69 Count ...................................................................................................................................................... 69 Clear ....................................................................................................................................................... 69 Priority Queue ........................................................................................................................................ 70 Priority Queue Class ............................................................................................................................ 70 Usage Example .................................................................................................................................... 71 Chapter 4 AVL Tree .................................................................................................................................. 73 Balanced Tree Overview........................................................................................................................ 73 What is Node Height? .......................................................................................................................... 73 Balancing Algorithms ............................................................................................................................. 75 Right Rotation ...................................................................................................................................... 75 Left Rotation ......................................................................................................................................... 77 Right-Left Rotation ............................................................................................................................... 78 Left-Right Rotation ............................................................................................................................... 80 Heaviness and Balance Factor ............................................................................................................ 81 7 AVLTreeNode Class .............................................................................................................................. 82 Balance ................................................................................................................................................ 83 Rotation Methods ................................................................................................................................. 86 AVLTree Class ....................................................................................................................................... 87 Add ....................................................................................................................................................... 88 Contains ............................................................................................................................................... 89 Remove ................................................................................................................................................ 90 GetEnumerator .................................................................................................................................... 93 Clear .................................................................................................................................................... 95 Count ................................................................................................................................................... 95 Chapter 5 B-tree ....................................................................................................................................... 96 Overview ................................................................................................................................................ 96 B-tree Structure ...................................................................................................................................... 96 Minimal Degree .................................................................................................................................... 97 Tree Height .......................................................................................................................................... 97 Searching the Tree .............................................................................................................................. 98 Putting it Together.............................................................................................................................. 100 Balancing Operations ........................................................................................................................... 100 Pushing Down .................................................................................................................................... 100 Rotating Values .................................................................................................................................. 102 Splitting Nodes ................................................................................................................................... 104 Adding Values ...................................................................................................................................... 105 Removing Values ................................................................................................................................. 107 B-tree Node .......................................................................................................................................... 108 BTreeNode Class............................................................................................................................... 108 Adding, Removing, and Updating Values .......................................................................................... 110 Splitting Node ..................................................................................................................................... 111 8 Pushing Down .................................................................................................................................... 113 Validation ........................................................................................................................................... 115 B-tree ................................................................................................................................................... 116 BTree Class ....................................................................................................................................... 116 Add ..................................................................................................................................................... 117 Remove .............................................................................................................................................. 118 Contains ............................................................................................................................................. 126 Clear .................................................................................................................................................. 127 Count ................................................................................................................................................. 127 CopyTo .............................................................................................................................................. 128 IsReadOnly ........................................................................................................................................ 128 GetEnumerator .................................................................................................................................. 129