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

# Red-black trees and 2-4 trees

At first it might seem surprising that a red-black tree can be efficiently
updated to maintain the black-height and no-red-edge properties, and
it seems unusual to even consider these as useful properties. However, red-black trees were designed to be an efficient simulation of 2-4 trees as binary trees.


Refer to the below figure:

Consider any red-black tree, $T$, having `n` nodes and perform the following transformation: Remove each red node `u` and connect `u`'s two children directly to the (black) parent of `u`. After this
transformation, we are left with a tree $T’$ having only black nodes.

Every internal node in $T’$ has two, three, or four children: A black
node that started out with two black children will still have two black
children after this transformation. A black node that started out with
one red and one black child will have three children after this transformation. A black node that started out with two red children will have
four children after this transformation. Furthermore, the black-height
property now guarantees that every root-to-leaf path in $T’$ has the same
length. In other words, $T’$
is a 2-4 tree!

The 2-4 tree $T’$ has $n + 1$ leaves that correspond to the $n + 1$ external
nodes of the red-black tree. Therefore, this tree has height at most $\log(n+
1).$ Now, every root to leaf path in the 2-4 tree corresponds to a path
from the root of the red-black tree $T$ to an external node. The first and
last node in this path are black and at most one out of every two internal
nodes is red, so this path has at most $\log(n + 1)$ black nodes and at most
$\log(n + 1) − 1$ red nodes. Therefore, the longest path from the root to any
internal node in $T$ is at most

$$
2 \log(n + 1) − 2 \leq 2 \log n 
$$

for any $n \geq 1$. This proves the most important property of red-black trees:

Learn subroutines of red-black trees and their relation with 2-4 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

Fundamentals of Red-Black Trees

Red-black trees and 2-4 trees