book

Data Structures and Algorithms in Java, 2nd Edition

by Robert Lafore

September 2017

Intermediate to advanced

800 pages

23h 19m

English

Sams

Read now

Unlock full access

What’s New in the Second EditionAdditional TopicsEnd-of-Chapter QuestionsExperimentsProgramming ProjectsWhat This Book Is AboutWhat’s Different About This BookEasy to UnderstandWorkshop AppletsJava Example CodeWho This Book Is ForWhat You Need to Know Before You Read This BookThe Software You Need to Use This BookHow This Book Is OrganizedEnjoy Yourself!

What Are Data Structures and Algorithms Good For?Real-World Data StorageProgrammer’s ToolsReal-World ModelingOverview of Data StructuresOverview of AlgorithmsSome DefinitionsDatabaseRecordFieldKeyObject-Oriented ProgrammingProblems with Procedural LanguagesObjects in a NutshellA Runnable Object-Oriented ProgramInheritance and PolymorphismSoftware EngineeringJava for C++ ProgrammersNo PointersOverloaded OperatorsPrimitive Variable TypesInput/OutputJava Library Data StructuresSummaryQuestions
The Array Workshop AppletInsertionSearchingDeletionThe Duplicates IssueNot Too SwiftThe Basics of Arrays in JavaCreating an ArrayAccessing Array ElementsInitializationAn Array ExampleDividing a Program into ClassesClasses LowArray and LowArrayAppClass InterfacesNot So ConvenientWho’s Responsible for What?The highArray.java ExampleThe User’s Life Made EasierAbstractionThe Ordered Workshop AppletLinear SearchBinary SearchJava Code for an Ordered ArrayBinary Search with the find() MethodThe OrdArray ClassAdvantages of Ordered ArraysLogarithmsThe EquationThe Opposite of Raising Two to a PowerStoring ObjectsThe Person ClassThe classDataArray.java ProgramBig O NotationInsertion in an Unordered Array: ConstantLinear Search: Proportional to NBinary Search: Proportional to log(N)Don’t Need the ConstantWhy Not Use Arrays for Everything?SummaryQuestionsExperimentsProgramming Projects
How Would You Do It?Bubble SortBubble Sort on the Baseball PlayersThe BubbleSort Workshop AppletJava Code for a Bubble SortInvariantsEfficiency of the Bubble SortSelection SortSelection Sort on the Baseball PlayersThe SelectSort Workshop AppletJava Code for Selection SortInvariantEfficiency of the Selection SortInsertion SortInsertion Sort on the Baseball PlayersThe InsertSort Workshop AppletJava Code for Insertion SortInvariants in the Insertion SortEfficiency of the Insertion SortSorting ObjectsJava Code for Sorting ObjectsLexicographical ComparisonsStabilityComparing the Simple SortsSummaryQuestionsExperimentsProgramming Projects
A Different Kind of StructureProgrammer’s ToolsRestricted AccessMore AbstractStacksThe Postal AnalogyThe Stack Workshop AppletJava Code for a StackStack Example 1: Reversing a WordStack Example 2: Delimiter MatchingEfficiency of StacksQueuesThe Queue Workshop AppletA Circular QueueJava Code for a QueueEfficiency of QueuesDequesPriority QueuesThe PriorityQ Workshop AppletJava Code for a Priority QueueEfficiency of Priority QueuesParsing Arithmetic ExpressionsPostfix NotationTranslating Infix to PostfixEvaluating Postfix ExpressionsSummaryQuestionsExperimentsProgramming Projects
LinksReferences and Basic TypesRelationship, Not PositionThe LinkList Workshop AppletThe Insert ButtonThe Find ButtonThe Delete ButtonA Simple Linked ListThe Link ClassThe LinkList ClassThe insertFirst() MethodThe deleteFirst() MethodThe displayList() MethodThe linkList.java ProgramFinding and Deleting Specified LinksThe find() MethodThe delete() MethodOther MethodsDouble-Ended ListsLinked-List EfficiencyAbstract Data TypesA Stack Implemented by a Linked ListA Queue Implemented by a Linked ListData Types and AbstractionADT ListsADTs as a Design ToolSorted ListsJava Code to Insert an Item in a Sorted ListThe sortedList.java ProgramEfficiency of Sorted Linked ListsList Insertion SortDoubly Linked ListsTraversalInsertionDeletionThe doublyLinked.java ProgramDoubly Linked List as Basis for DequesIteratorsA Reference in the List Itself?An Iterator ClassAdditional Iterator FeaturesIterator MethodsThe interIterator.java ProgramWhere Does the Iterator Point?The atEnd() MethodIterative OperationsOther MethodsSummaryQuestionsExperimentsProgramming Projects
Triangular NumbersFinding the nth Term Using a LoopFinding the nth Term Using RecursionThe triangle.java ProgramWhat’s Really Happening?Characteristics of Recursive MethodsIs Recursion Efficient?Mathematical InductionFactorialsAnagramsA Recursive Binary SearchRecursion Replaces the LoopDivide-and-Conquer AlgorithmsThe Towers of HanoiThe Towers Workshop AppletMoving SubtreesThe Recursive AlgorithmThe towers.java ProgrammergesortMerging Two Sorted ArraysSorting by MergingThe MergeSort Workshop AppletThe mergeSort.java ProgramEfficiency of the mergesortEliminating RecursionRecursion and StacksSimulating a Recursive MethodWhat Does This Prove?Some Interesting Recursive ApplicationsRaising a Number to a PowerThe Knapsack ProblemCombinations: Picking a TeamSummaryQuestionsExperimentsProgramming Projects
ShellsortInsertion Sort: Too Many CopiesN-SortingDiminishing GapsThe Shellsort Workshop AppletJava Code for the ShellsortOther Interval SequencesEfficiency of the ShellsortPartitioningThe Partition Workshop AppletThe partition.java ProgramThe Partition AlgorithmEfficiency of the Partition AlgorithmQuicksortThe Quicksort AlgorithmChoosing a Pivot ValueThe QuickSort1 Workshop AppletDegenerates to O(N2) PerformanceMedian-of-Three PartitioningHandling Small PartitionsRemoving RecursionEfficiency of QuicksortRadix SortAlgorithm for the Radix SortDesigning a ProgramEfficiency of the Radix SortSummaryQuestionsExperimentsProgramming Projects
Why Use Binary Trees?Slow Insertion in an Ordered ArraySlow Searching in a Linked ListTrees to the RescueWhat Is a Tree?Tree TerminologyPathRootParentChildLeafSubtreeVisitingTraversingLevelsKeysBinary TreesAn AnalogyHow Do Binary Search Trees Work?The Binary Tree Workshop AppletRepresenting the Tree in Java CodeFinding a NodeUsing the Workshop Applet to Find a NodeJava Code for Finding a NodeTree EfficiencyInserting a NodeUsing the Workshop Applet to Insert a NodeJava Code for Inserting a NodeTraversing the TreeInorder TraversalJava Code for TraversingTraversing a Three-Node TreeTraversing with the Workshop AppletPreorder and Postorder TraversalsFinding Maximum and Minimum ValuesDeleting a NodeCase 1: The Node to Be Deleted Has No ChildrenCase 2: The Node to Be Deleted Has One ChildCase 3: The Node to Be Deleted Has Two ChildrenThe Efficiency of Binary TreesTrees Represented as ArraysDuplicate KeysThe Complete tree.java ProgramThe Huffman CodeCharacter CodesDecoding with the Huffman TreeCreating the Huffman TreeCoding the MessageCreating the Huffman CodeSummaryQuestionsExperimentsProgramming Projects
Our Approach to the DiscussionConceptualTop-Down InsertionBalanced and Unbalanced TreesDegenerates to O(N)Balance to the RescueRed-Black Tree CharacteristicsFixing Rule ViolationsUsing the RBTree Workshop AppletClicking on a NodeThe Start ButtonThe Ins ButtonThe Del ButtonThe Flip ButtonThe RoL ButtonThe RoR ButtonThe R/B ButtonText MessagesWhere’s the Find Button?Experimenting with the Workshop AppletExperiment 1: Inserting Two Red NodesExperiment 2: RotationsExperiment 3: Color FlipsExperiment 4: An Unbalanced TreeMore ExperimentsThe Red-Black Rules and Balanced TreesNull ChildrenRotationsSimple RotationsThe Weird Crossover NodeSubtrees on the MoveHuman Beings Versus ComputersInserting a New NodePreview of the Insertion ProcessColor Flips on the Way DownRotations After the Node Is InsertedRotations on the Way DownDeletionThe Efficiency of Red-Black TreesRed-Black Tree ImplementationOther Balanced TreesSummaryQuestionsExperiments
Introduction to 2-3-4 TreesWhat’s in a Name?2-3-4 Tree OrganizationSearching a 2-3-4 TreeInsertionNode SplitsSplitting the RootSplitting on the Way DownThe Tree234 Workshop AppletThe Fill ButtonThe Find ButtonThe Ins ButtonThe Zoom ButtonViewing Different NodesExperimentsJava Code for a 2-3-4 TreeThe DataItem ClassThe Node ClassThe Tree234 ClassThe Tree234App ClassThe Complete tree234.java Program2-3-4 Trees and Red-Black TreesTransformation from 2-3-4 to Red-BlackOperational EquivalenceEfficiency of 2-3-4 TreesSpeedStorage Requirements2-3 TreesNode SplitsImplementationExternal StorageAccessing External DataSequential OrderingB-TreesIndexingComplex Search CriteriaSorting External FilesSummaryQuestionsExperimentsProgramming Projects
Introduction to HashingEmployee Numbers as KeysA DictionaryHashingCollisionsOpen AddressingLinear ProbingJava Code for a Linear Probe Hash TableQuadratic ProbingDouble HashingSeparate ChainingThe HashChain Workshop AppletJava Code for Separate ChainingHash FunctionsQuick ComputationRandom KeysNon-Random KeysHashing StringsFoldingHashing EfficiencyOpen AddressingSeparate ChainingOpen Addressing Versus Separate ChainingHashing and External StorageTable of File PointersNon-Full BlocksFull BlocksSummaryQuestionsExperimentsProgramming Projects
Introduction to HeapsPriority Queues, Heaps, and ADTsWeakly OrderedRemovalInsertionNot Really SwappedThe Heap Workshop AppletThe Fill ButtonThe Change ButtonThe Remove ButtonThe Insert ButtonJava Code for HeapsInsertionRemovalKey ChangeThe Array SizeThe heap.java ProgramExpanding the Heap ArrayEfficiency of Heap OperationsA Tree-based HeapHeapsortTrickling Down in PlaceUsing the Same ArrayThe heapSort.java ProgramThe Efficiency of HeapsortSummaryQuestionsExperimentsProgramming Projects
Introduction to GraphsDefinitionsHistorical NoteRepresenting a Graph in a ProgramAdding Vertices and Edges to a GraphThe Graph ClassSearchesDepth-First SearchBreadth-First SearchMinimum Spanning TreesGraphN Workshop AppletJava Code for the Minimum Spanning TreeThe mst.java ProgramTopological Sorting with Directed GraphsAn Example: Course PrerequisitesDirected GraphsTopological SortingThe GraphD Workshop AppletCycles and TreesJava CodeConnectivity in Directed GraphsThe Connectivity TableWarshall’s AlgorithmImplementation of Warshall’s AlgorithmSummaryQuestionsExperimentsProgramming Projects
Minimum Spanning Tree with Weighted GraphsAn Example: Cable TV in the JungleThe GraphW Workshop AppletSend Out the SurveyorsCreating the AlgorithmJava CodeThe mstw.java ProgramThe Shortest-Path ProblemThe Railroad LineDijkstra’s AlgorithmAgents and Train RidesUsing the GraphDW Workshop AppletJava CodeThe path.java ProgramThe All-Pairs Shortest-Path ProblemEfficiencyIntractable ProblemsThe Knight’s TourThe Traveling Salesman ProblemHamiltonian CyclesSummaryQuestionsExperimentsProgramming Projects
General-Purpose Data StructuresSpeed and AlgorithmsLibrariesArraysLinked ListsBinary Search TreesBalanced TreesHash TablesComparing the General-Purpose Storage StructuresSpecial-Purpose Data StructuresStackQueuePriority QueueComparison of Special-Purpose StructuresSortingGraphsExternal StorageSequential StorageIndexed FilesB-treesHashingVirtual MemoryOnward
The Workshop AppletsThe Example ProgramsThe Sun Microsystem’s Software Development KitCommand-line ProgramsSetting the PathViewing the Workshop AppletsOperating the Workshop AppletsRunning the Example ProgramsCompiling the Example ProgramsEditing the Source CodeTerminating the Example ProgramsMultiple Class FilesOther Development Systems
Data Structures and AlgorithmsObject-Oriented Programming LanguagesObject-Oriented Design (OOD) and Software Engineering
Chapter 1, OverviewAnswers to QuestionsChapter 2, ArraysAnswers to QuestionsChapter 3, Simple SortingAnswers to QuestionsChapter 4, Stacks and QueuesAnswers to QuestionsChapter 5, Linked ListsAnswers to QuestionsChapter 6, RecursionAnswers to QuestionsChapter 7, Advanced SortingAnswers to QuestionsChapter 8, Binary TreesAnswers to QuestionsChapter 9, Red-Black TreesAnswers to QuestionsChapter 10, 2-3-4 Trees and External StorageAnswers to QuestionsChapter 11, Hash TablesAnswers to QuestionsChapter 12, HeapsAnswers to QuestionsChapter 13, GraphsAnswers to QuestionsChapter 14, Weighted GraphsAnswers to Questions

Content preview from Data Structures and Algorithms in Java, 2nd Edition

10. 2-3-4 Trees and External Storage

In This Chapter

• Introduction to 2-3-4 Trees

• Java Code for a 2-3-4 Tree

• 2-3-4 Trees and Red-Black Trees

• Efficiency of 2-3-4 Trees

• 2-3 Trees

• External Storage

In a binary tree, each node has one data item and can have up to two children. If we allow more data items and children per node, the result is a multiway tree. 2-3-4 trees, to which we devote the first part of this chapter, are multiway trees that can have up to four children and three data items per node.

2-3-4 trees are interesting for several reasons. First, they’re balanced trees like red-black trees. They’re slightly less efficient than red-black trees but easier to program. Second, and most important, they serve as an easy-to-understand ...