INDEX

A

Abstract class, 137–139

versus fully defined class and interface, 139–140

Abstract data type, 31

Abstract method, 29

abstract modifier, 138

Abstraction,

data, 27–28

Accessor method, 57

Activation record, 209, 334

Active method, 208

Acyclic graph, 646, 648, 667, 669, 693–694

Adjacent vertices, 644

Aggregation, 51

Algorithm, 105

connectedness, 658–659

divide-and-conquer, 476–477

longest path, 667–669

minimum spanning tree, 659–663

shortest path, 663–667

Algorithm analysis, 105–121

Alternate implementation(s)

of the BinarySearchTree class, 449–451

of the HashMap class, 626–635, 640

of the LinkedList class, 294–295, 323

A-maze-ing application, 195–208

Ancestor, 379, 439

Application Programming Interface (API), 6

Applications

backtracking through a maze, 195–208

backtracking through a network, 686–689, 695–697

converting from infix to postfix, 338–343

creating a symbol table, 617–625

high-precision arithmetic, 251–257

how compilers implement recursion, 334–337

Huffman encoding, 573–590

line editor, 300–315

simulated car wash, 351–365

spell checker, 530–536

thesaurus, 517–525

Approval voting (project), 545–547

Argument, 19

ArrayList class, 234–251

fields in, 248

heading of, 246–247

versus LinkedList class, 150, 282–285

ArrayList objects,

serializing, 247, 701–702

simple program using, 244–246

Arrays class

binarySearch, 112–113, 180

sort (Merge Sort), 470–476

(Quick Sort), 477–489

assertArrayEquals, 62, 458

assertEquals, 62

Association, 51

Attribute in Unified Modeling Language, 49

Automatic garbage collection, 93

averageSpace(n), 106

averageTime(«), 106

important assumption for, 106

AVL tree, 435–436

height of, 436–438

AVLTree class, 438–441

fixAfterDeletion method (project), 451–454

fixAfterInsertion method (project), 455

B

BackTrack class, 193–195

Backtracking, 191–195

a-maze-ing application, 195–198

Eight Queens (project), 221–222

Knight's Tour (project), 222–224

Numbrix (project), 227–231

Sudoku (project), 225–226

through a network, 686–689, 695–697

Balance factor, 438–439

Balanced binary search tree, 430–435

AVL tree, 435–436

red-black tree, 501–504

rotations, 431–435

Base of a logarithm, 707

Base case, 709

Big-O notation, 106–116

Big-Omega notation, 116

Big-Theta notation, 117–119

Biglnteger class, 251

Binary search, 112–113, 180–185

Binary search tree, 402

AVL tree, 435–436

red-black tree, 501–504

rotations, 431–435

Binary tree, 377–392

branches and leaves, 378–379

chain, 384

complete, 381–383

decision tree, 468

definition, 377

external path length, 385

full, 381

Huffman tree, 576

properties, 378–386

traversals, 386–392

two-tree, 381

Binary Tree Theorem, 383

BinarySearchTree class, 403–427

add method, 416–418

alternative implementation, 449–450

contains method, 414, 420

embedded Entry class, 411–412

embedded TreeIterator class, 427–430

fields, 411

method specifications, 407–408

remove method, 418–426

testing, 410–411

TreeIterator embedded class, 427–430

BinarySearchTreeTest class, 410–411

Binding

dynamic, 49

late, 49

Bit-wise operators,

& (and), 605, 608

^ (exclusive or), 608

<< (left shift), 382

