16.3 Glossary¶
The following table lists important terms that appear in this book.
Table 16-1 Important Terms in Data Structures and Algorithms
| English |
|---|
| algorithm |
| data structure |
| code |
| file |
| function |
| method |
| variable |
| asymptotic complexity analysis |
| time complexity |
| space complexity |
| loop |
| iteration |
| recursion |
| tail recursion |
| recursion tree |
| big-\(O\) notation |
| asymptotic upper bound |
| sign-magnitude |
| 1’s complement |
| 2’s complement |
| array |
| index |
| linked list |
| linked list node, list node |
| head node |
| tail node |
| list |
| dynamic array |
| hard disk |
| random-access memory (RAM) |
| cache memory |
| cache miss |
| cache hit rate |
| stack |
| top of the stack |
| bottom of the stack |
| queue |
| double-ended queue |
| front of the queue |
| rear of the queue |
| hash table |
| hash set |
| bucket |
| hash function |
| hash collision |
| load factor |
| separate chaining |
| open addressing |
| linear probing |
| lazy deletion |
| binary tree |
| tree node |
| left-child node |
| right-child node |
| parent node |
| left subtree |
| right subtree |
| root node |
| leaf node |
| edge |
| level |
| degree |
| height |
| depth |
| perfect binary tree |
| complete binary tree |
| full binary tree |
| balanced binary tree |
| binary search tree |
| AVL tree |
| red-black tree |
| level-order traversal |
| breadth-first traversal |
| depth-first traversal |
| binary search tree |
| balanced binary search tree |
| balance factor |
| heap |
| max heap |
| min heap |
| priority queue |
| heapify |
| top-\(k\) problem |
| graph |
| vertex |
| undirected graph |
| directed graph |
| connected graph |
| disconnected graph |
| weighted graph |
| adjacency |
| path |
| in-degree |
| out-degree |
| adjacency matrix |
| adjacency list |
| breadth-first search |
| depth-first search |
| binary search |
| searching algorithm |
| sorting algorithm |
| selection sort |
| bubble sort |
| insertion sort |
| quick sort |
| merge sort |
| heap sort |
| bucket sort |
| counting sort |
| radix sort |
| divide and conquer |
| hanota problem |
| backtracking algorithm |
| constraint |
| solution |
| state |
| pruning |
| permutations problem |
| subset-sum problem |
| \(n\)-queens problem |
| dynamic programming |
| initial state |
| state-transition equation |
| knapsack problem |
| edit distance problem |
| greedy algorithm |