Index
Numbers
2-3 trees
2-3-4 trees
advantages/disadvantages, 5
defined, 401–403
insertion, 404–405
node splits, 405–406, 407–408
organization of, 403–404
red-black trees and, 508–510
operational equivalence, 510–514
transformation between, 509–510
root splits, 406–407
searching, 404
speed of, 431
storage requirements, 432
terminology, 403
Tree234 class, 415
Tree234 Visualization tool, 408–411
A
abstract data types. See ADTs (abstract data types)
abstraction, described, 190–191
adjacency, defined, 707
adjacency lists
adjacency matrix
ADT lists, 191
ADTs (abstract data types)
AdvancedSorting Visualization tool
algorithms
defined, 1
invariants, 82
purpose of, 40–47
recipe analogy, 1–3
speed of
Big O notation, 65–68
general-purpose data structures, 819–820, 824
sorting algorithms, 828
special-ordering data structures, 826
allocation of arrays, 39
all-pairs shortest-path problem, 796–798
altering data structures during iteration, 216–217
anagrams, described, 239–242
analyzing the problem, 814–818
amount of data, 815–816
frequency of operations, 816–817
software maintenance responsibilities, 817–818
types of data, 814–815
arguments, defined, 20
arithmetic expressions, parsing
described, 132–133
evaluating postfix expressions, 148–151
Infix Calculator tool, 142–148
postfix notation, 133–134
translating infix to postfix, 134–142
Array class
accessing elements, 38–39
bubble sorts, 81–82
creating arrays, 37–38
deletion, 42
encapsulation, 42–43
example of, 39–42
improved example of, 43–47
initialization, 39
insertion, 42
insertion sorts, 90
searches, 42
selection sorts, 85–86
traversal, 42
Array Visualization tool, 30–37
deletion, 34–35, 37
duplicates, 35–37
insertion, 33
searches, 31–33
speed of algorithms, 37
traversal, 35
arrays. See also hash tables; hashing
advantages/disadvantages, 5, 69, 820–821
Array class
accessing elements, 38–39
creating, 37–38
deletion, 42
encapsulation, 42–43
example of, 39–42
improved example of, 43–47
initialization, 39
insertion, 42
searches, 42
traversal, 42
Array Visualization tool, 30–37
deletion, 34–35, 37
duplicates, 35–37
insertion, 33
searches, 31–33
speed of algorithms, 37
traversal, 35
binary search trees as
insertion, speed of, 66
linked lists vs.164
lists as, 37
Ordered Array Visualization tool, 47–51
OrderedArray class
OrderedRecordArray class, 61–65
reusing in heapsort, 688–691
as sequences, 13–15
sorting. See sorting
two-dimensional
use case comparison with stacks/queues, 103–104
arrival ordering, defined, 116–117
ASCII codes, 386
assignment statements, multivalued assignment in Python, 17–18
attributes
defined, 7
Python name mangling, 44
AVL trees
AVLtree class
AVLTree Visualization tool, 470
crossover subtrees in rotations, 478–479
defined, 463, 469–471
speed of, 484–485
AVLtree class
AVLTree Visualization tool, 470
B
balanced trees. See also AVL trees; red-black trees
base case, defined, 233
best case, defined, 266
Big O notation, 65–68
2–3 trees, 438
2–3-4 trees, 431–432
AVL trees, 484–485
binary search trees, 350, 375–377
binary searches, 67
bubble sorts, 82
comparison of sorting methods, 96–97
constants in, 67–68
counting sorts, 324
degenerates, 463–464
exact point matches, 622–623
general-purpose data structures, 824
graphs, 798
hashing, 581
heaps, 683–684
heapsort, 693
insertion in unordered arrays, 66
insertion sorts, 91
K highest, 696–700
linear searches, 66–67
linked lists, 183–184
mergesorts, 264–267, 456
ordered lists, 198
partitioning algorithm, 301–302
priority queues, 132
quadtrees
exact matches, 645
insertion, 644
nearest matches, 655
queues, 125
quicksorts, 318–320
radix sorts, 322
recursion, 236
red-black trees, 508
selection sorts, 86–87
Shellsorts, 294
sorting algorithms, 828
spatial data searches, 656–658
special-ordering data structures, 826
stacks, 116
Timsorts, 327
topological sorting, 751
Binary Search Tree Visualization tool, 341–344
deleting double child nodes, 374
deleting leaf nodes, 367
deleting single child nodes, 368–369
finding nodes, 346–348
inserting nodes, 351–352
traversal with, 361–363
binary search trees. See also AVL trees; nodes; red-black trees
as arrays
Binary Search Tree Visualization tool, 341–344
deleting double child nodes, 374
deleting leaf nodes, 367
deleting single child nodes, 368–369
finding nodes, 346–348
inserting nodes, 351–352
traversal with, 361–363
BinarySearchTree class, 344
defined, 340
duplicate keys in, 381–382
hierarchical file system analogy, 340–341
minimum/maximum key values, 365–366
printing, 379–381
separate chaining with, 585
speed of, 350, 375–377
when to use, 822
binary searches, 48–51
duplicates, 51
Guess-a-Number game example, 48–49
logarithms in, 58–60
Ordered Array Visualization tool, 49–51
OrderedArray class
recursion in, 242–244
speed of, 67
binary trees. See also binary search trees
advantages/disadvantages, 5
balanced/unbalanced
defined, 337, 339–340
heaps as, 666–667, 684–685
Huffman trees
representing arithmetic expressions, 363–365
BinarySearchTree class, 344
black height
blocks per node in B-trees, 444–445
bottom-up insertion, 486–487
bounding boxes of query circles, 603
Bounds class, 605–606
bounds completely within other bounds, 610–611
Cartesian coordinates, 603–604
CircleBounds subclass, 607–609
geographic coordinates, 604–605
intersection of bounding boxes, 609–610
intersection with grid cells, 628–629
within layers, 625–628
Bounds class, 605–606
branches, defined, 338
breadth-first traversal
B-trees
bubble sorts, 77–82
in Array class, 81–82
comparison of sorting methods, 96–97
described, 77–79
invariants, 82
Simple Sorting Visualization tool, 79–81
speed of, 82
buckets, defined, 569
buffers, defined, 442
bytecode, defined, 8
C
Cartesian coordinates
cells, defined, 38
character codes, 386–388
children of tree nodes
defined, 338
double child nodes, deleting, 370–375
null children in red-black trees, 495–496
single child nodes, deleting, 367–370
CircleBounds subclass, 607–609
circles. See query circles
circular lists, 209–210
circular queues, defined, 118
class attributes, defined, 25
classes, defined, 23
close matches. See nearest matches
clustering in hash tables
with HashTableOpenAddressing Visualization tool, 540–543
primary and secondary clustering, 558–559
collisions
combinations, recursion and, 278–280
comments in Python, described, 12
complex numbers, defined, 26
compressing data. See Huffman code
computational complexity, defined, 68
concatenating sequences, 15
conditional expressions, defined, 20
connected graphs, defined, 708
connectivity in directed graphs, 751
constants in Big O notation, 67–68
counting sort, 323–324
crossover subtrees
cutoff points, defined, 315
cycles
D
data compression. See Huffman code
data organizations
defined, 1
recipe analogy, 1–3
data structures. See also types of specific data structures
data types
databases
data structures vs.7
defined, 6
datasets distributed in cloud, defined, 438
decoding with Huffman trees, 388–389
degenerate trees, defined, 463–464
deletion. See also removal
delimiter matching example for stacks, 113–116
dependency relationships example (topological sorting), 739
depth-first traversal
deques
descendants, defined, 339
dictionary example (hashing), 527–530
Dijkstra’s algorithm
implementation, 791–792
rail travel example, 782–788
WeightedGraph Visualization tool, 788–791
directed graphs
distance between points
Cartesian coordinates, 599
geographic coordinates, 599–601
query circles, 601–603
divide-and-conquer algorithms
double child nodes, deleting, 370–375
double hashing, 559–565
double-ended lists, 177–183
doubly linked lists, 198–201
for deques, 208
insertion/deletion at ends, 201–204
insertion/deletion in middle, 204–208
duplicate keys in binary search trees, 381–382
duplicates
in arrays
Array Visualization tool, 35–37
Ordered Array Visualization tool, 51
in hash tables
with HashTableChaining Visualization tool, 568
with HashTableOpenAddressing Visualization tool, 542
dynamic typing, described, 12–13
E
edges
efficiency. See speed
elements (of lists)
eliminating recursion, 267
encapsulation, defined, 42–43
encoding
enumerating sequences, 15–17
error handling in stacks, 111–112
errors. See exceptions
Euclidean distance, defined, 599
Euler, Leonhard, 709
evaluating postfix expressions, 148–151
exact matches
exceptions
external storage
accessing, 439–442
B-trees
choosing what to use, 829–831
defined, 438
file indexes
sequential ordering, 442–443
sorting with mergesort, 453–456
extreme values, finding
F
factorials, described, 237–238
fencepost loops, defined, 145
Fibonacci sequence, 218–222
fields, defined, 7
file indexes
files, defined, 438
filled sequences in hash tables, 540–542
find() method, binary searches with, 52–53
finding. See also searching
extreme values in heaps, 695–700
minimum/maximum key values, 365–366
nodes
with Binary Search Tree Visualization tool, 346–348
with BinarySearchTree class, 348–349
successors, 372–373
finishing iteration
exception handling, 213–215
markers/sentinel values, 213
termination tests, 213
Floyd, Robert, 798
Floyd-Warshall algorithm, 798
folding, defined, 580–581
folds, defined, 531
foundational data structures, when to use, 818–824
functions in Python, described, 19–20
fusion
G
game simulation with depth-first traversal, 727
gap sequences
general-purpose data structures, when to use, 818–824
generators
for 2–3-4 tree traversal, 421–423
for adjacent vertex traversal, 724–727
described, 218–222
doubleHashProbe(), 559–565
for graph traversal, 731–733
for grid offsets, 629–630
for grid traversal, 623–624
for hash table traversal, 553–554
for heap traversal, 682–683
linearProbe(), 552
for point traversal, 615
quadraticProbe(), 554–559
for quadtree traversal, 645–646
in Timsorts, 326
for tree traversal, 356–361
geographic coordinates
bounding boxes of query circles, 604–605
defined, 598
distance between, 599–601
Graph class, 715–718
breadth-first traversal, 731–733
depth-first traversal, 724–727
minimum spanning trees in, 735–739
topological sorting in, 746–747
Graph Visualization tool
breadth-first traversal, 731
depth-first traversal, 722–723
directed graphs in, 741–742
minimum spanning trees in, 733
topological sorting algorithm, 742
graphs. See also topological sorting; weighted graphs
adding vertices/edges, 713–716
advantages/disadvantages, 5
defined, 337
directed graphs
Graph class, 715–718
history of, 709
intractable problems
defined, 798
Hamiltonian paths/cycles, 800–802
Knight’s Tour, 798
Traveling Salesperson, 799–800
minimum spanning trees
modeling
purpose of, 706
speed of algorithms, 798
terminology, 707–709
traversal, 718–719
when to use, 828–829
great circle, defined, 599–600
Grid class, 619–620
grids, 617
deleting points, 623
exact matches, 621–623
Grid class instances, 619–620
implementation in Python, 618–619
inserting points, 620–621
intersection with query circles, 628–629
nearest matches, 624–625, 630–633
neighboring cell sequence, 629–630
query circles within layers, 625–628
traversing points, 623–624
when to use, 828
growing hash tables
Guess-a-Number game example, 48–49
H
Hamiltonian paths/cycles intractable problem, 800–802
hash addresses, defined, 531
hash functions
hash tables
adjacency matrix as, 712
advantages/disadvantages, 5, 525
defined, 525, 531
for external storage, 588–590
HashTable class, 544–545
HashTableChaining Visualization tool, 566–569
buckets, 569
deleting data, 568
duplicates, 568
load factors, 568
table size, 569
HashTableOpenAddressing Visualization tool, 536–543
when to use, 823
hashingf
collisions and, 533–536
external storage and, 588–590
keys
open addressing
process of, 530–533
separate chaining
defined, 565
HashTable class, 569–574
HashTableChaining Visualization tool, 566–569
KeyValueList class, 571–572
open addressing vs.587–588
types to use, 574–575
simpleHash() function, 545–546
speed of, 581
strings, 578–580
when to use, 830
HashTable class
HashTableChaining Visualization tool, 566–569
buckets, 569
deleting data, 568
duplicates, 568
load factors, 568
table size, 569
HashTableOpenAddressing Visualization tool, 536–543
haversine formula, defined, 600
Heap class, 677–683
Heap Visualization tool, 674–677
heapify() subroutine, 691–693
heaps
advantages/disadvantages, 5
as binary trees, 666–667, 684–685
changing priority, 674
defined, 104, 666
finding extreme values, 695–700
Heap class, 677–683
Heap Visualization tool, 674–677
insertion in, 669–670
for order statistics, 694–695
as partially ordered, 668
peeking, 674
priority queues and, 667–668
purpose of, 665
removal in, 670–674
replacing maximum, 674
sifting up/down, 670–674
sorting. See heapsort
speed of, 683–684
traversal
heapsort
heapsort() subroutine, 691–693
height of subtrees, defined, 467
hierarchical file system analogy, 340–341
holes, defined, 34–35
Huffman, David, 386
Huffman code
Huffman trees
I
importing Python modules, 18–19
indentation in Python, described, 9–12
indexes. See also file indexes
induction, defined, 237
infix notation
comparison with postfix notation, 133
defined, 133, 363
InfixCalculator tool, 142–148
translating to postfix, 134–142
InfixCalculator tool, 142–148
inheritance, defined, 23
initialization of arrays, 39
in-order successors
in-order traversal, 353–355
insertion
in 2–3 trees, 437–438
in 2–3-4 trees, 404–405
in arrays
bottom-up in trees, 486–487
defined, 4
in doubly linked lists
with duplicates, 36
in file indexes, 451–452
in grids, 620–621
in hash tables
with HashTable class, 548–549
with HashTableOpenAddressing Visualization tool, 537–540
speed of, 584
in heaps, 669–670
in linked lists, 170–174
of nodes
with AVLtree class, 474–478
with AVLTree Visualization tool, 470–472
with Binary Search Tree Visualization tool, 351–352
with BinarySearchTree class, 352–353
in B-trees, 446–449
multiple red nodes, 492
process of, 350
in red-black trees, 492, 498–499
in point lists, 613–614
in priority queues, 127–128
in quadtrees, 636–638, 641–644
in queues, 117, 119
in sequentially ordered files, 443
in stacks. See push (stacks)
top-down in trees, 486
insertion sorts, 87–91
in Array class, 90
comparison of sorting methods, 96–97
described, 87–89
disadvantages, 286
invariants, 91
list insertion sorts, 198
Simple Sorting Visualization tool, 89–90
within small partitions, 315
speed of, 91
when to use, 827
instance attributes, defined, 25
instances, defined, 23
integer index, defined, 38
internal nodes
interpreter (Python), described, 8–12
intersection
interval sequences
intractable problems
defined, 798
Hamiltonian paths/cycles, 800–802
Knight’s Tour, 798
Traveling Salesperson, 799–800
invariants
in bubble sorts, 82
defined, 82
in insertion sorts, 91
in selection sorts, 86
isomorphic, defined, 508
items, defined, 38
iteration
K
K highest
k-d trees, defined, 659
key values
keys
KeyValueList class, 571–572
knapsack problem, 277–278
Knight’s Tour intractable problem, 798
Königsberg bridge problem, 709
L
latitude, defined, 598
layers, query circles within, 625–628
leaves
defined, 339
deleting
left child, defined, 339–340
left heavy, defined, 476
levels (of nodes)
defined, 339
in trees as arrays, 378–379
libraries, when to use, 820
linear probing, 536–543
linear searches
Link class, 159
linked lists
adjacency list, modeling, 712–713
advantages/disadvantages, 5, 336, 821
arrays vs.164
circular lists, 209–210
double-ended lists, 177–183
doubly linked lists, 198–201
for deques, 208
insertion/deletion at ends, 201–204
insertion/deletion in middle, 204–208
Link and LinkedList classes
LinkedList Visualization tool, 164–167
links in, 158–160
ordered lists
described, 192
list insertion sort with, 198
OrderedList class, 193–198
OrderedList Visualization class, 192–193
speed of, 198
queue implementation by, 187–189
reference types and, 160–163
speed of, 183–184
stack implementation by, 184–187
linked trees, nodes in, 378–379
LinkedList class, 159
LinkedList Visualization tool, 164–167
links in linked lists, 158–160
list comprehensions, described, 20–22
list of points, 612
lists (data type in Python). See also ADT lists; linked lists
local variables, defined, 25
logarithms in binary searches, 58–60
logical lines in Python, defined, 10
longitude, defined, 598
looping. See also iterators
M
mapping, defined, 21
markers, finishing iteration, 213
matching delimiters example for stacks, 113–116
mathematical induction, defined, 237
maximum, replacing in heaps, 674, 677
maze analogy (depth-first traversal), 722
measuring tree balance, 464–469
median-of-three partitioning, 313–315
mergesort
advantages/disadvantages, 255, 827
as divide-and-conquer algorithm, 257–260
eliminating recursion in, 270–275
for external files, 453–456
Mergesort Visualization tool, 263–264
with sorted arrays, 255–257
speed of, 264–267
with subranges, 260–262
testing code, 262–263
Mergesort Visualization tool, 263–264
methods, defined, 23
minimum spanning trees
described, 733
in Graph class, 735–739
in Graph Visualization tool, 733
as subgraphs, 733–737
with weighted graphs
building, 770–774
creating algorithm, 774–780
networking example, 768
WeightedGraph class, 776–779
WeightedGraph Visualization tool,768–770
modeling graphs
adjacency list, 712–713
adjacency matrix, 710–712
edges, 710
vertices, 709–710
modules, importing, 18–19
multiple file indexes, 452
multiple red nodes during insertion, 492
multiplying sequences, 15
multivalued assignment, described, 17–18
multiway trees, defined, 337. See also 2–3 trees; 2–3-4 trees; B-trees
mutual recursion, defined, 374
N
name mangling in Python, defined, 44
namespaces in Python, defined, 19
nearest matches
neighbors, defined, 707
networking example (minimum spanning trees), 768
__Node class
Node class (quadtrees), 640–641
nodes
blocks per node in B-trees, 444–445
defined, 336
deleting
finding
with Binary Search Tree Visualization tool, 346–348
with BinarySearchTree class, 348–349
flipping colors, 489–490, 493–494, 499–500
inserting
with AVLtree class, 474–478
with AVLTree Visualization tool, 470–472
with Binary Search Tree Visualization tool, 351–352
with BinarySearchTree class, 352–353
in B-trees, 446–449
process of, 350
in red-black trees, 492–491, 498–499
in linked trees, 378–379
replacing with successors, 373–374
rotating in red-black trees, 490–491, 492–493, 500–507
splitting
nonrandom keys for hashing, 576–578
nonvolatile data storage, defined, 439
null children in red-black trees, 495–496
numbers
converting words to, 527–530
as hash keys, 526–527
raising to powers, 275–276
O
object-oriented programming, described, 23–26
objects
octrees, defined, 659
open addressing
operands, defined, 133, 364
operators
order of the function, defined, 68
order statistics, heaps for, 694–695
ordered arrays
advantages/disadvantages, 5, 57–58, 335–336, 826
defined, 47
Guess-a-Number game example, 48–49
OrderedArray class
OrderedArray Visualization tool, 47–51
binary searches, 49–51
duplicates, 51
OrderedRecordArray class, 61–65
ordered lists
described, 192
list insertion sort with, 198
OrderedList class, 193–198
OrderedList Visualization class, 192–193
speed of, 198
OrderedArray class
OrderedArray Visualization tool, 47–51
OrderedList class, 193–198
OrderedList Visualization class, 192–193
OrderedRecordArray class, 61–65
orders of magnitude, defined, 815
P
parameters, defined, 20
parent nodes, defined, 338
parsing arithmetic expressions
described, 132–133
evaluating postfix expressions, 148–151
Infix Calculator tool, 142–148
postfix notation, 133–134
translating infix to postfix, 134–142
traversal order and, 363–365
partial sorting
partitioning
with AdvancedSorting Visualization tool, 295–297
algorithm for, 297–301
defined, 294–295
in quicksort algorithm, 302–304
detailed explanation, 310–313
eliminating recursion in, 318
full implementation, 315–318
initial implementation, 306–309
median-of-three partitioning, 313–315
small partitions, 315
speed of, 318–320
speed of, 301–302
paths
peeking
in heaps, 674
in priority queues, 128
in queues, 120
in stacks
perfect hash functions, defined, 575–576
permutations, defined, 239
Peters, Tim, 325
pivot values
defined, 295–296
equal keys, 300–301
median-of-three, 313–315
selecting, 304–306
PointList class, 612
points
postfix notation
comparison with infix notation, 133
defined, 133, 364
described, 133–134
evaluating expressions, 148–151
Infix Calculator tool, 142–148
translating infix to, 134–142
post-order traversal, 355
powers, raising numbers to, 275–276
precedence (of operators), defined, 135
prefix notation, defined, 134, 364
pre-order traversal, 355
primary clustering, defined, 558
printing binary search trees, 379–381
priority, changing in heaps, 674
priority queues
defined, 106
described, 126–127
heaps and, 667–668
PriorityQueue class, 129–132
PriorityQueue Visualization tool, 127–129
search and traversal, 132
speed of, 132
use case comparison with arrays, 103–104
when to use, 826
PriorityQueue class, 129–132
PriorityQueue Visualization tool, 127–129
probing, defined, 541
problem analysis, 814–818
amount of data, 815–816
frequency of operations, 816–817
software maintenance responsibilities, 817–818
types of data, 814–815
pseudocode, defined, 140
push (stacks)
Python
comments, 12
dynamic typing, 12–13
exceptions, 22–23
functions/subroutines, 19–20
as interpreted language, 8–12
iteration, 15–17
list comprehensions, 20–22
modules, importing, 18–19
multivalued assignment, 17–18
as object-oriented programming, 23–26
sequences, 13–15
whitespace, 8, 9–12
Q
quadratic probing, 554–559
QuadTree class, 635–636
QuadTree Visualization tool, 639–640
quadtrees
advantages/disadvantages, 5, 828
ambiguity in, 638–639
deleting points, 646–647
described, 633–635
exact matches, 644–645
inserting points, 636–638, 641–644
nearest matches, 647–655
Node class, 640–641
QuadTree class, 635–636
QuadTree Visualization tool, 639–640
traversing points, 645–646
query circles
Queue class, 120–125
Queue Visualization tool, 119–120
queues. See also priority queues
advantages/disadvantages, 5, 825
circular, 118
defined, 106
deques, 125–126
described, 116–117
linked list implementation of, 187–189
Queue class, 120–125
Queue Visualization tool, 119–120
search and traversal, 132
shifting, 117–118
speed of, 125
use case comparison with arrays, 103–104
quicksort
AdvancedSorting Visualization tool, 309–310, 318
algorithm for, 302–304
defined, 302
detailed explanation, 310–313
eliminating recursion in, 318
full implementation, 315–318
initial implementation, 306–309
median-of-three partitioning, 313–315
pivot values, 304–306
small partitions, 315
speed of, 318–320
R
radix, defined, 321
radix sort, 320–323
rail travel example (shortest-path problem), 780–782
all-pairs shortest-path problem, 796–798
Dijkstra’s algorithm, 782–788
implementation of algorithm, 791–792
WeightedGraph class, 792–796
WeightedGraph Visualization tool, 788–791
raising numbers to powers, 275–276
random heaps, 676
random keys for hashing, 575–576
records
recursion
anagrams, 239–242
applications for
binary searches, 242–244
characteristics of, 235–236
defined, 6, 229
divide-and-conquer algorithms, 245
eliminating, 267
factorials, 237–238
finding nth terms with, 232–235
mathematical induction and, 237
mergesort
advantages/disadvantages, 255
as divide-and-conquer algorithm, 257–260
eliminating recursion in, 270–275
Mergesort Visualization tool, 263–264
with sorted arrays, 255–257
speed of, 264–267
with subranges, 260–262
testing code, 262–263
in partitioning algorithm, 297–301
in quicksort algorithm, 302–304
detailed explanation, 310–313
eliminating recursion in, 318
full implementation, 315–318
initial implementation, 306–309
median-of-three partitioning, 313–315
small partitions, 315
speed of, 318–320
speed of, 236
Tower of Hanoi puzzle
recursive depth, defined, 255
red-black correct, defined, 487
red-black rules
balanced trees and, 495
described, 487–488
fixing violations, 488
null children, 495–496
rotations and, 496–497
red-black trees, 485
2–3-4 trees and, 508–510
operational equivalence, 510–514
transformation between, 509–510
advantages/disadvantages, 5
bottom-up insertion, 486–487
characteristics of, 487
implementation, 513–515
red-black rules
RedBlackTree Visualization tool, 488–489
deleting nodes, 491, 508
erasing and randomly filling, 491
flipping node colors, 489–490, 493–494, 499–500
inserting nodes, 492–491, 498–499
multiple red nodes insertion experiment, 492
rotating nodes, 490–491, 492–493, 500–507
searching, 491
unbalanced tree experiment, 494–496
speed of, 508
top-down insertion, 486
RedBlackTree Visualization tool, 488–489
deleting nodes, 491, 508
erasing and randomly filling, 491
flipping node colors, 489–490, 493–494, 499–500
inserting nodes, 492–491, 498–499
multiple red nodes during insertion experiment, 492
rotating nodes, 490–491, 492–493, 500–507
searching, 491
unbalanced tree experiment, 494–496
reference types, 160–163
rehashing hash tables with HashTable class, 551
removal. See also deletion
reversing words example for stacks, 112–113
right child, defined, 339–340
right heavy, defined, 476
ring buffers, defined, 118
root (of trees)
rotation of tree nodes
S
saving operators on stacks, 139–140
scrolling in Tree234 Visualization Tool, 410–411
search
search keys. See keys
searching. See also finding
2–3-4 trees, 404
with Tree234 class, 415–417
with Tree234 Visualization tool, 409
arrays
B-trees, 445–446
with duplicates, 35–36
file indexes, 451, 452–453
hash tables
with HashTable class, 546–548
with HashTableOpenAddressing Visualization tool, 540
speed of, 584
linked lists, 166, 170–174
red-black trees, 491
sequences, 15
sequentially ordered files, 442–443
spatial data, 611–612
stacks and queues, 132
secondary clustering, defined, 558
secondary sort keys, defined, 96
selection sorts, 83–87
in Array class, 85–86
comparison of sorting methods, 96–97
described, 83–85
invariants, 86
Simple Sorting Visualization tool, 85
speed of, 86–87
sentinel values
separate chaining
with buckets, 569
defined, 535, 565
HashTable class, 569–574
HashTableChaining Visualization tool, 566–569
deleting data, 568
duplicates, 568
load factors, 568
table size, 569
KeyValueList class, 571–572
open addressing vs.587–588
speed of, 583–587
types to use, 574–575
sequences
sequential ordering, 442–443
sequential storage, 829
Shell, Donald L.285
Shellsort
AdvancedSorting Visualization tool, 289–291
advantages/disadvantages, 285–286
described, 286–288
insertion sort disadvantages, 286
interval sequences, 288–289, 293
ShellSort class, 291–293
speed of, 294
when to use, 827
ShellSort class, 291–293
shifting queues, 117–118
shortest-path problem
all-pairs shortest-path problem, 796–798
Dijkstra’s algorithm, 782–788
implementation, 791–792
rail travel example, 780–782
WeightedGraph class, 792–796
WeightedGraph Visualization tool, 788–791
siblings, defined, 339
sifting up/down
Simple Sorting Visualization tool
bubble sorts, 79–81
insertion sorts, 89–90
selection sorts, 85
simpleHash() function, 545–546
single child nodes, deleting, 367–370
slicing
lists in Python, 39
sequences, 14
software bloat, defined, 819
sort keys. See keys
SortArray class, 91–96
sorting
with counting sort, 323–324
defined, 6
with heapsort
with mergesort
advantages/disadvantages, 255
as divide-and-conquer algorithm, 257–260
eliminating recursion in, 270–275
for external files, 453–456
Mergesort Visualization tool, 263–264
with sorted arrays, 255–257
speed of, 264–267
with subranges, 260–262
testing code, 262–263
partitioning. See partitioning
with quicksort
AdvancedSorting Visualization tool, 309–310, 318
algorithm for, 302–304
defined, 302
detailed explanation, 310–313
eliminating recursion in, 318
full implementation, 315–318
initial implementation, 306–309
median-of-three partitioning, 313–315
pivot values, 304–306
small partitions, 315
speed of, 318–320
with radix sort, 320–323
with Shellsort
AdvancedSorting Visualization tool, 289–291
advantages/disadvantages, 285–286
described, 286–288
insertion sort disadvantages, 286
interval sequences, 288–289, 293
ShellSort class, 291–293
speed of, 294
simple sorting algorithms
with Timsort, 324–327
topological sorting
algorithm for, 742
dependency relationships example, 739
in directed graphs, 742–743
in Graph class, 746–747
improving, 747–751
speed of, 751
when to use, 826–828
spatial data
Cartesian coordinates
bounding boxes of query circles, 603–604
defined, 597–598
distance between points, 599
defined, 597
geographic coordinates
bounding boxes of query circles, 604–605
defined, 598
distance between points, 599–601
higher dimensions for, 658–659
operations on, 658
query circles
bounding boxes of, 603
Bounds class, 605–606
bounds completely within other bounds, 610–611
CircleBounds subclass, 607–609
distance between points, 601–603
intersection of bounding boxes, 609–610
within layers, 625–628
searching, 611–612
special-ordering data structures, when to use, 824–826, 828–829
speed
2–3 trees, 438
2–3-4 trees, 431
algorithms
Big O notation, 65–68
general-purpose data structures, 819–820, 824
sorting algorithms, 828
special-ordering data structures, 826
AVL trees, 484–485
binary search trees, 350, 375–377
B-trees, 449–450
bubble sorts, 82
counting sort, 324
graph algorithms, 798
hash function computation, 575
hashing, 581
heaps, 683–684
heapsort, 693
insertion sorts, 91
K highest, 696–700
linked lists, 183–184
mergesort, 264–267, 456
ordered lists, 198
partitioning, 301–302
priority queues, 132
quadtrees
exact matches, 645
insertion, 644
nearest matches, 655
queues, 125
quicksorts, 318–320
radix sort, 322
recursion, 236
red-black trees, 508
selection sorts, 86–87
Shellsorts, 294
spatial data searches, 656–658
stacks, 116
Timsort, 327
topological sorting, 751
splitting
nodes
root (of trees), 406–407
stability of sorting algorithms, 96
Stack class, 108–112
delimiter matching example, 113–116
error handling, 111–112
word reversal example, 112–113
Stack Visualization tool, 106–108
stacks
advantages/disadvantages, 5, 825
defined, 104–105
eliminating recursion with, 267–270
linked list implementation of, 184–187
postal analogy, 105–106
saving operators on, 139–140
search and traversal, 132
speed of, 116
Stack class, 108–112
delimiter matching example, 113–116
error handling, 111–112
word reversal example, 112–113
Stack Visualization tool, 106–108
use case comparison with arrays, 103–104
storage requirements. See also external storage
2–3 trees, 438
2–3-4 trees, 432
AVL trees, 484–485
binary search trees, 350, 375–377
B-trees, 449–450
bubble sorts, 82
counting sort, 324
graph algorithms, 798
hash tables, 581
heaps, 683–684
heapsort, 693
insertion sorts, 91
K highest, 696–700
linked lists, 183–184
mergesort, 264–267, 456
ordered lists, 198
partitioning, 301–302
priority queues, 132
quadtrees
exact matches, 645
insertion, 644
nearest matches, 655
queues, 125
quicksorts, 318–320
radix sort, 322
recursion, 236
red-black trees, 508
selection sorts, 86–87
Shellsorts, 294
spatial data searches, 656–658
stacks, 116
Timsort, 327
topological sorting, 751
storing
strings
subgraphs, minimum spanning trees as, 733–737
subheaps, 686–688
subranges, merging, 260–262
subroutines, described, 19–20
subtrees
successors
swapping node colors, 489–490, 493–494, 499–500
symbol tables, defined, 527
T
termination tests, finishing iteration, 213
testing
arrays, 40–47
BinarySearchTree class, 382–385
double-ended lists, 180–183
doubly linked lists, 207–208
mergesort, 262–263
ordered arrays, 56–57, 61–65
ordered lists, 196–198
priority queues, 131–132
queues, 123–125, 188–189
Shellsorts, 292–293
simple sorting algorithms, 94–96
stacks, 110–112, 186–187
Timsort, 324–327, 827
tokens, defined, 145
top-down insertion, 486
topological sorting
algorithm for, 742
dependency relationships example, 739
of directed graphs, 742–743
in Graph class, 746–747
improving, 747–751
speed of, 751
Tower of Hanoi puzzle
TowerOfHanoi Visualization tool, 246–247
transitive closure, 751–756
translating infix to postfix notation, 134–142
Traveling Salesperson intractable problem, 799–800
traversal
Tree234 Visualization tool, 408–411
tree-based heaps, 684–685
trees. See also types of trees
advantages/disadvantages, 335–336
balanced/unbalanced
cycles and, 743–744
defined, 336–337
terminology, 337–340
traversal of
2–3-4 trees, 421–423
with Binary Search Tree Visualization tool, 361–363
with BinarySearchTree class, 356–361
defined, 339, 353
order of, 363–365
in-order traversal, 353–355
post-order traversal, 355
pre-order traversal, 355
triangular numbers
defined, 230–231
eliminating recursion in, 268–270
finding nth term
tuples, defined, 17, 715
two-dimensional arrays
adjacency matrix as, 710–711
in Python, 713–714
W
Warshall, Stephen, 752, 798
Warshall’s algorithm
weighted graphs
WeightedGraph class
minimum spanning trees, 776–779
shortest-path problem, 792–796
WeightedGraph Visualization tool
minimum spanning trees, 768–770
shortest-path problem, 788–791
whitespace in Python, described, 8, 9–12
word clouds example (heaps), 694–695
word reversal example for stacks, 112–113
worst case, defined, 266
..................Content has been hidden....................
You can't read the all page of ebook, please click
here login for view all page.
