Gain insights into implementing array-based and linked list data structures, explore advanced structures like skiplists, hashing, and graphs, and learn reusable, template-based collections for efficient data analysis.

java.tar.gz

Java

Java-1

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 Java

So far, we've established that:

1. In the external memory model, the running time of `find(x)`, `add(x)`,
and `remove(x)` in a $B$-tree is $O(\log_Bn)$.
2. In the word-RAM model, the running time of `find(x)` is $O(\log n)$, and the running time of `add(x)` and `remove(x)` is $O(B\log n)$.


The following lemma, however, shows that we have overestimated the number of merge and split operations performed by $B$-trees.

**Lemma 1:** Starting with an empty $B$-tree and performing any sequence
of $m$ `add(x)` and `remove(x)` operations results in at most $3m/2$ splits, merges,
and borrows being performed.

**Proof:** The proof of this has already been sketched for the
special case in which $B = 2$. The lemma can be proven using a credit
scheme, in which

1. Each split, merge, or borrow operation is paid for with two credits, i.e., a credit is removed each time one of these operations occurs; and
2. At most three credits are created during any `add(x)` or `remove(x)`
operation.

Since at most $3m$ credits are ever created and each split, merge, and borrow is paid for with two credits, it follows that at most $3m/2$ splits,
merges, and borrows are performed. These credits are illustrated using
the $¢$ symbol.

To keep track of these credits, the proof maintains the following _credit
invariant_: Any non-root node with $B − 1$ keys stores one credit, and any
node with $2B − 1$ keys stores three credits. A node that stores at least $B$ keys and most $2B − 2$ keys doesn't need to store any credits. What remains is to show that we can maintain the credit invariant and satisfy properties $1$
and $2$, above, during each `add(x)` and `remove(x)` operation.


## Adding

The `add(x)` method does not perform any merges or borrows, so we only need to consider the split operations that occur as a result of calls to
`add(x)`.

Each split operation occurs because a key is added to a node, `u`, that
already contains $2B−1$ keys. When this happens, `u` is split into two nodes,
`u'` and `u''` having $B − 1$ and $B$ keys, respectively. Prior to this operation, `u` was storing $2B − 1$ keys, and hence three credits. Two of these credits can be used to pay for the split and the other credit can be given to `u'`
(which has $B−1$ keys) to maintain the credit invariant. Therefore, we can pay for the split and maintain the credit invariant during any split.



The only other modification to nodes that occur during an `add(x)` operation happens after all splits, if any, are complete. This modification involves adding a new key to some node `u'`. If, prior to this, `u'` had $2B−2$ children, then it now has $2B−1$ children and must therefore receive three credits. These are the only credits given out by the `add(x)` method.



## Removing

During a call to `remove(x)`, zero or more merges occur and are possibly followed by a single borrow. Each merge occurs because two nodes, `v` and `w`, each of which had exactly $B − 1$ keys prior to calling `remove(x)`, were merged into a single node with exactly $2B−2$ keys. Each such merge, therefore, frees up two credits that can be used to pay for the merge.

After any merges are performed, at most one borrow operation occurs, after which no further merges or borrows occur. This borrow operation only occurs if we remove a key from a leaf, `v`, that has $B − 1$ keys. The node `v` therefore has one credit, and this credit goes toward the cost of the borrow operation. This single credit is not enough to pay for the borrow operation, so we create one credit to complete the payment.


At this point, we have created one credit and we still need to show that the credit invariant can be maintained. In the worst case, `v`’s sibling, `w`, has exactly $B$ keys before the borrow operation so that, afterward, both `v` and `w` have $B−1$ keys. This means that `v` and `w` each should be storing a credit when the operation is complete. Therefore, in this case, we create additional two credits to give to `v` and `w`. Since a borrow operation happens at most once during a `remove(x)` operation, this means that we create at most three credits, as required.



If the `remove(x)` operation does not include a borrow operation, this
is because it finishes by removing a key from some node that, prior to the
operation, had $B$ or more keys. In the worst case, this node had exactly $B$
keys, so that it now has $B−1$ keys and must be given one credit, which we create.


In either case—whether the removal finishes with a borrow operation
or not—at most three credits need to be created during a call to `remove(x)` to maintain the credit invariant and pay for all borrows and merges that occur. This completes the proof of the lemma.


The purpose of Lemma 1 is to show that, in the word-RAM model, the cost of splits, merges, and joins during a sequence of $m$ `add(x)` and `remove(x)` operations is only $O(Bm)$. That is, the amortized cost per operation is only $O(B)$, so the amortized cost of `add(x)` and `remove(x)` in the word-RAM model is $O(B + \log n)$. This is summarized by the following pair of theorems:



**Theorem 1:** (External Memory $B$-Trees) A `BTree` implements the `SSet`
interface. In the external memory model, a `BTree` supports the operations
`add(x)`, `remove(x)`, and `find(x)` in $O(\log_Bn)$ time per operation.

**Theorem 2:** (Word-RAM $B$-Trees) A `BTree` implements the `SSet` interface. In the word-RAM model, and ignoring the cost of splits, merges, and borrows, a `BTree` supports the operations `add(x)`, `remove(x)`, and `find(x)` in $O(\log n)$ time per operation. Furthermore, beginning with an empty `BTree`, any sequence of $m$ `add(x)` and `remove(x)` operations results in a total of $O(Bm)$ time spent performing splits, merges, and borrows.

