Red-Black Trees

Table of contents:

Projects

14.22

Implement a priority queue using an OrderedLinkedList instead of a heap. Give the worst-case running time of each of your methods.

14.23

After doing Problem 14.21, rewrite the Heap class to handle only heaps of doubles. Use an array rather than an ArrayList. Your implementation of heapsort should be in place. (Hint: Recall Figure 8-7.)

14.24

Write a DisjointSetCluster class that uses an ArrayList of Sets instead of the up-tree data structure described in Section 14.2. Provide the methods inSameSet() and mergeSets(). What is the running time of these operation?

14.25

Suppose Figure 14-23 is the entire digital search tree for a game of Ghost. If your opponent starts the game with 'g,' why is 'r' not a wise response? Modify the program to take advantage of this information.


Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting

Recursion

Part IV: Trees and Sets

Trees

Sets

Part V: Advanced Topics

Advanced Linear Structures

Strings

Advanced Trees

Graphs

Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading

Index



Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake

Flylib.com © 2008-2020.
If you may any questions please contact us: flylib@qtcs.net