>> (right shift, 112

>>> (unsigned right shift), 608

Black-height, 716–718

Bottom-up testing, 91

Boundary condition, 66

Boxing, 141

Branch, 378

Breadth-first iterator, 651–654, 683

break statement, 73

Bubble Sort, 463–464

Bytecode, 92

C

CalendarDate (project), 58

Car wash (application), 351–365

randomizing the arrival times, 362–365

CarWash class, 354–361

Car class, 356, 359

CarWashTest class, 355

CarWashUser class, 361–362

fields, 355–357

UML diagram, 357

catch block, 68–69, 73

with finally block, 81

with try block, 68–69

chain in a binary tree, 384

Chained hashing, 609–610

char type, 2–3

Checked exception, 77–78

Circularity in LinkedList class, 298

Circularity in SinglyLinkedList class (project), 322

Class, 3–7

abstract, 137–139

ArrayList, 234–251

Arrays, 112–113, 180, 470–475, 477–489

AVLTree, 438–441

BackTrack, 193–195

BigInteger, 251

CalendarDate, 58

Car, 356, 359

CarWash, 354–361

CarWashTest, 355

CarWashUser, 361–362

Collections, 256, 476

Company, 35–37

CompanyTest, 64–66

constant, 60–61

constructor, 4–5, 43, 92

contiguous, 133

DecimalToBinaryTest, 163

Editor, 304–312

EditorTest, 306–307

EditorUser, 312–315

embedded, 269

Entry, 268–269

in BinarySearchTree class, 412

in HashMap class, 610

in Huffman class, 580

in LinkedList class, 295

in SinglyLinkedList class, 268–269

in TreeMap class, 513

FactorialTest, 157–158

Field, 1

FullTimeEmployee, 32–34

FullTimeEmployeeTest, 62–63

Hasher, 620–625

HashIterator, 615–619

HashMap, 603–615

HashSet, 625–626

HourlyEmployee, 38–43

HourlyEmployeeTest, 66–67

Huffman, 581–586

HuffmanTest, 582

HuffmanUser, 586–589

HuffmanUserTest, 587

Immutable, 20

implementing an interface, 32–34

inheritance, 37–43

instance variables, 59

LinkedList, 295–300

ListItr, 285–291

Mutable, 21–22

Network, 669–686

NetworkTest, 677

Nothing, 19

PriorityQueue, 552–566

Random, 122–126

SalariedEmployee, 46

SinglyLinkedList, 268–276

SinglyLinkedListIterator, 276–279

SpellChecker, 531–534

SpellCheckerTest, 533

SpellCheckerUser, 534–536

String, 4–9

Swap, 20–21

Thesaurus, 518–521

ThesaurusTest, 519–520

ThesaurusUser, 521–525

ThesaurusUserTest, 521–522

TreeIterator, 427–430

TreeMap, 509–517

TreeSet, 525-530

VeryLongInt, 252–257

VeryLongIntTest, 253

VeryLongIntUser, 257

VeryLongIntUserTest, 257

Class constant, 60–61

Class variable, 60

clone method, 237–238

Cloneable interface, 246–247

close() method in PrintWriter class, 82, 85

Clustering in open-address hashing

primary, 631–632

Co-domain (of a function), 705

Collection interface, 141–142

Collections class, 256, 476

Collision, 606

Collision handling

with chained hashing, 609–611

with open-address hashing, 626–634

Company class, 35–37

CompanyTest class, 64–66

Comparable interface, 179

Comparator interface, 465–468

Compiler: implementing recursion, 334–338

Complete binary tree, 381–383

Computer simulation, 350–351

Concordance (project), 543–545

Conditional operator (?:), 300

Connectedness, 646–647, 658–659

Constant (independent of n), 111, 117

Constant identifier, 60

Constructor, 4–5, 30, 43

copy, 236–237

default, 4, 43

inheritance and, 43

Contiguous-collection class, 136, 234–251, 329–332, 552–566

Contiguous elements, 17, 136

Conversion formulas, 135

Converting from infix notation,

to postfix notation, 338–343

to prefix notation, 343–346

tokens, 342–343

transition matrix, 341–342

Copy

shallow, 236–237

Copy constructor, 236–237

Correctness, 61

Cost of recursion, 209–210

Covariant subtyping, 237

Critical activity, 668

Critical path, 668

Current line (in line editor), 300

Cycle, 646, 669

D

Data abstraction, 27

principle of, 27–28

Data structure, 31

Dead end, in backtracking, 191

Decimal to binary (application), 162–167

Decision tree, 468–469

Decoding a Huffman-encoded message (project), 595–597

Default constructor, 4, 43

Default visibility, 93

versus visibility modifiers, 93–94, 100

Depth of an element, 381

Depth-first iterator, 654–658

Depth-first search, 390–391

Dequeue, 347

Deserialize, 702

Design pattern, 147

divide-and-conquer, 476–477, 484

greedy, 578, 663, 664, 686, 692–693

iterator, 147

Dictionary, 505

Dijkstra's Algorithm, 663–667, 683–686

Directed graph (digraph), 647–648

Directed tree, 648–649

Directed weighted graph, 649

Distribution

Poisson, 362–365

uniform, 122

Divide-and-conquer algorithms, 476–477, 484

Domain (of a function), 705

Double hashing, 632–635, 638, 640

Double rotation, 434–435

Doubly linked list, 267–268

Dummy entry, 295

Dynamic binding, 49

E

Earliest time for an event, 668

Edge, 643

Editor class, 304–312

EditorTest class, 306–307

EditorUser class, 312–315

EditorUserTest class, 313

Efficiency of methods (estimating), 105–119

Eight Queens (project), 221–222

Embedded class, 269

Employee interface, 31–32

Encapsulation, 48

Encoding, 573

prefix-free, 573–575

Enhanced for statement, 145–147

Enqueue, 347

Entry class

in BinarySearchTree class, 412

in HashMap class, 610

in Huffman class, 580

in LinkedList class, 295

in SinglyLinkedList class, 268–269

in TreeMap class, 513

reason for static modifier, 296

Entry interface, 610

Equality

of objects, 7–9

of references, 8–9

untestability of double values for, 66–67

equals method, 8, 94, 411

in Object class, 94–95

overriding, 95–96

Error

in JUnit, 76

Evaluation of a condition (project), 371–374

Event-driven simulation, 354

Exception, 6, 68

checked, 77–78

handling of, 68–74

propagating, 71–74

testing, 69–71, 74–77

thrown, 68–69

Execution frame, 159–161

Exponential-time method, 119

Expression tree, 389–390

Expression, 44–45

extends, 38

External path length, 385

External Path Length Theorem, 385–386

F

Factorial, 156–159

execution frames, 159–161

FactorialTest class, 157–158

Failure

in JUnit, 76

Fail-fast iterators, 703–704

Fairness in priority queue, 557, 566

Fast sorts

Heap Sort, 567–573

Merge Sort, 470–475

Quick Sort, 477–489

Feedback, 350

Fibonacci numbers, 167

Fibonacci tree, 437

Field(s), 1

in the ArrayList class, 248

in the BinarySearchTree class, 411

in the CarWash class, 355–357

in the Editor class, 307–308

in the Hasher class, 621

in the HashMap class, 610–611

in the LinkedList class, 295

in the Network class, 680–681

in the SinglyLinkedList class, 273

in the SpellCheck class, 533

in the Thesaurus class, 520

in the TreeMap class, 512

in the VeryLongInt class, 254

pre-initialization of, 92

File

input, 12–16

output, 81–91

sorting (project), 497–499

final modifier, 60

finally block, 81

Finite sequence, 706

First-in, first-out (FIFO)

in a queue, 347

fixAfterDeletion method

in AVLTree class (project), 455

in TreeMap class (lab), 517

fixAfterInsertion method

in AVLTree class (project), 451–454

in TreeMap class (lab), 515

Full binary tree, 381

FullTimeEmployee class, 32–34

Function, 705

growth rate of, 117–119

and map, 705

G

Garbage, 92

automatic collection of, 92–93

Generating

a minimum spanning tree, 659–663

permutations

exercise, 215–216

lab experiment, 191

pseudorandom values, 122

Generic type, 140–141

Graph

acyclic, 646, 648, 667, 669, 693–694

algorithms, 651–669

cycle, 646, 669

directed, 647–648

edge, 643

neighbor, 644

path, 644

undirected, 643

vertex, 643

weighted, 649

Graph algorithms

breadth-first traversal, 651–654

connectedness, 658–659

depth-first traversal, 654–658

longest path, 667–669

minimum spanning tree, 659–663

shortest path, 663–667

Greedy algorithm, 578

Dijkstra's algorithm, 663–667, 683–686

Huffman's algorithm, 573–577

Prim's algorithm, 659–663

Growth rates, 117–119

H

Has-a, 47

Hash classes

HashMap, 603–615

HashSet, 625–626

Hasher class, 620–625

Hashing, 606

chained, 606–612

double, 632–635, 638, 640

identifiers, 617–625

Uniform Hashing Assumption, 609

HashIterator class, 615–619

HashMap class, 603–615

chaining, 606–612

fields in, 610–611

implementation of, 612–614

views (entrySet(), keyset(), values()), 616

HashSet class, 625–626

Heading

of the ArrayList class, 246

of the BinarySearchTree class, 406

of the HashMap class, 603

of the LinkedList class, 295

of the Network class, 670

Heap, 553–554

Heap Sort, 567–573

Height

black height, 716–718

of an AVL tree, 436–438

of a binary search tree, 434–436

of a binary tree, 339, 447–448 of a red-black tree, 503–504

Hexadecimal notation (exercise), 25

High-precision arithmetic (application), 251–257

HourlyCompany class, 44

HourlyEmployee class, 38–42

HourlyEmployeeTest class, 66–67

How fast can we sort, 468–469

Huffman

Huffman class, 581–586

Huffman encoding, 574

Huffman tree, 574

HuffmanTest class, 582

HuffmanUser class, 586–589

HuffmanUserTest class, 587

I

Identifier, 617

Imbalance ancestor, 439

Immutable, 20

Immutable class, 20

import directive, 12

In-place sorting, 461, 572

Index-related method, 147

Indirect recursion, 208–209

Induction and recursion, 719

Infinite recursion, 177

Infix notation, 338

converting to postfix, 338–343

converting to prefix, 343–346

Information hiding, 48

Inheritance, 37–43

and constructors, 43

multiple inheritance (not allowed), 139

Insertion Sort, 459–461

Instance variables, 59

instanceof operator, 96

Integrated Web Browser and Search Engine (project),

ArrayList, 264–266

GUI, 102–104

HashMap, 640–642

LinkedList, 328

Network, 698–700

PriorityQueue, 595–598

TreeMap, 548–550

Interface

Application Programming Interface, 6

Collection interface, 141–142

Comparable interface, 179

Comparator interface, 465–468

Employee interface, 31–32

Iterator interface, 143–144

List interface, 147

ListIterator interface, 285–287

Map interface, 504–508

Queue interface, 348

Set interface, 403

SortedMap interface, 508

SortedSet interface, 525

Interning of strings, 8

Intractable problem, 119

Invariant subtyping, 237

Is-a, 47

Iterative method, 161

Iterator, 143

bi-directional, 285

breadth-first, 651–654, 682

depth-first, 654–658

design pattern, 143

fail fast, 703–704

J

Java Collections Framework, 133

Java Virtual Machine, 92

java.util, 12

javadoc notation, 6–7

JUnit, 61–67, 69–70, 74–77

assertArrayEquals, 62, 458

assertEquals, 62

error, 76

exception testing, 74–75

fail(), 90 failure, 76

no testing of Big-O claims, 131

no testing double values for equality, 66

stub testing, 64, 76, 307

test first, 63–64

K

Key part in a map, 504

Knight's Tour (project), 222–224

L

Last-in, first-out (LIFO),

in a stack, 32

Late binding, 49

Latest time (for an event), 668

Leaf, 378

Leap year, 71

LeapYear class, 72

LeapYearTest class, 74–76

Left child, 379

Left rotation

followed by right rotation, 434–435

Length

of a path in a graph, 645

of a path in a network, 650

Let's Make a Deal (project), 131–132

Level of an element, 380–381

Line editor (application), 300–315

Linear in n, 117

Linear-logarithmic in n, 117

Link, 267

Linked list, 267

doubly linked list, 268

singly linked list, 268

LinkedList class, 295–300

alternate implementation (project), 323

iterators, 285–291

versus ArrayList class, 282–285, 291

List interface, 147

loadFactor, 611-612

Local variable, 9–12

explicit initialization, 10

Logarithmic in n, 117

Logarithms, 707–708

Longest path through a network, 667–668

Lower bound on sorting, 468–469

M

main method, 1, 35

Map, 504

Map interface, 504–508

embedded Entry interface, 610

Mathematical background

functions and sequences, 705–719

logarithms, 707–708

mathematical induction, 708–719

sums and products, 706–707

Mathematical induction. See Principle of Mathematical

Induction

and recursion, 719

Mathematical model, 350

Maze (application), 195–208

Mean arrival time, 362

Median, 478

finding in linear-in-n time (exercise), 495–496

of medians, 488

Member of a class, 35

Member-selection operator, 7

Merge Sort

in Arrays class, 470–476

in Collections class, 476

Message

in Huffman encoding, 573

in object-oriented language, 7

Method, 1

abstract, 29

accessor, 57

active, 208

exponential-time, 119

final, 61

iterative, 161

local variables in, 9–12

mutator, 57

overloading, 5

overriding, 37–38

polynomial-time, 119

private, 39, 94

protected, 39, 94

public, 39, 94

recursive, 208–209

signature, 5

static, 61

testing of, 61–67, 69–70, 74–77

timing of, 121–122

virtual, 49

Method specification, 5–6

in javadoc notation, 6–7

Minimum spanning tree, 659–663

Model, 350

mathematical, 350

physical, 350

Modifier. See Visibility modifier,

abstract, 138

final, 60–61

private, 39, 94

protected, 39, 94

public, 39, 94

static, 60–61

transient, 248

Modularity, 3–4

Modulus operator (%), 2

Mutable class, 21–22

Mutator method, 57

N

Natural logarithm, 708

Neighbor, 644

Nested class, 269

Network, 649–689

backtracking through, 686–689, 695–697

finding longest path, 667–669

finding minimum spanning tree, 659–663

finding shortest path, 663–667

Network class, 669–686

NetworkTest class, 677

project network, 667

Traveling Salesperson Problem (project), 694–695

new operator, 4

node, 136

Notation

Big-O, 106–116

Big-Omega, 116

Big-Theta, 117–119

infix, 338

javadoc, 5–7

postfix, 339

prefix, 343

null keyword, 7

NullPointerException, 78

O

Object class, 46–47

overriding equals method of, 94–96

Object-oriented concepts, 27–49

Open-address hashing, 626–637

double hashing, 632–635, 638, 640

primary clustering, 631–632

Open-Closed Principle, 38

Operator

bitwise and (&), 605, 608

bitwise exclusive or (^), 608

bitwise left shift (<<), 382

bitwise right shift (>>), 112

unsigned (>>>), 608

conditional (? :), 300

equality (==), 8

instanceof, 96

modulus (%), 2

new, 4,

Output file, 81–91

Overloading of methods, 5

Overriding of methods, 37–38

P

Package, 93

Parameterized type, 140–141

Parent, 379

Path, 381, 644

cycle, 646, 669

length, 645

Path length

external, 385

Path Rule, 502

Performance requirements, 120

Permutation, generating

exercise, 215–216

lab experiment, 191

Persistent object, 702

Physical model, 350

Poisson distribution, 362–365

Polymorphism, 48–49

Polynomial-time method, 119

Postcondition, 6, 28

Postfix notation, 338

converting from infix to, 338–343

Pre-initialization of fields, 92

Precondition, 28

Prefix notation, 343

converting from infix to, 343–346

Prefix-free encoding, 573–575

Prim's Algorithm, 659–663

Primary clustering, 631–632

Primitive type, 2

Principle of Data Abstraction, 27–28

Principle of Mathematical Induction, 708

general form, 711

strong form, 710

Priority queue, 551

heap implementation of, 553–556

in Huffman encoding, 575

in minimum-spanning-tree algorithm, 660

in shortest-path algorithm, 664

PriorityQueue class, 552–566

private visibility, 39, 94

versus other visibility modifiers, 93–94, 100

Probing

quadratic, 635

Program modularity, 3–4

Project network, 667–669

critical activity, 668

critical path, 668

earliest time of an event, 668

latest time of an event, 668

project length, 667–668

sink, 667

slack time of an activity, 668

source, 667

topological order, 669

topological sorting, 669

Propagating exceptions, 71–74

protected visibility, 39, 94

fields, 39

methods, 42

testing protected methods, 306

versus other visibility modifiers, 39, 94

Pseudo-random number generator, 122

public visibility, 39, 94

versus other visibility modifiers, 39, 94

Public-key cryptography, 251

Punched-card sorters, 489

PurePriorityQueue class, 552

PureQueue class, 349

PureStack class, 333

Q

Quadratic in n, 117

Quadratic probing, 635

Queue, 347

computer simulation, 350–365

dequeue, 347

enqueue, 347

Queue interface, 348

implemented by LinkedList class, 348

implemented by PriorityQueue class, 552

Quick Sort, 477–484

optimizations, 484–489

Quotient-offset collision handler, 632–633

R

Radix Sort, 489–492

Random access, 134

Random class, 122–126

Random number, 122

Random-number generator, 122

Randomizing

arrival times in simulation, 362–365

variable seed in Random class, 123

Reachable vertices, 651

Recursion, 155–210

activation record, 209, 334

backtracking, 191–195

cost of, 209–210

decimal to binary (application), 162–167

definition, 209

divide and conquer, 476–477

execution frame, 159–161

factorial, 156–159 indirect, 208–209

induction and, 719

infinite, 177

maze searching (application), 195–208

stack frame, 304

stack-based implementation, 334–338

Towers of Hanoi (application), 167–179

versus iteration, 161

Recursive definition, 377

Red Rule, 502

Red-black tree, 502

height of, 504, 715–718

in TreeMap implementation, 504

Reference variables, 4

testing equality of (==), 8

Right child, 379

Right rotation, 433

followed by left rotation, 435

Robust program, 68

Root element, 377, 648

Rotation, 431

double, 434–435

left, 431–433

properties of, 435

right, 433–434

Run-time analysis, 121–126

of sort methods (lab), 492

S

SalariedEmployee class (lab), 46

Scanner class, 12–17

delimiter, 12

InputMismatchException, 71

scanning over a string, 12

scanning over file input, 12

scanning over keyboard input, 12

token, 12

useDelimiter method, 16

whitespace, 12

Scope of an identifier, 11

Search engine. See Integrated Web Browser and Search Engine

Searching

an array, 179–181

binary search, 180–181, 601–602

framework to analyze, 599–600

in HashMap class, 614–615

red-black tree, 602–603

sequential, 179, 600–601

seed, 123

Selection Sort, 461–463

Sequence, 706

Sequential searching, 179, 600–601

Serialization, 701–703

Set interface, 403

Shallow copy, 236–237

Shortest path through a network, 663–667

Signature of a method, 5

Simple sorts, 458–464

Simulation, 350

event driven, 354

Singly linked list, 268

SinglyLinkedList class, 268–281

embedded SinglyLinkedListIterator class, 276–279

embedded Entry class, 268

expanding (projects), 319–322 field, 273

method definitions, 273–276

testing, 271–272

SinglyLinkedTest class, 271–272

Sink, 667

Slack time (for an activity), 668

SortedMap interface, 508

TreeMap implementation of, 509

Sorting

Bubble Sort, 463–464

fast sorts, 470–475, 477–489, 567–573

file sorting (project), 497–499

Heap Sort, 567–573

in-place sorting, 461, 572

Insertion Sort, 459–461

Merge Sort, 470–475

Quick Sort, 477–489

Radix Sort, 489–492

Selection Sort, 461–463

simple sorts, 458–464

stable sort, 458

summary, 493

topological sorting, 669

Source, 667

Spanning tree, 659

Specification of methods, 5

Speedo's car wash (application), 351–354

making more realistic, 362–365

Spell Checker (application), 530–531

SpellChecker class, 531–534

SpellCheckerTest class, 532–533

SpellCheckerUser class, 534–536

Splitting Rule, 112

Stable sort, 458

Stack, 329

in converting from infix-to-postfix, 334–338

in implementing recursion, 338–341 Stack class, 329–333

Stack frame, 334

Static constant, 60

static modifier, 60

Static variable, 60

Storage structures for collection classes, 136

String class, 4–9

constructors, 4

testing equality of String objects, 7–8

Stub, 64

Subclass, 37–38

Subclass-Substitution Rule, 44

Sums and products, 706–707

super, 40

Superclass, 37

Symbol table, 617

Synonym, 606

System test, 91

T

Testing

bottom up, 91

unit testing. See JUnit

system tests, 91

Thesaurus (application), 517–518

Thesaurus class, 518–521

ThesaurusTest class, 519–520

ThesaurusUser class, 521–525

ThesaurusUserTest class, 521–522

throw statement, 71

throws clause, 67–68

Timing, 121–122

Token, 342

Topological order, 669, 693–694

Topological sorting, 669

Towers of Hanoi (application), 167–178

iterative version (project), 219–220

Trade-off, 119–121

performance requirements, 120

time versus space, 120

transient modifier, 248

Transition matrix, 341–342

Traveling Salesperson Problem (lab), 684

Traversals of a binary tree, 383–392

breadthFirst, 391–392

inOrder, 386–388

postOrder, 387–390

preOrder (= depth-first), 390–391

Tree

balanced binary search tree, 430

binary search tree, 402

binary tree, 377

complete tree (binary), 382

decision tree (binary), 468

directed tree, 648

expression tree (binary), 389–390

Fibonacci tree (binary), 437

full tree (binary), 381

Huffman tree (binary), 575

red-black tree (binary), 502

root, 377, 648

spanning tree, 659

subtree, 377

two-tree (binary), 381

undirected tree, 648

TreeMap class, 509–517

approval voting (problem), 545–547

building a concordance (problem), 543–545

building a thesaurus (application), 518–525

Comparable and Comparator interfaces, 510–511

determining word frequencies (problem), 542–543

Entry class, 513

field in Network class, 680–681

fields in, 512

red-black tree, 504

SortedMap interface, 509

views (entrySet(), keyset(), values()), 507–508

TreeSet class, 525–530

spell checker (application), 530–536

try block, 68–69

with catch block, 68–69

with finally block, 81

Two-tree, 381

Type parameter, 141

U

UML, See

Unified Modeling Language Unboxing, 141

Undirected graph, 643–646

acyclic, 646

adjacent, 644

complete, 644

connected, 646

cycle, 646

edge, 643

neighbor, 644

path, 644

vertex, 643

Undirected, weighted tree, 676

Unified Modeling Language (UML), 49–52

Uniform distribution, 112

Uniform Hashing Assumption, 609

Upper bound, 107

V

Value part in a map, 504

Variable, 1, 2

reference variable, 4

Vertex, 643

comparing vertices, 680

reachable, 651

Very long integers (application), 251–257

VeryLongInt class, 251–257

field in, 254

VeryLongIntTest class, 253

VeryLongIntUser class, 257

VeryLongIntUserTest class, 257

Virtual method, 49

Visibility modifier, 39, 94

default visibility, 93

private, 39, 94

protected, 39, 94

public, 39, 94

W

Web browser. See Integrated Web Browser and

Search Engine

Weighted graph, 649

Word frequencies (problem), 542–543

worstSpace(n), 105

worstTime(n), 106

Wrapper class, 135

conversions from/to, 135

Wrapper method, 158, 164, 169, 181