Contents
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Time Complexity. . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Basic Counts . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Solving Recurrence Equations . . . . . . . . 1
1.2.1 Master Theorem . . . . . . . . . . . . 1
1.3 Useful Math Equations. . . . . . . . . . . . . . . 1
2 Memory Complexity. . . . . . . . . . . . . . . . . . . . . . 3
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Memory for Data Type . . . . . . . 3
2.1.2 Example . . . . . . . . . . . . . . . . . . . 3
3 Basic Data Structures. . . . . . . . . . . . . . . . . . . . . 4
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Stack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2.1 Stack and Recursion . . . . . . . . . 4
3.2.2 Usage . . . . . . . . . . . . . . . . . . . . . 4
3.2.3 Applications . . . . . . . . . . . . . . . . 4
3.2.4 All nearest smaller values. . . . . 5
3.3 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.3.1 Math relations . . . . . . . . . . . . . . 5
3.3.2 Operations . . . . . . . . . . . . . . . . . 5
4 Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.1 Operations . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.1.1 Fundamentals . . . . . . . . . . . . . . . 6
4.1.2 Basic Operations . . . . . . . . . . . . 6
4.1.3 Combined Operations . . . . . . . . 6
4.2 Combinations . . . . . . . . . . . . . . . . . . . . . . 6
4.2.1 LRU . . . . . . . . . . . . . . . . . . . . . . 6
5 Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2 Operations . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2.1 Sink
(sift down). . . . . . . . . . . . . 8
5.2.2 Swim
(sift up) . . . . . . . . . . . . . . 8
5.2.3 Heapify . . . . . . . . . . . . . . . . . . . . 8
5.3 Implementation . . . . . . . . . . . . . . . . . . . . . 8
5.3.1 General . . . . . . . . . . . . . . . . . . . . 8
5.3.2 Python Heapq . . . . . . . . . . . . . . 9
5.3.3 Java Priority Queue . . . . . . . . . . 9
5.4 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.4.1 Heap of Linked Lists. . . . . . . . . 9
6 Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.1 Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . 10
6.1.1 Basic Operations . . . . . . . . . . . . 10
6.1.2 Morris Traversal . . . . . . . . . . . . 11
6.2 Binary Search Tree (BST) . . . . . . . . . . . . 13
6.2.1 Property . . . . . . . . . . . . . . . . . . . 13
6.2.2 Rank . . . . . . . . . . . . . . . . . . . . . . 13
6.2.3 Range search . . . . . . . . . . . . . . . 14
6.3 Binary Index Tree (BIT) . . . . . . . . . . . . . 15
6.3.1 Introduction . . . . . . . . . . . . . . . . 15
6.3.2 Implementation . . . . . . . . . . . . . 15
6.4 Segment Tree. . . . . . . . . . . . . . . . . . . . . . . 15
6.4.1 Introduction . . . . . . . . . . . . . . . . 15
6.4.2 Operations . . . . . . . . . . . . . . . . . 16
6.5 Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.5.1 Basic . . . . . . . . . . . . . . . . . . . . . . 17
6.5.2 Advanced . . . . . . . . . . . . . . . . . . 17
6.5.3 Extensions . . . . . . . . . . . . . . . . . 17
6.5.4 Applications . . . . . . . . . . . . . . . . 17
7 Balanced Search Tree . . . . . . . . . . . . . . . . . . . . . 19
7.1 2-3 Search Tree . . . . . . . . . . . . . . . . . . . . . 19
7.1.1 Insertion . . . . . . . . . . . . . . . . . . . 19
7.1.2 Splitting . . . . . . . . . . . . . . . . . . . 19
7.1.3 Properties . . . . . . . . . . . . . . . . . . 19
7.2 Red-Black Tree . . . . . . . . . . . . . . . . . . . . . 20
7.2.1 Properties . . . . . . . . . . . . . . . . . . 20
7.2.2 Operations . . . . . . . . . . . . . . . . . 20
7.3 B-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.3.1 Basics . . . . . . . . . . . . . . . . . . . . . 21
7.3.2 Operations . . . . . . . . . . . . . . . . . 21
7.4 AVL Tree . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7.5 Cartesian Tree . . . . . . . . . . . . . . . . . . . . . . 22
7.5.1 Basics . . . . . . . . . . . . . . . . . . . . . 22
7.5.2 Treap . . . . . . . . . . . . . . . . . . . . . . 22
8 Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 24
8.2 Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 24
8.2.1 Quick Sort . . . . . . . . . . . . . . . . . 24
8.2.2 Merge Sort . . . . . . . . . . . . . . . . . 25
8.2.3 Do something while merging . . 26
8.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 26
8.3.1 Stability . . . . . . . . . . . . . . . . . . . 26
8.3.2 Sorting Applications . . . . . . . . . 26
8.3.3 Considerations . . . . . . . . . . . . . . 26
8.3.4 Sorting Summary . . . . . . . . . . . 27
v
评论0
最新资源