[Mark_A._Weiss]_Data_Structures_and_Algorithm_Anal(BookZZ.org)

632 Index resize function, 87, 89 skip lists, 499–501 divide and conquer strategy for, Return passing, 27, 37 splay trees, 551–554 475–478 Reverse Polish notation, 105 Runs in external sorting, 337–341 Right-justifying paragraphs, 524 rvalue, 23–24, 27–29, 31 lower bounds 325-328 Rivest, R. L., 377, 529 rvalue reference, 23–24, 27–28 priority queues for, 258–259 Roberts, F. S., 49 quicksorts for, 321–322 Rodler, F. F., 243 S references for, 527 Rohnert, H., 242 Selection replacement in external Roots Sack, J. R., 288, 289 Saini, A., 49 sorting, 340–341 decision trees, 323 Saks, M. E., 377 Self-adjusting structures leftist heaps, 262–263 Salesman problem, 435–436 top-down splay trees, 560 Samet, H., 614 binary search trees, 144 trees, 121–122 Samples of medians, 475–477 disjoint sets. See Disjoint sets rotate function, 570, 574 Sanders, P., 243, 614 lists, 119 rotateWithLeftChild function, 154 Santoro, N., 288 path compression, 374 rotateWithRightChild function, Satisfiability problem, 436 skew heaps, 269–270 Saxe, J. B., 528 splay trees. See Splay trees 154 Saxena, N., 528 Sen, S., 191 Rotation operations Schaeffer, J., 531 Sentinel nodes, 92 Schaffer, R., 349 Separate chaining for hash tables, AVL trees, 145–147 Scheduling problem, 450–453 double, 149–158 Schellbach, U., 243 196–197, 200, 211 single, 147–148 Schonhage, A., 377 Separate compilation of class Schrage, L., 531 red-black trees, 567–568 Schwab, B., 613 templates, 42–44, 615–616 splay trees Scope resolution operator, 18 explicit instantiation, 616–618 Scroggs, R. E., 191 for header information, 616 limitations of, 159–160 Search trees Separation of interface from running times, 551–554 top-down, 559–561 binary. See Binary search trees implementation, 16–18 zig-zag, 160–168 k-d trees, 596–600, 611 Sequences of random numbers, Running times, 57–70 red-black. See Red-black trees in algorithm selection, 55, splay trees. See Splay trees 499 treaps, 576–579 Series, 4–5 468–470 Searches. See also Find operations set class, 121 amortized, 158 binary, 65–67 Sets definitions for, 51–52 breadth-first, 389–391 disjoint sets, 356–357 depth-first. See Depth-first disjoint. See Disjoint sets disk I/O assumptions in, implementation of, 175–176 searches operations for, 173–174 168–169 Secondary clustering in hash setValue function, 618 divide and conquer algorithms, Shallow copies, 32 tables, 207 Shamos, M. I., 531 467–469 Sedgewick, R., 191, 289, 348, 349, Shapiro, H. D., 447, 614 examples, 58 Sharir, M., 376, 377, 445, 447 factors in, 54–57 613, 614 Shell, Donald L., 296–397, 349 general rules, 58–60 Seeds for random numbers, 496 Shellsort logarithmic, 66–70 Segev, G., 242 description, 296–298 maximum subsequence sum Seidel, R., 377, 613 references for, 347 Selection (lower bound), 325–328 worst-case analysis of, 297–300 problem, 60–66 Selection problem shellsort function, 297 mergesorts, 305–308 Shing, M. R., 529 overestimating, 70 alternate algorithms for, 1–2 shortest function, 526 quicksorts, 309, 318–321 Shortest-path algorithms, 386–406 randomized algorithms, acyclic graphs, 400–404 all-pairs, 404, 493 494–495 rates of growth, 52–54 Shellsorts, 298–300