So far, we've established that:

1. In the external memory model, the running time of `find(x)`, `add(x)`,
and `remove(x)` in a $B$-tree is $O(\log_Bn)$.
2. In the word-RAM model, the running time of `find(x)` is $O(\log n)$, and the running time of `add(x)` and `remove(x)` is $O(B\log n)$.


The following lemma, however, shows that we have overestimated the number of merge and split operations performed by $B$-trees.

**Lemma 1:** Starting with an empty $B$-tree and performing any sequence
of $m$ `add(x)` and `remove(x)` operations results in at most $3m/2$ splits, merges,
and borrows being performed.

**Proof:** The proof of this has already been sketched for the
special case in which $B = 2$. The lemma can be proven using a credit
scheme, in which

1. Each split, merge, or borrow operation is paid for with two credits, i.e., a credit is removed each time one of these operations occurs; and
2. At most three credits are created during any `add(x)` or `remove(x)`
operation.

Since at most $3m$ credits are ever created and each split, merge, and borrow is paid for with two credits, it follows that at most $3m/2$ splits,
merges, and borrows are performed. These credits are illustrated using
the $¢$ symbol.

To keep track of these credits, the proof maintains the following _credit
invariant_: Any non-root node with $B − 1$ keys stores one credit, and any
node with $2B − 1$ keys stores three credits. A node that stores at least $B$ keys and most $2B − 2$ keys doesn't need to store any credits. What remains is to show that we can maintain the credit invariant and satisfy properties $1$
and $2$, above, during each `add(x)` and `remove(x)` operation.


# Adding

The `add(x)` method does not perform any merges or borrows, so we only need to consider the split operations that occur as a result of calls to
`add(x)`.

Each split operation occurs because a key is added to a node, `u`, that
already contains $2B−1$ keys. When this happens, `u` is split into two nodes,
`u'` and `u''` having $B − 1$ and $B$ keys, respectively. Prior to this operation, `u` was storing $2B − 1$ keys, and hence three credits. Two of these credits can be used to pay for the split and the other credit can be given to `u'`
(which has $B−1$ keys) to maintain the credit invariant. Therefore, we can pay for the split and maintain the credit invariant during any split.



The only other modification to nodes that occur during an `add(x)` operation happens after all splits, if any, are complete. This modification involves adding a new key to some node `u'`. If, prior to this, `u'` had $2B−2$ children, then it now has $2B−1$ children and must therefore receive three credits. These are the only credits given out by the `add(x)` method.



# Removing

During a call to `remove(x)`, zero or more merges occur and are possibly followed by a single borrow. Each merge occurs because two nodes, `v` and `w`, each of which had exactly $B − 1$ keys prior to calling `remove(x)`, were merged into a single node with exactly $2B−2$ keys. Each such merge, therefore, frees up two credits that can be used to pay for the merge.

After any merges are performed, at most one borrow operation occurs, after which no further merges or borrows occur. This borrow operation only occurs if we remove a key from a leaf, `v`, that has $B − 1$ keys. The node `v` therefore has one credit, and this credit goes toward the cost of the borrow operation. This single credit is not enough to pay for the borrow operation, so we create one credit to complete the payment.


At this point, we have created one credit and we still need to show that the credit invariant can be maintained. In the worst case, `v`’s sibling, `w`, has exactly $B$ keys before the borrow operation so that, afterward, both `v` and `w` have $B−1$ keys. This means that `v` and `w` each should be storing a credit when the operation is complete. Therefore, in this case, we create additional two credits to give to `v` and `w`. Since a borrow operation happens at most once during a `remove(x)` operation, this means that we create at most three credits, as required.



If the `remove(x)` operation does not include a borrow operation, this
is because it finishes by removing a key from some node that, prior to the
operation, had $B$ or more keys. In the worst case, this node had exactly $B$
keys, so that it now has $B−1$ keys and must be given one credit, which we create.


In either case—whether the removal finishes with a borrow operation
or not—at most three credits need to be created during a call to `remove(x)` to maintain the credit invariant and pay for all borrows and merges that occur. This completes the proof of the lemma.


The purpose of Lemma 1 is to show that, in the word-RAM model, the cost of splits, merges, and joins during a sequence of $m$ `add(x)` and `remove(x)` operations is only $O(Bm)$. That is, the amortized cost per operation is only $O(B)$, so the amortized cost of `add(x)` and `remove(x)` in the word-RAM model is $O(B + \log n)$. This is summarized by the following pair of theorems:



**Theorem 1:** (External Memory $B$-Trees) A `BTree` implements the `SSet`
interface. In the external memory model, a `BTree` supports the operations
`add(x)`, `remove(x)`, and `find(x)` in $O(\log_Bn)$ time per operation.

**Theorem 2:** (Word-RAM $B$-Trees) A `BTree` implements the `SSet` interface. In the word-RAM model, and ignoring the cost of splits, merges, and borrows, a `BTree` supports the operations `add(x)`, `remove(x)`, and `find(x)` in $O(\log n)$ time per operation. Furthermore, beginning with an empty `BTree`, any sequence of $m$ `add(x)` and `remove(x)` operations results in a total of $O(Bm)$ time spent performing splits, merges, and borrows.

This lesson is about analysis of the B-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

Analysis of B-Trees