Gain insights into array-based and linked list-based data structures, explore advanced structures like skiplists and hashing, and discover template-based collections for efficient data storage and retrieval.

java.tar.gz

Data structures and algorithms are essential in computer science since they play a crucial role in efficient information retrieval and processing, dealing with files, storing contacts on phones, social networks and web searches.

In this course, you’ll learn about the array-based implementation of various linear data structures, stack, and queues. You’ll also learn about linked list-based implementation. Next, you’ll explore advanced data structures like skiplists and hashing. You’ll learn how to implement a variety of trees and graphs, and data structures related to bits of an integer. Toward the end of the course, you’ll learn the implementation of structures based on external storage.

After completing this course, you’ll be able to create reusable programs with template-based collections that can efficiently analyze how to optimize the storage and retrieval of very large amounts of data. Overall, this course will enhance your productivity and performance as a software developer.

Data Structures with Generic Types in Python

# Additional notes
The term scapegoat tree is due to 
#key# Galperin and Rivest: I. Galperin and R. Rivest. Scapegoat trees. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 165–174. Society for Industrial and Applied Mathematics, 1993. #key#, who defined and analyzed these trees. However, the same structure was discovered earlier by #key# Andersson: A. Andersson. Improving partial rebuilding by using simple balance criteria. In F. K. H. A. Dehne, J.-R. Sack, and N. Santoro, editors, Algorithms and Data Structures, Workshop WADS ’89, Ottawa, Canada, August 17–19, 1989, Proceedings, volume 382 of Lecture Notes in Computer Science, pages 393–402. Springer, 1989. #key#, who called them #key# general balanced trees: A. Andersson. General balanced trees. Journal of Algorithms, 30(1):1–18, 1999. #key# since they can have any shape as long as their height is small.

Experimenting with the `ScapegoatTree` implementation will reveal that it is often considerably slower than the other `SSet` implementations in this course. This may be somewhat surprising, since height bound of

$$
\text{log}_{3/2}
q \approx 1.709\log n + O(1)
$$

is better than the expected length of a search path in a `Skiplist` and not
too far from that of a `Treap`. The implementation could be optimized by
storing the sizes of subtrees explicitly at each node or by reusing already
computed subtree sizes. Even with these optimizations, there will always be sequences of `add(x)` and `delete(x)` operation for which a `ScapegoatTree` takes longer than other `SSet` implementations.

This gap in performance is due to the fact that, unlike the other `SSet`
implementations discussed in this course, a `ScapegoatTree` can spend a lot
of time restructuring itself. There are
sequences of `n` operations in which a `ScapegoatTree` will spend on the order of $n\log n$ time in calls to `rebuild(u)`. This is in contrast to other `SSet` implementations discussed in this book, which only make $O(n)$ structural changes during a sequence of `n` operations. This is, unfortunately, a necessary consequence of the fact that a `ScapegoatTree` does all its #key# restructuring: P. Dietz and J. Zhang. Lower bounds for monotonic list labeling. In J. R. Gilbert and R. G. Karlsson, editors, SWAT 90, 2nd Scandi- navian Workshop on Algorithm Theory, Bergen, Norway, July 11–14, 1990, Proceedings, volume 447 of Lecture Notes in Computer Science, pages 173–180. Springer, 1990. #key# by calls to `rebuild(u)`.



Discover more aspects regarding scapegoat trees.

Overview

Array-Based Lists

Linked Lists

Skiplists

Hash Tables

Binary Trees

Random Binary Search Trees

Scapegoat Trees

Red-Black Trees

Heaps

Sorting Algorithms

Graphs

Data Structures for Integers

External Memory Searching

Wrap Up

Discussion on Scapegoat Trees