Index 633 Dijkstra’s algorithm, 391–400, bucket sorts, 331–336 hash tables in, 210–212 541 Counting radix, 332–336 insertion sort implementation, external, 336–341 example, 404–406 heapsorts, 300–304 293–294 negative edge costs, 399–400 insertion sorts, 292–295 maps in, 174–175, 210–212 single source, 385–387 lower bounds for, 295–296, priority queues in, 282–283 unweighted, 387–391 sets in, 173–174 Shrairman, R., 289 323–325 sorting algorithms in, 291–292 Siblings in trees, 122 mergesorts, 304–309 Stasevich, G. V., 349 Sieve of Eratosthenes, 74 quicksort. See Quicksort Stasko, J. T., 614 Signatures for member Radix sort, 331–336 States in decision trees, 358 references for, 347–349 std::move, 29–30 functions, 18 Shellsort, 296–300 std::swap, 29–30 Simon, I., 377 topological, 382–385 Stege, U., 613 Simple paths, 379 Sources in network flow, 406 Steiglitz, K., 447 Simulation, priority queues for, Spanning trees, minimum, Stephenson, C. J., 614 Stirling’s formula, 344, 347 259–260 412–413, 522 STL. See Standard Template Single rotation operations Kruskal’s algorithm, 417–419 Prim’s algorithm, 414–417 Library (STL) in AVL trees, 147–149 references for, 444 Strassen, V., 531 limitations of, 159–161 Sparse graphs Strassen’s algorithm, 481–482, Single source algorithm for adjacency lists for, 381 with Dijkstra’s algorithm, 404, 486, 520, 527, 530 shortest-path problem, 386, strcpy function, 36 491 491 string class, 18–20, 36 Sinks in network flow, 406 Special cases in recursion, 9 Strings, C-style, 33–36 size function and size Spelling checkers, 237, 240 Strip areas in closest points arrays, 36, 113–114 Spencer, T. H., 446 binomial queues, 271 Spirakis, P., 243 problem, 471 containers, 81 splay function, 564 strlen function, 36 directory structures, 125–126 Splay trees, 158–166 Strong, H. R., 243 hash tables, 193–194, 204 Strong components, 431–432 input, in running time, 55–57 amortized analysis, 551–555 Strongly connected graphs, 380 lists, 93–94 vs. single rotations, 158–159 Strothotte, T., 288, 289, 290 maps, 174 top-down, 559–566 Stroustrop, B., 49 sets, 173 zig-zag rotations in, 160–166 struct keyword for lists, 85 vectors, 19–20, 87, 90–91 SplayTree class, 561 Suboptimal solutions, 410, 449 size_t, 197–199, 205, 212, Square class, 39–41 Substitution problem, maps for, 220–221, 226 stable_sort function, 292 Skew heaps, 269–271 Stable sorting algorithms, 348 176–181 amortized analysis of, 539–541 Stack frames, 111 Subtraction of pointers, 323 Skiena, S. S., 531 Stacks Successor positions in games, 511 Skip lists, 500–503 for balancing symbols, 104–105 Suel, T., 349 Slack time in acyclic graphs, 403 for function calls, 110–112 Suffix arrays, 579–596 Sleator, D. D., 191, 289, 558, 613, implementation, 104 Suffix trees, 579–596 614 for infix to postfix conversions, Sums Smart union algorithms, 357–359 Smith, H. F., 183 108–111 maximum subsequence sum Smith, W. D., 531 model of, 103 problem, 55–57, 60–66 Smolka, S. A., 529 for postfix expressions, 105–107 Smyth, W. F., 614 for topological sorts, 384 telescoping, 307, 320 sort function, 292 Stale iterators, 117–118 Sutphen, S., 531 Sorting, 291–341 Standard Template Library (STL) swapChildren function, 265 algorithm comparison, 344 containers in, 80–81 Symbol tables, 236 Symbols in header files, 15–16

634 Index Symmetric relations in disjoint Top-down red-black trees, top-down, 559–566 sets, 351 568–570 zig-zag rotations in, 160–166 suffix trees, 579–596 System clocks for random Top-down splay trees, 559–566 threaded, 176 numbers, 496 Top of stacks, 103 treaps, 576–579 top operations traversing, 166–168 Szemeredi, E., 243 weight-balanced, 456 priority queues, 282 Tries, 454–459 T stacks, 103 Tsur, S., 190 Topological sorts, 382–385 Tucker, A., 49 Table size in hash tables, 193–194, topSort function, 384–386 Turing machines, 436 204 Traffic flow, graphs for, 380 turnpike function, 508 Traffic problems, 450 Turnpike reconstruction problems, Tables Transitive relations, 351 vs. recursion, 483–485 Transposition tables, 237, 514 506–511 symbol, 237 Traveling salesman problem, Turpin, A., 614 transposition, 237, 514 2-3 trees, 182, 190 435–436, 445, 506, 522 2-d heaps, 610 Tail nodes, 92 Traversing 2-d trees, 599–601 Tail recursion, 112 Two-dimensional range queries, Takaoka, T., 529, 531 binary trees, 166–167 Tan, Z., 531 directories, 123–126 596–597 Tapes, sorting on, 291, 336–341 Treap class, 576–579 Two-parameter operations Tardos, E., 446 TreapNode structure, 577–579 Tarjan, R. E., 191, 242, 289, 375, Treaps, 576–579 insertion sorts, 173–174 Trees, 121–182 sets, 173–174 376, 377, 378, 445, 446, 2-3, 182, 190 Two-pass algorithms 447, 448, 529, 558, 613, 2-d, 599–600 Huffman algorithm, 459 614 AVL, 144–158 pairing heap merging, 604, Telescoping sums, 308, 321 Templates, 36–44 double rotation, 141–158 606–608 class, 132 single rotation, 139–141 Type conversions implicit, 37 Comparable and Object, 39–41 B-trees, 168–173 compilation of, 44, 615–616 binary, 126–131 U explicit instantiation, Cartesian, 612 616–618 decision, 323–328 Ukkonen, E., 614 function, 37–38 definitions, 121–122 Ullman, J. D., 76, 190, 376, 377, Terminal positions in games, 511 for disjoint sets, 363 Tesman, B., 49 game, 514 445, 529 Tests, primality, 503–506 implementations of, 122–123 Unary minus operator, 128 Theta notation, 51–54 isomorphic, 188 Undecidable problems, 433 Thomo, A., 613 k-d, 596–601 Undirected graphs, 379 Thornton, C., 191 minimum spanning, 413–414, Thorup, M., 243 biconnected, 421–425 Threaded trees, 176 522 depth-first searches, 420–421 Threads, 188 Kruskal’s algorithm, 417–419 Uninitialized pointers, 22 Three-parameter insertion sort, Prim’s algorithm, 414–417 Union algorithms, 357–359 294 parse, 182 Union-by-height approach, Thurston, W. P., 191 quad, 611 Tic-tac-toe game, 511–513, 517, red-black, 566–576 358–359 518, 522, 526 bottom-up insertion, 567–568 Union-by-rank approach, 361, Ticks for event simulation, 259 top-down deletion, 570–576 Time bound proof for Fibonacci top-down insertion, 568–570 363–365, 368 heaps, 548–551 splay, 144, 158 Union-by-size approach, 357, amortized analysis, 551–555 vs. single rotations, 158–160 359 Union/find algorithm analysis, 362–372 for disjoint sets, 392

Index 635 union operations Vertices Worst-case analysis, 55 disjoint sets, 352–353 graph, 379–380 quicksorts, 318–319 Kruskal’s algorithm, 417 topological sorts for, 379–380 randomized algorithms, 494–495 unionSets function, 355, 356, Vishkin, U., 530 Shellsort, 297–300 359 Visibility in classes, 12 union-by-rank approach, Vitanyi, P., 349 361–371 Universal hashing, 230–233 Vitter, J. S., 244, 614 unordered_map, 181, 210–212, 405 Vöcking, B., 243 write function unordered_set, 210–212 Voronoi diagrams, 523 in IntCell, 12–13, 19 unweighted function, 390–391 Vuillemin, J., 290, 558, 614 in MemoryCell, 38 Unweighted path length, W X 386 Upfal, E., 242 Wagner, R. A., 531 Xia, B., 531 Upper bounds of function Wayne, K., 614 Weakly connected graphs, 380 Y growth, 52 Wegman, M. N., 242, 244 Upton, C., 613 Weidling, C., 243 Yao, A. C., 191, 244, 349, 378, weight-balanced trees, 190, 613 448, 531 V Weighted path lengths, 386 weightedNegative function, 401 Yao, F. F., 531 Vallner, S., 290 Weights Values Z graph edges, 379–381 parameter passing by, 23 in Huffman algorithm, 455–456 Zaman, A., 530 returning, 25 Wein, J., 528, 614 Zero-slack edges, 404 van Emde Boas, P., 290 Weiner, P., 614 Zhang, Z., 531 van Kreveld, M. J., 378 Weiss, M. A., 49, 289, 349, 613 Zig operations van Leeuwen, J., 377, 614 Westbrook, J., 378 van Vleit, A., 530 Wieder, U., 243 for red-black trees, 568 Variables Williams, J. W. J., 290, 349, for splay trees, 551–555, reference, 27 Winograd, S., 529 stacks for, 110 witness function, 504–505 559–560, 562 Vassilevska-Williams, V., 531 Witten, I. H., 528 Zig-zag operations vector class, 19–21, 36, Wong, C. K., 614 Wong, J. K., 447 for red-black trees, 568 87–90 Wood, D., 190 for splay trees, 160–166, Vectors Word puzzles, 1 hash tables for, 237 551–555, 559–566 for adjacency lists, 381 word ladders, 443 Zig-zig operations implementation, 28, 86–91 word substitution problem, iterators for, 75–79 for red-black trees, 607 for stacks, 104 184–189 for splay trees, 551–555, in STL, 80–86 Vertex class, 381, 398 559–562 Vertex cover problem, 444 Zijlstra, E., 290 Ziv, J., 531 Ziv-Lempel encoding, 527 Ziviana, N., 190 Zwick, U., 348, 529, 531