---
title: 'Data Structures'
source: 'https://academia.sh/en/courses/data-structures'
language: en
updated: '2026-08-17T04:39:30+00:00'
license: 'CC BY-SA 4.0'
lessons: 26
outcomes:
    - 'Compares the memory layout and the operation cost of linear and linked data structures'
    - 'Selects the data structure suited to a problem and justifies the choice by cost'
    - 'Uses tree and graph structures together with their traversal algorithms'
---

# Data Structures

An intermediate course that establishes the relation between the layout of data in memory and the cost of operations, from linear structures to trees and graphs.

## Linear Structures

Arrays, linked lists, stacks, queues, and skip lists; the consequences of contiguous and linked layout.

### Arrays

Source: https://academia.sh/en/courses/data-structures/arrays

Contiguous memory layout, constant-time access through address arithmetic, the fixed-size constraint, and the language of cost.

In the Programming Fundamentals course, lists were used: elements were added,
traversed, filtered. What these operations correspond to in memory, and why some are
more expensive than others, was left open.

This course fills that gap. Its question is: depending on how data is arranged in
memory, which operation is cheap and which is expensive? The answer always comes from
the same two sources — the memory model established in the How Computers Work course,
and the structure's own layout.

#### Contiguous Layout

An **array** is a structure that keeps elements of the same type **contiguous** in
memory. If the address of the first element is known, the addresses of the rest can be
computed:

$$
\text{address}(i) = \text{base} + i \times \text{element size}
$$

If an array of four-byte integers starts at address `1000`, the address of the element at
index `3` — the fourth one — is $1000 + 3 \times 4 = 1012$. The calculation is a single
multiplication and a single addition; it is independent of the array's length.

This is the array's distinguishing property: **any element can be accessed directly,
given its index.** Reaching the fifth element does not require passing through the
previous four.

The layout's second consequence is that the array carries elements of a single type.
Address arithmetic relies on elements being of equal size; if elements of different
sizes were arranged contiguously, the location of the $i$-th element could not be
computed and would have to be searched for.

#### The Language of Cost

Throughout this course, the cost of operations will be compared. Three expressions
suffice for the comparison; their formal definitions are given in the **Algorithms**
course.

- **Constant time**, $O(1)$: The duration of the work is independent of the data's
  size. Access to the array's $i$-th element is like this.
- **Linear time**, $O(n)$: The duration grows in proportion to the number of elements.
  Scanning an array from start to end is like this.
- **Logarithmic time**, $O(\log n)$: At each step, the search space shrinks by a fixed
  ratio. Binary search in a sorted array is like this.

The notation ignores constant factors and lower-order terms; what it measures is **the
rate at which** cost grows as data grows.

#### The Cost of Array Operations

| Operation | Cost | Reason |
|---|---|---|
| Access to the $i$-th element | $O(1)$ | Address arithmetic |
| Search in an unsorted array | $O(n)$ | All elements in the worst case |
| Search in a sorted array | $O(\log n)$ | The range halves at each step |
| Insertion at the end (if room exists) | $O(1)$ | A single write |
| Insertion at the start or middle | $O(n)$ | Shifting the following elements |
| Deletion from the middle | $O(n)$ | Closing the gap |

Insertion and deletion being expensive is the direct cost of contiguous layout.
Inserting an element at the start of a five-element array requires moving each of the
existing five elements one position forward; the layout must stay contiguous, because
address arithmetic depends on it.

```python
def insert_at_start(array: list[int], value: int) -> int:
    """Shifts the array by one position to insert at the start; returns the count of elements shifted."""
    array.append(None)                      # open room at the end
    shifted = 0
    for i in range(len(array) - 1, 0, -1):  # shift from the end toward the start
        array[i] = array[i - 1]
        shifted += 1
    array[0] = value
    return shifted


measurements = [12, 18, 7, 25, 14]
print(insert_at_start(measurements, 30))    # 5     — five elements shifted
print(measurements)                         # [30, 12, 18, 7, 25, 14]
```

The number of shifts equals the length of the array; this is the $O(n)$ row from the
table shown as an actual count.

#### The Fixed-Size Constraint

A classic array is a memory block whose size is fixed at the moment it is created.
Because the block is contiguous, growing it afterward is generally not possible: the
memory immediately following the array may already be in use by other data.

This constraint has two consequences. An array allocated larger than needed wastes
memory; one allocated too small becomes unusable once it fills up. If how many
elements the program will hold is not known in advance, a fixed-size array is not a
direct solution.

The next lesson's subject is exactly how this constraint is overcome.

#### Bounds Checking

Address arithmetic assumes that the given index is valid. If the index is out of
range, the computed address points to a memory location outside the array.

Languages respond to this in two different ways. **Languages that check** compare the
index against the bound on every access and raise an error on overrun; the cost is a
few instructions per access. **Languages that do not check** apply the calculation
directly; access is at its fastest, but an out-of-range index leads to reading or
overwriting neighboring data.

The second behavior came up under the heading of undefined behavior in the How
Computers Work course. Its result is not only a wrong value: writing past the end of
an array can corrupt the return address in a stack frame. This is the best-known class
of memory safety vulnerabilities and is treated separately in the Cybersecurity
curriculum.

#### Multidimensional Arrays

A two-dimensional array also sits one-dimensionally in memory; rows are placed one
after another. This is called **row-major order**, and the index calculation is:

$$
\text{position}(i, j) = i \times \text{column count} + j
$$

```python
COLUMNS = 4
flat = [0] * (3 * COLUMNS)        # a 3-row, 4-column table in a single array

def write(i: int, j: int, value: int) -> None:
    flat[i * COLUMNS + j] = value

def read(i: int, j: int) -> int:
    return flat[i * COLUMNS + j]

write(1, 2, 99)
print(read(1, 2), flat)           # 99 [0, 0, 0, 0, 0, 0, 99, 0, 0, 0, 0, 0]
```

The value `99` sitting at index `6` ($1 \times 4 + 2$) in the flat array shows how
two dimensions are reduced to one.

This layout's performance consequence was calculated in the cache lesson of the How
Computers Work course: traversing along a row reads consecutive addresses, while
traversing along a column skips a row's length at every step. For the same number of
additions, the amount of data moved differs by as much as the number of elements that
fit in a cache line.

#### Why Arrays Are Common

Despite the array's high insertion and deletion costs, there are three reasons it is
the most commonly used structure in practice.

**Access cost is the lowest.** It is constant time and as cheap as a single address
calculation.

**Cache behavior is the best.** Contiguous layout is the arrangement that benefits
most from spatial locality; when one element is fetched, its neighbors enter the cache
too.

**It takes no extra space.** Unlike linked structures, no pointer is stored per
element.

For these three reasons, the default answer to the "which structure" question is the
array; another structure is chosen only when an operation the array is weak at
dominates. The rest of this course shows what those situations are and which
structure reduces which cost.

#### Cost Table

Throughout the course, the table below will grow row by row. The first row is this
lesson's result:

| Structure | Access | Search | Insert at start | Insert at end | Delete from middle |
|---|---|---|---|---|---|
| Array (fixed size) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ |

\* As long as room remains; once the array is full, insertion is not possible.

#### Summary

- An array keeps elements of the same type contiguous; the address of the $i$-th
  element is computed from the base address and the element size.
- Because this calculation is independent of the array's length, access is constant
  time.
- Insertion and deletion require shifting elements to preserve contiguity, and are
  linear time.
- The fixed-size constraint arises from the fact that a contiguous block cannot be
  grown afterward.
- Multidimensional arrays sit one-dimensionally in memory; row-major order causes the
  direction of traversal to determine cache behavior.
- Because of its access cost, cache compatibility, and lack of extra space, the array
  is the default choice.

#### Next Step

The fixed-size constraint makes the array unusable in problems where the number of
elements is not known in advance. The next lesson will lift this constraint with a
solution based on moving the array, and show why that solution's cost is not as high
as it looks — through the concept of amortized cost.

### Dynamic Arrays

Source: https://academia.sh/en/courses/data-structures/dynamic-arrays

Capacity growth, the choice of growth factor, amortized cost analysis, and the shrink threshold.

The previous lesson established that an array is a fixed-size contiguous block, and
that this block cannot be grown afterward. When the number of elements is not known in
advance, this constraint is binding.

The solution is not to eliminate the constraint but to live with it: when the array
fills up, a new, larger array is allocated, the old elements are copied into it, and
the old block is released. This structure is called a **dynamic array**.

#### Capacity and Length

A dynamic array holds two numbers:

- **Length:** The actual number of elements it contains.
- **Capacity:** The maximum number of elements the allocated block can hold.

Capacity is always equal to or greater than length. The difference between them is
space that is allocated but not yet used; appending is cheap as long as it uses this
room.

When length reaches capacity, **reallocation** is required: a new and larger block is
allocated, and all elements are copied. Copying is proportional to the number of
elements — that is, $O(n)$.

#### The Growth Factor

The critical question is: how large should the new capacity be?

**Growing by a fixed amount** — adding a constant number to capacity each time — is a
poor choice. If capacity increased one at a time, the total copying done to insert $n$
elements would be:

$$
1 + 2 + 3 + \dots + (n-1) = \frac{n(n-1)}{2}
$$

This means $O(n^2)$: inserting a thousand elements does approximately half a million
copies.

**Growing by doubling** — multiplying capacity by a factor (commonly two) each time —
changes the total cost fundamentally. If capacity starts at $1$ and doubles, the total
of the copies made until $n$ elements are reached is:

$$
1 + 2 + 4 + \dots + \frac{n}{2} < n
$$

The geometric sum itself is less than twice the last term. When $n$ is not an exact power
of two the capacity climbs to the next power and the total can slightly exceed $n$ — 1023
copies for a thousand elements — but it always stays below $2n$; the average cost per
insertion is **constant**.

#### Amortized Cost

This observation calls for a concept. Looked at individually, most append operations
are $O(1)$, some are $O(n)$; the worst-case cost is linear.

But expensive operations are rare, and because capacity doubles after every expensive
operation, twice as many cheap operations happen before the next expensive one. The
value obtained by dividing the **total** cost of a sequence of operations by the
number of operations is called the **amortized cost**.

In a dynamic array, the amortized cost of appending is $O(1)$. This does not mean
"every append takes constant time"; it means "$n$ appends together take $O(n)$." The
distinction matters in latency-sensitive systems: it must be known that any single
append can take a long time.

```python
class DynamicArray:
    """An array that grows by doubling its capacity."""

    def __init__(self) -> None:
        self._block: list = [None]     # capacity starts at 1
        self._length = 0
        self.copies = 0                # counter for measurement

    def __len__(self) -> int:
        return self._length

    def capacity(self) -> int:
        return len(self._block)

    def append(self, value: int) -> None:
        if self._length == self.capacity():
            self._grow()
        self._block[self._length] = value
        self._length += 1

    def _grow(self) -> None:
        new_block = [None] * (self.capacity() * 2)
        for i in range(self._length):          # each element is moved to the new block
            new_block[i] = self._block[i]
            self.copies += 1
        self._block = new_block

    def __getitem__(self, i: int) -> int:
        if not 0 <= i < self._length:
            raise IndexError("index out of range")
        return self._block[i]


array = DynamicArray()
for value in range(16):
    array.append(value)

print(len(array), array.capacity())    # 16 16
print(array.copies)                    # 15    — total copies, fewer than the element count
print(array[3])                        # 3
```

The number of copies made for sixteen appends is $1 + 2 + 4 + 8 = 15$. That is less
than one copy per append on average; the bound given by the geometric sum is confirmed
by the count.

This count is the simplest form of amortized analysis: alongside its own cost, every
append sets aside a share for future copying; when reallocation comes, these
accumulated shares cover the cost.

The factor does not have to be two. A smaller factor (for example, $1.5$) leaves less
empty room but copies more often; a larger factor does the opposite. In both cases the
amortized cost stays constant — what changes is the size of the constant factor.

#### Preallocation

If the number of elements is known in advance, growth may never happen at all. Most
dynamic array implementations offer an operation that lets capacity be set up front.

The gain is twofold. Reallocation and copying disappear entirely; and because the
allocated block is a single piece, memory fragmentation is reduced. If it is known
that a result of a thousand elements will be produced, giving capacity a thousand up
front prevents ten reallocations.

```python
result = []
# When capacity is known up front, the language's preallocation facility is used.
# Without preallocation, producing the result directly at its target size does the same job:
ready = [0] * 1000                      # a single allocation, no copying
for i in range(1000):
    ready[i] = i * 3
print(len(ready), ready[999])           # 1000 2997
```

This is not premature optimization: when the final size is known, preallocation also
improves the code's readability — the intent is written explicitly.

#### Shrinking and Oscillation

When elements are removed, capacity is expected to shrink as well; otherwise an array
that has once grown never releases memory.

The shrink threshold must be chosen with care. If capacity is halved as soon as length
drops to half of capacity, **oscillation** results: with the array right at that
boundary, an append followed by a delete, repeated, triggers reallocation every single
time. Every operation becomes $O(n)$ and the amortized gain disappears.

The standard solution is to separate the thresholds: capacity doubles when it fills
up, but is halved only when length drops to **one quarter** of capacity. The gap
between the two prevents operations that go back and forth near the boundary from
triggering reallocation.

#### The Counterpart in Real Languages

Most languages' standard "list" or "vector" structure is a dynamic array. Appending at
the end is amortized constant, inserting at the start is linear; this asymmetry
determines which end is used when writing code.

One detail is what is actually stored. Fixed-width types can be kept directly in the
block; when object references are stored instead, the block carries pointers and the
real values sit scattered on the heap. The second arrangement offers flexibility and
lowers cache compatibility. The contiguous layout discussion in the How Computers Work
course covered this distinction.

#### Cost Table

| Structure | Access | Search | Insert at start | Insert at end | Delete from middle |
|---|---|---|---|---|---|
| Array (fixed size) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ |
| Dynamic array | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ amortized | $O(n)$ |

\* As long as room remains.

#### Summary

- A dynamic array overcomes the fixed-size constraint by allocating a larger block and
  copying elements over when it fills up.
- Capacity denotes allocated room; length denotes the actual number of elements.
- Growing by a fixed amount makes the total cost $O(n^2)$; under doubling growth, the
  total copying is less than $n$.
- Amortized cost is the total cost of a sequence of operations divided by the number
  of operations; the amortized cost of appending is constant, though the cost of any
  single append is not.
- The shrink threshold is chosen separately from the growth threshold; otherwise
  operations at the boundary produce oscillation.

#### Next Step

The dynamic array made appending cheap, but inserting at the start or middle is still
linear. The source of the shifting cost was contiguous layout. The next lesson takes
up a structure that abandons contiguity entirely — the linked list — and what this
trade-off gains and loses.

### Linked Lists

Source: https://academia.sh/en/courses/data-structures/linked-lists

Node and link structure, singly and doubly linked lists, the cost of pointer relinking, and their practical limits.

An array's insertion and deletion cost arose from a single requirement: elements
staying contiguous. If contiguity is abandoned, shifting disappears with it.

A **linked list** makes this trade-off. Elements sit wherever they like in memory;
order is established by each element carrying the address of the next one.

#### Node and Link

The structure's unit is the **node**: a value and the address of the next node.

```
head → [12 | •] → [18 | •] → [7 | •] → [25 | ⏚]
```

The last node's link is empty; this emptiness marks the end of the list. The list
itself is represented by a single thing: the address of the first node, that is, the
**head**.

Address arithmetic does not apply here. Where the third element is cannot be computed;
two links must be followed starting from the head. This means losing the array's
constant-time access: in a linked list, access to the $i$-th element is $O(n)$.

```python
class Node:
    """A value and the link to the next node."""

    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


class LinkedList:
    def __init__(self) -> None:
        self.head: Node | None = None
        self.length = 0

    def prepend(self, value: int) -> None:
        """Links the new node at the head: constant time."""
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        self.length += 1

    def find(self, value: int) -> int:
        """Returns the value's index; -1 if absent. Takes as many steps as the links followed."""
        index = 0
        node = self.head
        while node is not None:
            if node.value == value:
                return index
            node = node.next
            index += 1
        return -1

    def values(self) -> list[int]:
        result = []
        node = self.head
        while node is not None:
            result.append(node.value)
            node = node.next
        return result


linked_list = LinkedList()
for measurement in (25, 7, 18, 12):    # inserted in reverse order
    linked_list.prepend(measurement)

print(linked_list.values())                        # [12, 18, 7, 25]
print(linked_list.find(7), linked_list.find(99))    # 2 -1
print(linked_list.length)                           # 4
```

Prepending is constant time: two links are written, no element is moved. The same
operation shifted every element in an array.

#### Locating Versus Linking

The most commonly misunderstood aspect of the linked list is this: **insertion and
deletion are cheap, but locating the position is expensive.**

If a node reference is already in hand, inserting after it is a few pointer writes —
$O(1)$. But if the request is "insert after the tenth element," nine links must be
followed first; the total cost is $O(n)$ after all.

This distinction determines the linked list's proper use: the structure pays off if
the reference to the relevant node is already held; it does not if every operation
searches from the head.

#### Doubly Linked List

Deleting a node in a singly linked list requires changing the **previous** node's
link, yet there is no way to go backward from the node. The solution is to add a
back-link to every node as well.

In a **doubly linked list**, every node knows both its next and its previous.
Consequences:

- Deletion is $O(1)$ when a node reference is already in hand.
- The list can be traversed in either direction.
- Every node carries one more pointer; memory overhead increases.
- Every insertion and deletion updates four links instead of two; the code is more
  error-prone.

If both head and tail pointers are kept, insertion at either end of the list becomes
constant time. This is the natural foundation of the stack and queue structures in the
next two lessons.

A third variant is the **circular list**, in which the last node links back to the
head; it is used in scheduling and buffering applications that keep cycling to the
next item.

#### Sentinel Node

The source of errors in linked list code is edge cases: inserting into an empty list,
deleting the first node, inserting after the last node. Each requires a separate `if`
block, and when one of these blocks is forgotten, the bug shows up only in that
specific case.

A **sentinel node** is a dummy node that carries no value and is placed permanently at
the head of the list. Because the head always exists, "deleting the first node" stops
being a separate case — every node has a predecessor.

```python
class SentinelList:
    """Deletion runs with a single code path thanks to the head sentinel node."""

    def __init__(self) -> None:
        self.sentinel = Node(0)        # its value is never used

    def insert(self, value: int) -> None:
        new_node = Node(value)
        new_node.next = self.sentinel.next
        self.sentinel.next = new_node

    def remove(self, value: int) -> bool:
        previous = self.sentinel       # a valid "previous" always exists
        while previous.next is not None:
            if previous.next.value == value:
                previous.next = previous.next.next
                return True
            previous = previous.next
        return False


sentinel_list = SentinelList()
for measurement in (7, 18, 12):
    sentinel_list.insert(measurement)
print(sentinel_list.remove(12), sentinel_list.remove(99))    # True False
```

The same technique is also used in circular doubly linked lists, and it markedly
reduces the number of edge cases in the code.

#### Memory Overhead and Cache

The linked list's advertised advantages are limited in practice by two costs.

**Extra space.** Every node carries one or two pointers alongside its value. With
eight-byte pointers, in a singly linked list of four-byte integers the structural data
outweighs the actual data. Compared to an array, memory usage can grow by a
multiplicative factor.

**Locality.** Nodes sit scattered on the heap. Moving from one node to the next means
jumping to an unpredictable address in memory; fetching a cache line brings no
benefit, and prefetching does not work. The difference calculated in the cache lesson
of the How Computers Work course works in reverse here: while array traversal uses
many elements per cache line, list traversal carries a separate miss risk for every
node.

The result is this: a linked list insertion that is $O(1)$ on paper can, in actual
measurements, be slower than an array insertion that is $O(n)$ — especially when the
element count is small or moderate. The complexity class ignores constant factors;
hardware does not.

#### When to Use a Linked List

The structure's legitimate use cases are narrow but real:

- **When a node reference is already held.** The best-known example is a doubly
  linked list used together with a hash table: the table hands over the node
  directly, and the list updates the ordering in constant time.
  Least-recently-used cache designs are built on this pair.
- **When reallocation is unacceptable.** A dynamic array's growth makes a single
  operation take a long time; systems with a latency bound may not tolerate this.
- **When reference stability is required.** A node's address in a linked list does
  not change when new elements are added to the list; in a dynamic array,
  reallocation invalidates every address.
- **When lists are frequently merged.** Joining two lists end to end amounts to
  writing a single link.

Outside of these, the default choice is the array.

#### Cost Table

| Structure | Access | Search | Insert at start | Insert at end | Delete (node in hand) |
|---|---|---|---|---|---|
| Array (fixed size) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ |
| Dynamic array | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ amortized | $O(n)$ |
| Singly linked list | $O(n)$ | $O(n)$ | $O(1)$ | $O(n)$** | $O(n)$ |
| Doubly linked list | $O(n)$ | $O(n)$ | $O(1)$ | $O(1)$** | $O(1)$ |

\* As long as room remains.  \*\* $O(1)$ if a tail pointer is kept.

#### Summary

- In a linked list, elements do not sit contiguously; order is established by each
  node carrying the address of the next one.
- Address arithmetic does not apply; access to the $i$-th element is linear time.
- Insertion and deletion are cheap because they amount to writing pointers; what is
  expensive is locating the position.
- In a doubly linked list, the back-link makes deletion constant time when a node is
  in hand; the cost is extra memory and more complex updates.
- Pointer overhead and scattered layout can pull the list's practical performance
  below its theoretical cost.
- The structure is chosen when a node reference is already held, when reallocation is
  unacceptable, or when reference stability is required.

#### Next Step

The next two lessons take up two abstract data types built on top of the structures
defined so far. The first is the stack, which permits access only to the most
recently added element; how function calls are managed will be recalled from the
previous course.

### Stacks

Source: https://academia.sh/en/courses/data-structures/stacks

The abstract data type concept, the last-in-first-out model, two implementation options, and typical use cases.

The previous three lessons described concrete layouts: a contiguous block, a growing
block, linked nodes. This lesson asks a different question — not how the data is
stored, but **which operations are permitted**.

#### Abstract Data Type

An **abstract data type** defines the operations a structure offers and what those
operations mean; it does not say how the data sits in memory. It is the data
structures counterpart of the interface–implementation distinction from the
Programming Fundamentals course.

The distinction's value runs both ways. The consumer writes code relying only on the
contract; the implementer can change the internal structure without breaking the
contract. The same abstract type can be implemented in more than one way, each with a
different cost profile.

The **stack** is the abstract data type this lesson covers, and it is defined by a
single rule: **the last element added is the first one out.**

#### Stack Operations

Four operations suffice:

| Operation | Meaning | Cost |
|---|---|---|
| `push` | Adds an element to the top | $O(1)$ |
| `pop` | Removes and returns the top element | $O(1)$ |
| `peek` | Shows the top element without removing it | $O(1)$ |
| `is_empty` | Reports whether the stack is empty | $O(1)$ |

The operations not on this list are also part of the definition: a middle element
cannot be accessed in a stack, there is no search, there is no traversal. The
restriction is not a deficiency but the design itself — a restricted interface makes
misuse impossible.

#### Two Implementations

The same contract can be met by two different structures, and both perform every
operation in constant time.

**With a dynamic array:** The top is the end of the array. Insertion is appending,
removal is deleting from the end; neither requires shifting. The amortized cost is
constant, and cache behavior is good thanks to contiguous layout.

**With a linked list:** The top is the head of the list. Prepending and removing from
the head are constant time. Reallocation never happens; in exchange, there is per-node
pointer overhead and scattered layout.

The selection criterion repeats the previous lessons' conclusion: a dynamic array if
predictable single-operation duration is not required, a linked list if it is.

```python
class Stack:
    """Last in, first out; built on a dynamic array."""

    def __init__(self) -> None:
        self._data: list = []

    def push(self, value) -> None:
        self._data.append(value)

    def pop(self):
        if self.is_empty():
            raise IndexError("cannot pop from an empty stack")
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("an empty stack has no top")
        return self._data[-1]

    def is_empty(self) -> bool:
        return len(self._data) == 0

    def __len__(self) -> int:
        return len(self._data)


stack = Stack()
for measurement in (12, 18, 7):
    stack.push(measurement)

print(stack.peek(), len(stack))       # 7 3
print(stack.pop(), stack.pop())       # 7 18
print(len(stack), stack.is_empty())   # 1 False
```

Popping from an empty stack raising an error is part of the contract. Silently
returning a null value would carry the null value problem from the Programming
Fundamentals course over to the caller.

#### Why the Stack

The stack is the natural structure for every problem that can be described as "return
to the most recently unfinished task."

**The call stack.** The frame arrangement established in the How Computers Work course
is exactly this: the function called last returns first. Recursion depth was this
stack's fullness.

**Undo.** Operations performed in an editor are pushed onto a stack; undo pops the top
operation.

**Matching validation.** Every opening parenthesis is pushed onto a stack; every
closing parenthesis is compared against the top.

**Backtracking.** Keeping tried choices on a stack makes it possible to return to the
last decision when a dead end is reached.

**Depth-first search.** As will be seen in this course's final topic, depth-first
search in graphs runs on a stack — in its recursive form, this stack is the call stack
itself.

#### Example: Parenthesis Checking

Whether the parentheses in a piece of text match correctly is tested in a single pass,
with a stack:

```python
MATCHES = {")": "(", "]": "[", "}": "{"}

def is_balanced(text: str) -> bool:
    """Tests whether the parentheses open and close in the correct order."""
    stack = Stack()
    for char in text:
        if char in "([{":
            stack.push(char)
        elif char in MATCHES:
            if stack.is_empty() or stack.pop() != MATCHES[char]:
                return False                # a closing bracket that does not match
    return stack.is_empty()                 # unbalanced if anything is left open


print(is_balanced("(12 + [18 - 7])"))       # True
print(is_balanced("(12 + [18 - 7)]"))       # False   — out of order
print(is_balanced("((12)"))                 # False   — left open
print(is_balanced("12)"))                   # False   — extra closing bracket
```

The reason the solution requires a stack is that the depth of nesting is not known in
advance: the most recently opened parenthesis is the one that must close first. The
same structure applies to anything that nests — code blocks, markup tags, expression
parsing.

This is the core of the parsing stage covered in the previous course; the nested
structures of grammar rules are processed on a stack.

#### Example: Expression Evaluation

The second classic use is evaluating arithmetic expressions. In **postfix notation**,
where operators are written after their operands, no parentheses are needed and
evaluation runs with a single stack: a number is pushed when seen, and when an
operator is seen, two values are popped and the result is pushed back.

```python
def evaluate_postfix(expression: str) -> float:
    """Computes a postfix-notation expression using a stack."""
    stack = Stack()
    for token in expression.split():
        if token in "+-*/":
            right = stack.pop()
            left = stack.pop()
            if token == "+": stack.push(left + right)
            elif token == "-": stack.push(left - right)
            elif token == "*": stack.push(left * right)
            else: stack.push(left / right)
        else:
            stack.push(float(token))
    return stack.pop()


print(evaluate_postfix("12 18 +"))            # 30.0
print(evaluate_postfix("12 18 + 2 /"))        # 15.0   — (12 + 18) / 2
print(evaluate_postfix("12 18 7 - +"))        # 23.0   — 12 + (18 - 7)
```

The second call is the postfix form of the average calculation used throughout this
course. Note the importance of pop order: the value popped first is the right
operand, because it is the one pushed last. If this order is mixed up in subtraction
and division, the result comes out silently wrong.

Converting an expression in the (familiar) infix form to postfix notation also
requires a stack; operator precedence determines when the operators waiting on the
stack are popped. A compiler's expression-parsing stage is a generalized form of this
arrangement.

#### Limits

The stack's restricted interface brings with it some questions that cannot be
answered: how many elements have a given value, what a middle element is, whether the
elements are sorted. If this information is needed, the stack is the wrong choice.

In a fixed-capacity implementation there is a second limit: **overflow** occurs when
capacity fills up. The stack overflow in the How Computers Work course was this
situation's counterpart in the call stack.

#### Cost Table

| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Dynamic array | $O(1)$ | $O(n)$ | at end $O(1)$ amortized | from middle $O(n)$ |
| Linked list | $O(n)$ | $O(n)$ | at start $O(1)$ | from start $O(1)$ |
| **Stack** | top only $O(1)$ | — | $O(1)$ | $O(1)$ |

#### Summary

- An abstract data type defines the operations offered and their meanings; it does
  not specify layout.
- The stack is defined by the last-in-first-out rule, and its four operations are
  constant time.
- A restricted interface is not a deficiency but a design decision that prevents
  misuse.
- A dynamic array and a linked list implement the stack with the same costs; the
  choice is made based on single-operation duration and cache behavior.
- Call management, undo, matching validation, and backtracking are the family of
  problems solved with a stack.
- Popping from an empty stack raises an error; in a fixed-capacity implementation,
  overflow is the second limit.

#### Next Step

In some problems, the expected behavior is the reverse: the first to arrive must be
the first processed — in a job queue, a printer line, a network buffer. The next
lesson takes up this model and the circular buffer that allows continuous stream
processing with fixed memory.

### Queues and Deques

Source: https://academia.sh/en/courses/data-structures/queues

The first-in-first-out model, a queue in fixed memory using a circular buffer, the deque, and use cases.

The stack gives priority to the most recently added element. In some problems, the
expected behavior is exactly the reverse: in a job queue, the first to arrive must be
processed first; in a network buffer, packets must preserve their arrival order.

The **queue** is the abstract data type that defines this rule: **first in, first
out.**

#### Queue Operations

| Operation | Meaning | Target cost |
|---|---|---|
| `enqueue` | Adds an element to the end | $O(1)$ |
| `dequeue` | Removes and returns the front element | $O(1)$ |
| `front` | Shows the front element without removing it | $O(1)$ |
| `is_empty` | Reports whether the queue is empty | $O(1)$ |

Its only difference from the stack is which end removal happens at. This small
difference makes the implementation noticeably harder: in a stack, both operations
are at the same end so a single index suffices, while in a queue the two ends must be
tracked separately.

#### The Problem with a Naive Array Implementation

If a queue is built with a dynamic array, appending at the end is cheap, but taking
from the front requires shifting every element one position to the left — $O(n)$. In a
thousand-element queue, every `dequeue` call shifts the nine hundred ninety-nine
elements that remain.

The first idea for avoiding the shift is to advance a head index: the element is not
deleted, it is just counted as "no longer in the queue." This makes `dequeue`
constant time but creates a new problem — space at the start of the array becomes free
and is never reclaimed. A queue that runs continuously grows its unused space without
bound.

#### Circular Buffer

The solution is to wrap around to the start when the end of the array is reached. A
fixed-capacity block is treated as if its ends were joined together; this structure is
called a **circular buffer**.

Two indices are kept: `head` points to the next element to be taken; `tail` points to
the next position to be written. Advancing is done by taking the remainder modulo
capacity:

$$
\text{new position} = (\text{position} + 1) \bmod \text{capacity}
$$

The modulo operator was introduced in the Operators lesson; this use of it is its
canonical example.

```python
class CircularBuffer:
    """Fixed-capacity queue; wraps around to the start when it reaches the ends."""

    def __init__(self, capacity: int) -> None:
        self._data: list = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._count = 0

    def __len__(self) -> int:
        return self._count

    def is_full(self) -> bool:
        return self._count == self._capacity

    def is_empty(self) -> bool:
        return self._count == 0

    def enqueue(self, value) -> None:
        if self.is_full():
            raise OverflowError("buffer is full")
        tail = (self._head + self._count) % self._capacity   # position to write
        self._data[tail] = value
        self._count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("cannot dequeue from an empty buffer")
        value = self._data[self._head]
        self._data[self._head] = None                        # drop the reference
        self._head = (self._head + 1) % self._capacity       # wrap to the start
        self._count -= 1
        return value


queue = CircularBuffer(3)
queue.enqueue(12); queue.enqueue(18); queue.enqueue(7)
print(len(queue), queue.is_full())        # 3 True

print(queue.dequeue(), queue.dequeue())   # 12 18
queue.enqueue(25); queue.enqueue(14)      # written into freed slots by wrapping to the start
print(len(queue))                         # 3
print(queue.dequeue(), queue.dequeue(), queue.dequeue())   # 7 25 14
```

A buffer with capacity three has carried five elements: the new elements were written
into the freed positions by wrapping around to the start. No element was shifted, no
reallocation happened.

What happens on insertion into a full buffer is a design choice. Three options are
common: raising an error (as above), blocking the caller, or overwriting the oldest
element. The third is preferred in logging buffers that keep only the last $k$
measurements.

#### A Queue with a Linked List

If a capacity limit is not wanted, a linked list that keeps both a head and a tail
pointer is used: appending at the end is done in constant time with the tail pointer,
and taking from the front with the head pointer.

Its cost was defined in the previous lesson: per-node pointer overhead and scattered
layout. The common practical solution is a combination of the two — the linked list's
nodes carry not a single element but small contiguous blocks. This achieves both
unbounded growth and reasonable cache behavior.

#### Deque

A **deque** permits insertion and removal at both ends. It encompasses both the stack
and the queue: it behaves like a stack if only one end is used, and like a queue if
the two ends are used separately.

The circular buffer naturally supports the deque as well; the head index can also wrap
backward.

Its typical use is sliding-window problems: a new measurement enters at one end, and
whatever falls outside the window leaves at the other. This is the data-structure
counterpart of the sliding window pattern introduced in the Programming Fundamentals
course.

#### Use Cases

- **Job queues.** In a producer–consumer arrangement, jobs are queued; order is
  preserved.
- **Buffering.** A circular buffer is used between two components running at
  different speeds; device communication in the How Computers Work course follows
  this arrangement.
- **Breadth-first search.** As will be seen in this course's final topic,
  layer-by-layer traversal in graphs runs on a queue.
- **Scheduling.** An operating system's ready-process list follows queue order under
  fair sharing.

In situations where what determines order is not arrival but priority, a queue is not
enough; a **priority queue** is required. That structure will be taken up in the heap
lesson of the trees topic.

#### Queue Length Is a Metric

A queue is not only a data structure; it is an indicator of the speed difference
between two components. If queue length keeps growing, production is outpacing
consumption.

In an unbounded-capacity queue, this can stay hidden for a long time: no sign appears
until memory fills up, and then the system suddenly collapses. In a bounded-capacity
queue, a decision becomes necessary once the limit is reached — blocking the producer,
rejecting new work, or dropping the oldest item.

Blocking the producer is slowness propagating back toward the source, and it is
called **backpressure**. This concept, which came up in device-to-device
communication in the How Computers Work course, works the same way in distributed
systems.

For this reason, queue length is a monitored metric in production: its trend directly
shows where the bottleneck is.

#### Cost Table

| Structure | Take from front | Insert at end | Insert at start | Capacity |
|---|---|---|---|---|
| Dynamic array (naive queue) | $O(n)$ | $O(1)$ amortized | $O(n)$ | Unbounded |
| Circular buffer | $O(1)$ | $O(1)$ | $O(1)$ | Fixed |
| Linked list (head + tail) | $O(1)$ | $O(1)$ | $O(1)$ | Unbounded |
| Deque | $O(1)$ | $O(1)$ | $O(1)$ | Varies |

#### Summary

- The queue is defined by the first-in-first-out rule; its only difference from the
  stack is which end removal happens at.
- In a naive array implementation, taking from the front requires shifting; advancing
  a head index instead accumulates unused space.
- The circular buffer joins the ends with the modulo operator and makes both
  operations constant time with fixed capacity.
- Behavior on a full buffer — error, blocking, or overwriting — is a design decision.
- A linked list with head and tail pointers gives an unbounded-capacity queue; its
  cost is pointer overhead and locality.
- The deque permits both ends and is the natural structure for sliding-window
  problems.

#### Next Step

So far, sequential access and operations at the ends have been covered. Search in a
sorted data set, however, is still linear: binary search cannot be done on a linked
list, because there is no jumping to the middle element. The next lesson takes up a
probabilistic solution that makes this jump possible by adding layers to the linked
structure.

### Skip Lists

Source: https://academia.sh/en/courses/data-structures/skip-lists

Reducing search cost by adding layers to a sorted linked list, probabilistic height, and expected cost.

In a sorted array, binary search is $O(\log n)$: the middle element can be jumped to
directly. In a sorted linked list, the same search stays $O(n)$, because there is no
jumping — reaching the middle element requires following every link.

The **skip list** brings jumping back while keeping the linked structure. Its method
is to add sparse layers on top of the list.

#### The Layer Idea

Consider a railway line: a local line that stops at every station, a fast line that
stops every few stations, and an express line that stops only at major hubs.
Traveling to a distant station, the express line is used to get as close as possible
first, then the lower lines are dropped down to.

The skip list follows the same arrangement. The bottom layer is a sorted linked list
containing every element. Each layer above carries a portion of the elements of the
one below it. Search starts from the top layer:

1. Advance within the current layer as long as the next element is smaller than the
   target.
2. Drop down one layer when advancing is no longer possible.
3. Stop at the bottom layer; the sought element is either the next element at that
   point, or it is absent.

If each layer carries roughly half the elements of the one below it, the number of
layers is $\log_2 n$, and a constant number of steps on average is taken in each
layer. The expected search cost is therefore $O(\log n)$.

#### How Height Is Determined

If the layers had to be kept regular — every second element one layer up, every
fourth element two layers up — insertion and deletion would require reorganizing the
entire structure. This is the same problem that balanced trees solve, and it would
mean code of similar complexity.

The skip list's solution is different: **every new element chooses its own height at
random.** The common rule is the number of consecutive tails in a coin flip sequence —
an element is present in at least one layer; with probability one half it rises to a
second layer, with probability one quarter to a third.

The result is that layer occupancy comes out close to the desired ratio **on
average**. No rebalancing is done at all; the structure stays balanced on its own.

The cost is the type of guarantee. With an unlucky sequence of randomness, every
element could end up staying in a single layer, and search could fall back to $O(n)$.
This probability drops rapidly as the element count grows, but it is not zero. The
skip list gives an **expected**-cost guarantee, not a worst-case one.

The distinction matters: systems that need a worst-case guarantee choose balanced
trees.

#### Demonstrating the Search

The structure below is a skip list whose heights are given by hand, for the sake of
the example. Using fixed heights instead of randomness serves to show, repeatably,
how the search proceeds.

```python
class SkipNode:
    def __init__(self, value: int, height: int) -> None:
        self.value = value
        self.forward: list = [None] * height        # one link per layer


def build_list(elements: list[tuple[int, int]], top: int) -> SkipNode:
    """Builds a sorted skip list from (value, height) pairs."""
    head = SkipNode(-1, top)                         # sentinel node
    last = [head] * top                              # last node in each layer
    for value, height in elements:
        node = SkipNode(value, height)
        for k in range(height):
            last[k].forward[k] = node
            last[k] = node
    return head


def search(head: SkipNode, target: int, top: int) -> tuple[bool, int]:
    """Searches for the target; returns (found, steps taken)."""
    node = head
    steps = 0
    for k in range(top - 1, -1, -1):                 # from the top layer down
        while node.forward[k] is not None and node.forward[k].value < target:
            node = node.forward[k]                   # advance within the same layer
            steps += 1
        steps += 1                                    # drop down one layer
    candidate = node.forward[0]
    return (candidate is not None and candidate.value == target), steps


TOP = 3
elements = [(7, 3), (12, 1), (14, 2), (18, 1), (25, 3), (30, 1), (42, 2)]
head = build_list(elements, TOP)

print(search(head, 30, TOP))     # (True, 5)
print(search(head, 13, TOP))     # (False, 5)
print(search(head, 7, TOP))      # (True, 3)
```

When searching for the value `30`, the top layer carries only `7` and `25`, so the `25`
node is reached in two steps; by the time the lower layers are reached, only a few
elements are left.
The same search in a single-layer sorted list would have required following six
links.

The second call searches for a value not in the list and follows the same path; even
though the search fails, the cost is of the same order.

#### Insertion and Deletion

Insertion is the search itself: the last node stopped at in each layer is recorded,
the new node's height is determined, and links are rewritten in that many layers. The
expected cost is again $O(\log n)$.

Deletion proceeds the same way; the link is skipped past in every layer the node is
present in.

What is notable is that no operation involves **rebalancing**. The rotation
operations applied after insertion in balanced trees are absent here; balance comes
from probability. This is why a skip list's code is markedly shorter than a balanced
tree's.

The second practical advantage is concurrency: because changes are local, multiple
threads working on the same structure require less locking than with balanced trees.
This is why some database and in-memory store implementations choose it as their
sorted index structure.

#### Bounding the Number of Layers

When height is chosen at random, a theoretically very tall node can be produced.
Implementations therefore place an upper bound: the number of layers is fixed around
the logarithm of the expected element count.

The bound's effect is negligible. Because the probability of an element rising to $k$
layers is on the order of $2^{-k}$, in a structure of a million elements the
probability of rising past twenty layers is vanishingly small. The bound only keeps
memory layout predictable: the maximum number of links a node can carry is known.

The second practical detail is that the upper bound is chosen relative to the data
size. If it is chosen too small, the layers saturate and search approaches linear; the
cost of choosing it too large is only a few empty links. Because of this asymmetry,
the bound is chosen generously.

#### Probabilistic Data Structures

The skip list is the first example of a broader family: **probabilistic data
structures**. Their common trait is giving a probabilistic guarantee instead of a
certain one, and being simpler or cheaper in return.

The family also includes filters that test membership with a false-positive
probability, and counters that estimate the count of distinct elements using little
memory. These structures are used at scales where an exact answer is not required or
its cost is unacceptable, and they are a separate topic in the design of
data-intensive systems.

#### Cost Table

| Structure | Search | Insert | Delete | Guarantee |
|---|---|---|---|---|
| Sorted array | $O(\log n)$ | $O(n)$ | $O(n)$ | Certain |
| Sorted linked list | $O(n)$ | $O(1)$* | $O(1)$* | Certain |
| Skip list | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | Expected |

\* If the position is already held.

#### Summary

- Binary search cannot be done on a sorted linked list; the skip list brings jumping
  back by adding sparse layers on top.
- Search advances in the top layer and drops to the layer below when it cannot
  advance further; the number of layers is logarithmic.
- Height is chosen at random for every element; this means rebalancing is never
  needed.
- The guarantee given is expected cost, not worst case; systems that need a certain
  guarantee choose balanced trees.
- The brevity of its code and its requiring less locking under concurrency are the
  structure's practical advantages.
- The skip list is a member of the probabilistic data structures family.

#### Next Step

Throughout this topic, search stayed logarithmic at best: as the element count grows,
cost keeps growing. Yet if where a value is stored can be computed from the value
itself, search can drop to a single step. The next topic takes up the hash tables
that build this idea, and the idea's limits.

## Dictionaries and Sets

Hash tables, collision resolution, set structures, and disjoint sets.

### Hash Tables

Source: https://academia.sh/en/courses/data-structures/hash-tables

Computing a location from a key, the qualities of a hash function, the load factor, and the conditions for average constant cost.

The previous topic brought search down to logarithmic cost in the best case. Is
anything lower possible? Not for every structure based on ordering and comparison;
structures that search by comparison are stuck at this bound.

A different idea is needed: **computing where an element is stored from the element
itself.** If the location of a sought value can be computed, search comes down to a
single step.

#### Direct Addressing

The plainest form of this idea is this: if the key is an integer and its range is
small, the key itself can be used as an index.

```python
# Let the keys be in the range 0-9; the key is directly the index.
table = [None] * 10
table[3] = "three"
table[7] = "seven"
print(table[3], table[7])        # three seven
```

Access is constant time, and no search is done. The problem is the size of the key
space: if the keys are nine-digit identification numbers, direct addressing requires
an array of a billion slots. If the keys are strings, they cannot be used as an index
at all.

#### The Hash Function

A **hash function** maps any key to an integer within a fixed range. This number
determines the location (bucket) in the table:

$$
\text{location} = h(\text{key}) \bmod m
$$

Here $m$ is the table size. No matter how large the key space is, the location falls
between $0$ and $m-1$.

This solves direct addressing's memory problem — but introduces a new one: two
different keys can fall into the same location. This is called a **collision**, and
it is unavoidable. As long as the key space is larger than the table size, it is
certain that at least two keys will map to the same location. This is a direct
consequence of the pigeonhole principle: when $n$ objects are distributed into
$m < n$ boxes, at least one box receives more than one object.

How to deal with collisions is the subject of the next lesson. This lesson is
concerned with the conditions that make collisions **rare**.

#### A Good Hash Function

Three qualities are sought.

**Determinism.** The same key must always produce the same value. The mapping must
not change while the program runs; otherwise stored data cannot be found.

**Uniform distribution.** Keys should spread as evenly as possible across buckets.
Piling up in one bucket turns search in that bucket linear. In a good function,
changing a single bit of the key changes roughly half the output; this property is
called the **avalanche effect**.

**Speed.** Computing the hash must not be more expensive than the search itself.
Cryptographic hash functions provide the avalanche effect strongly, but they are
slower than necessary for a data structure; lightweight functions are used for tables.

A common method for strings is to evaluate the characters as a polynomial over a
base:

```python
def string_hash(text: str, base: int = 31, mod: int = 1_000_003) -> int:
    """Evaluates the characters as a polynomial."""
    value = 0
    for char in text:
        value = (value * base + ord(char)) % mod
    return value


print(string_hash("value"))          # 972388
print(string_hash("valuf"))          # 972389  — one-letter difference
print(string_hash("aluev"))          # 914375  — same letters, different order
```

Using the base as a multiplier makes the character order affect the result:
different strings made of the same letters produce different values. If order were
not taken into account, a function that summed the letters would collide on every
permutation of the letters.

#### The Load Factor

The table's fill ratio is the determinant of performance:

$$
\alpha = \frac{n}{m}
$$

$n$ is the number of elements, $m$ the number of buckets. As the load factor grows,
the probability of collision increases; as it shrinks, memory is wasted.

Implementations set a threshold (commonly around $0.7$) and grow the table once it is
exceeded. Growing means doubling capacity, as with a dynamic array, and **relocating
every element** — because the location depends on the table size. This operation is
called **rehashing**, and its cost is $O(n)$; amortized, it stays constant per
insertion.

#### The Hash Value and the Location Are Separate Things

It is common to confuse the two concepts. The **hash value** is the number computed
from the key, independent of the table size. The **location** is that value reduced
to the table size.

The practical consequence of this distinction is that the hash value can be stored.
Implementations write the hash value alongside the key in every slot. This provides
two gains: during rehashing, values are not recomputed, only reduced to the new table
size; and during search, hash values are compared before the keys themselves — if
they differ, the expensive equality test is never entered.

The second gain is significant when keys are long strings: comparing two integers is
far cheaper than comparing two strings character by character.

#### Average and Worst Case

The hash table's cost guarantee is conditional:

| Case | Search, insert, delete |
|---|---|
| Average (uniform distribution, bounded load factor) | $O(1)$ |
| Worst case (all keys in the same bucket) | $O(n)$ |

The worst case is not merely theoretical. If the hash function is known, keys that
fall into the same bucket can be deliberately produced; this is a form of attack that
forces the server into linear cost. The defense is adding a seed determined at run
time to the hash function — so the distribution of buckets cannot be predicted from
outside. This subject is covered separately in the application security curriculum.

#### The Immutability of the Key

If a key is modified after being placed in the table, its hash value also changes;
the element is no longer searched for in the bucket it occupies and becomes
unreachable.

This is why **immutable** values are used as keys. This is one of the practical
consequences of the immutable–mutable distinction introduced in the Programming
Fundamentals course: languages often directly forbid mutable objects from being keys.

The second rule is consistency between equality and the hash: two keys considered
equal must produce the same hash value. Failing to update the hash computation while
customizing equality behavior leads to silently broken tables.

#### Cost Table

| Structure | Search | Insert | Delete | Order preserved |
|---|---|---|---|---|
| Sorted array | $O(\log n)$ | $O(n)$ | $O(n)$ | Yes |
| Skip list | $O(\log n)$ expected | $O(\log n)$ | $O(\log n)$ | Yes |
| Hash table | $O(1)$ average | $O(1)$ average | $O(1)$ average | No |

Some implementations separately preserve **insertion order**, independent of bucket
layout; this is insertion order, not sorted order, and has nothing to do with the
magnitude of the keys. Range queries still cannot be done.

The last column is the price the hash table pays: because elements are distributed
by bucket order, key order is not preserved. If sorted traversal or range queries are
needed, tree-based structures are chosen.

One last warning: a hash value is not an identity. It is ordinary for two different
keys to produce the same hash value; this is why, once a hash match is found, the
keys themselves are also compared. Skipping this step leads to a table that silently
returns the wrong value.

#### Summary

- A hash table brings search down to average constant time by computing the location
  from the key.
- Direct addressing is applicable only to small, integer key spaces; a hash function
  removes this restriction.
- A good hash function is deterministic, distributes uniformly, and is fast; the
  avalanche effect is a sign of uniform distribution.
- Collisions are unavoidable; the load factor is the fill ratio, and once the
  threshold is exceeded, the table is grown and every element relocated.
- The worst case is linear and can be deliberately triggered; a seeded hash reduces
  this risk.
- Keys must be immutable, and equality must stay consistent with the hash.

#### Next Step

It has been established that collisions are unavoidable, but not what to do about
them. Where are two elements that fall into the same bucket placed, and how does that
decision affect search cost? The next lesson compares the two main families of
solutions — chaining and open addressing.

### Collision Resolution

Source: https://academia.sh/en/courses/data-structures/collision-resolution

Chaining and open addressing, probing strategies, clustering, the deletion problem, and a comparison of the two families.

The previous lesson showed that collisions are unavoidable: if the key space is
larger than the table, at least two keys fall into the same bucket. This lesson
covers what to do when they do.

There are two families of solutions, and both are widely used. The distinction comes
down to a single question: is the colliding element stored **inside the bucket**, or
**at another location in the table**?

#### Chaining

In **chaining**, every bucket holds a list of the elements that fall into it. The
table is an array of lists; inserting means appending to the relevant list.

```python
class ChainedTable:
    def __init__(self, bucket_count: int = 8) -> None:
        self._buckets: list[list] = [[] for _ in range(bucket_count)]
        self.comparisons = 0                    # for measurement

    def _location(self, key) -> int:
        return hash(key) % len(self._buckets)

    def put(self, key, value) -> None:
        bucket = self._buckets[self._location(key)]
        for i, (existing, _) in enumerate(bucket):
            if existing == key:
                bucket[i] = (key, value)        # existing key is updated
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self._buckets[self._location(key)]
        for existing, value in bucket:
            self.comparisons += 1
            if existing == key:
                return value
        raise KeyError(key)

    def delete(self, key) -> None:
        bucket = self._buckets[self._location(key)]
        for i, (existing, _) in enumerate(bucket):
            if existing == key:
                bucket.pop(i)                    # removing from the list is enough
                return
        raise KeyError(key)


table = ChainedTable()
for name, measurement in [("north", 12), ("south", 18), ("east", 7), ("west", 25)]:
    table.put(name, measurement)

print(table.get("east"))       # 7
table.delete("east")
print(table.get("west"))       # 25
```

Notice that deletion is simple: the element is removed from the list, and nothing
else is affected.

The cost of chaining is the average number of elements per bucket — that is, the load
factor. Search is finding the bucket (constant) plus scanning the list in the bucket
($O(\alpha)$). As long as the load factor is kept constant, average cost is constant.

In chaining, the load factor can exceed $1$: because buckets hold lists, the table
never "fills up". This flexibility allows resizing to be delayed.

#### Open Addressing

In **open addressing**, every element sits in the table's own slots. When a collision
occurs, another slot is tried according to a fixed rule; these attempts are called
**probing**.

The plainest rule is **linear probing**: look at the next slot; if it is full, the
one after that; wrap around to the beginning once the end of the table is reached.

```python
EMPTY = object()       # a slot that has never been used
DELETED = object()     # a deleted slot (tombstone)

class OpenTable:
    def __init__(self, capacity: int = 8) -> None:
        self._slots: list = [EMPTY] * capacity
        self.probes = 0

    def _location(self, key) -> int:
        return hash(key) % len(self._slots)

    def put(self, key, value) -> None:
        i = self._location(key)
        while self._slots[i] is not EMPTY and self._slots[i] is not DELETED:
            if self._slots[i][0] == key:
                break                                    # update
            i = (i + 1) % len(self._slots)                # linear probing
            self.probes += 1
        self._slots[i] = (key, value)

    def get(self, key):
        i = self._location(key)
        while self._slots[i] is not EMPTY:                # search ends on seeing EMPTY
            self.probes += 1
            if self._slots[i] is not DELETED and self._slots[i][0] == key:
                return self._slots[i][1]
            i = (i + 1) % len(self._slots)
        raise KeyError(key)

    def delete(self, key) -> None:
        i = self._location(key)
        while self._slots[i] is not EMPTY:
            if self._slots[i] is not DELETED and self._slots[i][0] == key:
                self._slots[i] = DELETED                  # a tombstone is left
                return
            i = (i + 1) % len(self._slots)
        raise KeyError(key)


table = OpenTable()
for name, measurement in [("north", 12), ("south", 18), ("east", 7)]:
    table.put(name, measurement)
print(table.get("south"))      # 18
table.delete("south")
print(table.get("east"))       # 7
```

#### The Deletion Problem

In open addressing, deletion cannot be done by merely marking the slot "empty".
Because search stops upon seeing the first empty slot, a deleted slot cuts off the
search path: elements further along the same chain become unreachable.

The solution is to fill the deleted slot with a separate marker — a **tombstone**.
Search continues past a tombstone, while insertion may write into it.

The cost is accumulation: after many deletions, the table fills with tombstones and
searches grow longer. Implementations rebuild the table once the tombstone ratio
exceeds a threshold.

#### Clustering

Linear probing's well-known weakness is **primary clustering**: consecutive blocks of
full slots form, and every new collision extends the block. As a block grows, the
number of probes for every key that lands in that region increases; the growth feeds
on itself.

Two alternative rules reduce this:

- **Quadratic probing:** The step size is not fixed but an increasing sequence of
  squares. Consecutive blocks do not form; however, keys starting from the same
  location follow the same sequence (secondary clustering).
- **Double hashing:** The step size is computed from a second hash function. Every key
  follows a different sequence; clustering is minimized, at the cost of a second hash
  computation.

Linear probing has one advantage, and it is not negligible: looking at consecutive
slots means staying within a cache line. The locality observation from the How
Computers Work course makes linear probing competitive here against alternatives
that are theoretically better.

#### Comparing the Two Families

| Criterion | Chaining | Open addressing |
|---|---|---|
| Load factor limit | Can exceed $1$ | Cannot exceed $1$; threshold kept lower |
| Memory | Node/list overhead | No extra structure, but has empty slots |
| Cache behavior | Weak (scattered list) | Good (contiguous slots) |
| Deletion | Direct | Requires a tombstone |
| Worst case | Long list in one bucket | Long probe traversing the table |
| Structure inside bucket can be changed | Yes (tree instead of list) | No |

The last row opens the door to a practical security measure: if a bucket's length
exceeds a threshold, a balanced tree is used instead of a list, and the worst case
becomes $O(\log n)$ instead of $O(n)$. This design has become widespread as a defense
against deliberate collision attacks.

#### Cost Table

| Structure | Average search | Worst-case search | Deletion |
|---|---|---|---|
| Chaining | $O(1 + \alpha)$ | $O(n)$ | $O(1 + \alpha)$ |
| Chaining (tree bucket) | $O(1 + \alpha)$ | $O(\log n)$ | $O(\log n)$ |
| Open addressing | $O\left(\frac{1}{1-\alpha}\right)$ (unsuccessful) | $O(n)$ | $O(1)$ with a tombstone* |

\* Degrades as tombstone accumulation grows.

The expression in the third row shows why cost rises sharply as the load factor
approaches $1$: at $\alpha = 0.9$ a key that is **not** in the table takes about ten
probes. Finding a key that is present is cheaper — the search stops at the first match, so
about two and a half probes suffice at the same load. This is why the threshold in open
addressing is kept lower.

#### Summary

- In chaining, colliding elements are stored in a list within the bucket; in open
  addressing, they are stored in other slots of the table.
- In chaining, average cost depends on the load factor, and the load factor can
  exceed $1$.
- In open addressing, deletion requires a tombstone; otherwise the search path is cut
  off.
- Linear probing produces primary clustering; quadratic probing and double hashing
  reduce it.
- Linear probing's cache behavior compensates in practice for its theoretical
  disadvantage.
- Converting the structure inside a bucket to a tree makes the worst case logarithmic
  and defends against collision attacks.

#### Next Step

A hash table establishes a key–value mapping. Some problems do not need a value;
only the question "does this element exist" is asked. The next lesson covers set
structures built around this question, and a highly efficient implementation built
with bit-level operations for small universes.

### Sets and Multisets

Source: https://academia.sh/en/courses/data-structures/sets

The membership-focused abstract type, hash-based and ordered implementations, bitsets, and counted multisets.

A hash table maps a key to a value. In some problems there is no value; the only
question asked is **"does this element exist"**. Filtering out duplicates, testing
whether an identifier is in a list, finding the common elements of two collections
all belong to this class.

A **set** is an abstract data type focused on membership: every element either exists
or does not, its count is not kept, and its order is not defined.

#### Set Operations

| Operation | Meaning |
|---|---|
| `add` | Adds the element to the set; no change if it is already there |
| `remove` | Removes the element |
| `contains` | Membership test |
| `union` | All elements of both sets |
| `intersection` | Elements found in both |
| `difference` | Elements in the first but not the second |
| `is_subset` | Containment test |

The first three work on a single element, the last four on a pair of sets. Their
costs are considered differently: single-element operations can be independent of the
element count, while set operations must traverse at least one set.

#### Implementation Options

A **hash set** is a hash table without a value. Single-element operations are average
constant time; order is not preserved.

A **sorted set** is built on a structure that keeps elements in order (a balanced
tree or a skip list). Single-element operations are logarithmic; in exchange,
elements can be traversed in order and range queries can be done — such as "elements
with a value between 10 and 20".

The selection criterion is clear: a hash set if order or range is not needed, a
sorted set if it is.

#### The Bitset

If the elements are integers between $0$ and $N-1$, and $N$ is of reasonable size,
there is a third, much more efficient implementation: a single bit for every element.

A **bitset** keeps membership at the bit level. The bit-level operations from the How
Computers Work course are used directly here.

```python
class BitSet:
    """Holds integers in the range 0..N-1 at the bit level."""

    def __init__(self, universe: int) -> None:
        self.universe = universe
        self._bits = 0                          # a single large integer

    def add(self, value: int) -> None:
        self._bits |= 1 << value                # set the relevant bit

    def remove(self, value: int) -> None:
        self._bits &= ~(1 << value)             # clear the relevant bit

    def contains(self, value: int) -> bool:
        return ((self._bits >> value) & 1) == 1

    def union(self, other: "BitSet") -> "BitSet":
        result = BitSet(self.universe)
        result._bits = self._bits | other._bits
        return result

    def intersection(self, other: "BitSet") -> "BitSet":
        result = BitSet(self.universe)
        result._bits = self._bits & other._bits
        return result

    def elements(self) -> list[int]:
        return [i for i in range(self.universe) if self.contains(i)]

    def __len__(self) -> int:
        return bin(self._bits).count("1")       # number of set bits


a = BitSet(16)
b = BitSet(16)
for d in (1, 3, 5, 7):
    a.add(d)
for d in (3, 5, 9):
    b.add(d)

print(a.elements(), b.elements())              # [1, 3, 5, 7] [3, 5, 9]
print(a.intersection(b).elements())            # [3, 5]
print(a.union(b).elements())                   # [1, 3, 5, 7, 9]
print(len(a), a.contains(7), a.contains(8))    # 4 True False
```

It has two advantages, and both are significant.

**Memory.** One bit is used per element. A universe of a million elements fits into
125 kilobytes; holding the same set with a hash set requires tens of bytes per
element.

**Set operations are parallel at the word level.** The intersection of two bitsets is
a single AND operation; the processor handles 64 elements in one instruction. In a
hash set, the same operation requires visiting elements one by one.

Its condition, however, is narrow: the universe must be small and dense. If the
elements are a few values scattered among billions, a bitset turns into wasted
memory. In that case, sparse representations or a hash set are preferred.

Bitsets are widely used to combine row sets in database indexes, to mark visited
nodes in graph algorithms, and to hold permission sets.

#### The Multiset

A set reports whether an element exists; it does not report **how many times**. When
a count is needed, a **multiset** is used: a counter is kept alongside every element.

```python
def frequency(measurements: list[int]) -> dict[int, int]:
    """Counts how many times each value occurs."""
    counts: dict[int, int] = {}
    for measurement in measurements:
        counts[measurement] = counts.get(measurement, 0) + 1
    return counts


measurements = [12, 18, 7, 12, 25, 12, 18]
print(frequency(measurements))                 # {12: 3, 18: 2, 7: 1, 25: 1}
print(max(frequency(measurements).items(), key=lambda c: c[1]))   # (12, 3)
```

A multiset is really a mapping whose value is a count; the reason it is called a
separate structure is that set operations are defined through the counters: union
takes the larger count, intersection the smaller.

Its typical use is counting problems: word frequencies, the most frequent values,
sample distributions. The frequency analyses in the data analytics curriculum are
built on this structure.

#### Set or List

A common performance mistake is doing a membership test on a list. Search in a list
is linear; the same test on a set is average constant.

```python
ids = list(range(100_000))
ids_set = set(ids)

# Membership on a list: every query can scan the whole list.
print(99_999 in ids)            # True — 100,000 comparisons in the worst case
# Membership on a set: a single step via hashing.
print(99_999 in ids_set)        # True — a bucket computation and a few comparisons
```

The difference is multiplied by the number of tests: performing $m$ queries on a list
is $O(n \cdot m)$, on a set $O(m)$. A membership test performed inside a loop is
therefore a standard review point.

Converting to a set also has a cost — adding every element is $O(n)$. Converting for
a single query is pointless; as the number of queries grows, the conversion pays for
itself.

#### The Cost of Set Operations

When computing the intersection of two sets, traversing the smaller set and testing
membership in the larger one is cheaper than doing it the other way around:

$$
O(\min(\lvert A\rvert, \lvert B\rvert)) \quad \text{instead of} \quad O(\lvert A\rvert)
$$

This detail makes a noticeable difference when working with large data sets, and most
library implementations do it automatically.

Sorted sets, however, offer a different route: advancing in a single pass, as if
merging two sorted arrays, gives every set operation at a cost of
$O(\lvert A\rvert + \lvert B\rvert)$ and requires no extra memory.

#### Cost Table

| Structure | Membership | Insertion | Intersection | Order |
|---|---|---|---|---|
| Hash set | $O(1)$ average | $O(1)$ average | $O(\min(\lvert A\rvert, \lvert B\rvert))$ | No |
| Sorted set | $O(\log n)$ | $O(\log n)$ | $O(\lvert A\rvert + \lvert B\rvert)$ | Yes |
| Bitset | $O(1)$ | $O(1)$ | $O(N / w)$* | By value |

\* $w$ is the processor's word width; $N$ the universe size.

#### Summary

- A set is an abstract type focused on membership; an element either exists or does
  not, and its count and order are not kept.
- A hash set performs single-element operations in average constant time but does not
  preserve order; a sorted set provides order and range queries at logarithmic cost.
- A bitset uses a single bit per element in small, dense integer universes and
  performs set operations in parallel at the word level.
- A multiset keeps a counter alongside each element; it is the natural structure for
  counting problems.
- When intersecting two sets, traversing the smaller one brings the cost down to its
  size.

#### Next Step

Up to this point, sets have been treated independently. In some problems, the
question asked is different: "are these two elements in the same group?" and groups
merge over time. The next lesson covers the disjoint-set structure that answers this
question in nearly constant time.

### Disjoint Sets

Source: https://academia.sh/en/courses/data-structures/disjoint-sets

The dynamic grouping problem, the union-find structure, union by rank, path compression, and its uses.

Suppose the question is whether two computers in a network are connected — directly
or through intermediaries. Connections are added over time and never removed. Two
questions arrive in turn: *"are these two in the same group?"* and *"merge these two
groups."*

This is the problem solved by the **disjoint sets** structure — also known as
**union–find**. Its name comes from the sets having no intersection: every element
belongs to exactly one group.

#### Two Operations

| Operation | Meaning |
|---|---|
| `find(x)` | Returns the representative of the group `x` belongs to |
| `union(x, y)` | Merges the groups of the two elements into one |

The "same group" question requires no separate operation: if two elements'
representatives are the same, they are in the same group.

A **representative** is any element of the group; which element it is does not
matter — what matters is that every element in the same group finds the same
representative.

#### Forest Representation

The structure keeps every group as a tree; the tree's root is the group's
representative. All the groups together form a **forest**.

The representation is a single array: `parent[x]` holds `x`'s parent node. A root
points to itself.

```
parent:  [0, 0, 1, 3, 3]
          ↑
          0 and 3 are roots (pointing to themselves)

group 1: 0 ← 1 ← 2        group 2: 3 ← 4
```

The `find` operation follows parent links until it reaches the root. `union`
attaches one of two roots to the other.

In this plain form, the structure can degenerate in the worst case: if every union
attaches a root to the end of a long chain, the tree turns into a linked list and
`find` becomes $O(n)$.

#### Two Improvements

**Union by rank.** During a union, the smaller tree's root is attached to the larger
one's. This way, depth increases only when two trees of equal size merge; tree height
is bounded by $O(\log n)$. Either the element count or an estimated height (rank) is
used as the size measure. Both give the same bound; the element count is often
preferred because it provides a side benefit — the group size can also be queried.
Once path compression is applied, the estimated height can exceed the actual height —
meaning the measure is used only in the union decision and does not need to be exact.

**Path compression.** As the `find` operation locates the root, it attaches every
node along the way directly to the root. The next query does not retrace the same
path. The operation flattens the structure as a byproduct of the query.

When both are applied together, the total cost of $m$ operations is nearly linear:
the amortized cost per operation is bounded by a function that grows slowly enough to
be treated as constant in practice. The precise statement and proof belong to the
**Advanced Algorithms** course; what is enough for this course is that the two
improvements are used together.

```python
class DisjointSets:
    """Union-find with union by size and path compression."""

    def __init__(self, n: int) -> None:
        self._parent = list(range(n))    # initially, everyone is their own group
        self._size = [1] * n
        self.group_count = n

    def find(self, x: int) -> int:
        root = x
        while self._parent[root] != root:    # climb to the root
            root = self._parent[root]
        while self._parent[x] != root:        # path compression: attach the path to the root
            self._parent[x], x = root, self._parent[x]
        return root

    def union(self, x: int, y: int) -> bool:
        a, b = self.find(x), self.find(y)
        if a == b:
            return False                  # already in the same group
        if self._size[a] < self._size[b]:
            a, b = b, a                   # the larger tree becomes the root
        self._parent[b] = a
        self._size[a] += self._size[b]
        self.group_count -= 1
        return True

    def same_group(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


ds = DisjointSets(6)                      # six elements, 0..5
ds.union(0, 1)
ds.union(1, 2)
ds.union(3, 4)

print(ds.same_group(0, 2))                # True
print(ds.same_group(0, 3))                # False
print(ds.group_count)                     # 3   — {0,1,2}, {3,4}, {5}

print(ds.union(0, 2))                     # False — already together
ds.union(2, 4)
print(ds.same_group(1, 3), ds.group_count)   # True 2
```

The `union` operation returning a logical value is a practical detail: the caller
learns whether a merge actually took place. This information is used directly in the
applications covered in the next section.

#### Tracing

To see how the structure flattens, the parent array can be examined step by step:

```python
ds = DisjointSets(5)
ds.union(1, 2)
ds.union(3, 4)
ds.union(2, 4)
print(ds._parent)             # [0, 1, 1, 1, 3]  — 3's root is still indirect

ds.find(4)                    # path compression runs
print(ds._parent)             # [0, 1, 1, 1, 1]  — 4 is now attached directly to the root
```

In the first output, node `4`'s root was found in two steps (`4 → 3 → 1`); after a
single `find` call, the link points directly to the root. Compression is not a
separate maintenance operation — the query itself improves the structure.

#### What It Cannot Do

The structure's well-known limit is that **splitting is not supported**. Groups
merge, they do not split. When a connection is removed, the groups must be
recomputed; this means building the structure from scratch.

The second limit is that group members cannot be listed. The structure only answers
the "same group" question; counting or listing a group's elements requires keeping
additional records.

These constraints are not accidental: the structure's speed comes precisely from not
keeping this information.

#### Applications

**Connected components.** Which nodes in a graph can reach each other is tracked with
this structure as edges are added. In this course's last topic, the same question
will also be answered with traversal algorithms; disjoint sets are more suitable when
edges arrive as a stream.

**Minimum spanning tree.** The algorithm that sorts edges by weight and selects the
ones that do not form a cycle asks the "does this edge form a cycle" question with
disjoint sets: if the two endpoints are already in the same group, the edge is
skipped. The algorithm itself is covered in the **Algorithms** course.

**Equivalence classes.** Groups formed by accumulating rules of the "these two count
as the same" kind — merging accounts belonging to the same person, matching records
that refer to the same object — are held directly with this structure.

**Grid problems.** Regions formed by merging adjacent cells in a grid (connected
areas in an image, percolation models) are tracked the same way.

Another property of the structure is that its result is **independent of the order**
of operations: no matter what order the same set of unions is applied in, the
resulting groups are the same. Only the internal shape of the trees changes, and this
does not affect the result of any query.

#### Cost Table

| Implementation | `find` | `union` |
|---|---|---|
| Plain forest | $O(n)$ | $O(n)$ |
| Union by size | $O(\log n)$ | $O(\log n)$ |
| + path compression | Amortized nearly constant | Amortized nearly constant |

#### Summary

- The disjoint-set structure divides elements into non-intersecting groups and offers
  two operations: finding a group's representative and merging two groups.
- Groups are kept as a forest; the root is the group's representative.
- Union by size keeps the height logarithmic by attaching the smaller tree to the
  larger one.
- Path compression flattens the structure during `find` by attaching the nodes along
  the path directly to the root.
- Together, the two give an amortized, nearly constant cost per operation.
- The structure does not support splitting or listing a group's elements; its speed
  comes from not keeping this information.

#### Next Step

This topic used a tree representation for groups, but trees themselves were never
defined. The next topic covers trees on their own: terminology, traversal methods,
search trees, the balance problem, and the heap structure that implements a priority
queue.

## Trees

From tree terminology to balanced search trees, heaps, tries, and range structures.

### Tree Terminology

Source: https://academia.sh/en/courses/data-structures/tree-terminology

The concepts of root, child, leaf, depth, and height; the definition of a tree, representation options, and areas of use.

The structures covered so far have been linear: every element had at most one
predecessor and one successor. This broke in the Disjoint Sets lesson — groups were
held in structures where every node has one parent, but a parent can have more than
one child.

This topic takes up that structure in its own right. A **tree** is the fundamental
structure for modeling branching relationships, and it appears at every layer of
computer science.

#### Definition

A tree is a node–edge structure that satisfies two conditions:

1. All nodes are connected to one another; none is disconnected.
2. There is no cycle; there is exactly one path between any two nodes.

The numerical consequence of these two conditions is this: a tree with $n$ nodes has
exactly $n - 1$ edges. Adding one more edge creates a cycle; removing one edge splits
the structure in two.

Most trees are **rooted**: one node is chosen as the root, and every edge is treated
as pointing away from it. Throughout this course, "tree" means a rooted tree unless
stated otherwise.

#### Terminology

```
                 (12)          ← root, depth 0
                /    \
            (18)      (7)      ← depth 1
           /   \        \
       (25)   (14)      (30)   ← depth 2, all leaves
```

| Term | Meaning | In the example |
|---|---|---|
| Root | The single node with no parent | 12 |
| Parent | The node directly above a node | 18's parent is 12 |
| Child | A node directly below a node | 12's children are 18 and 7 |
| Sibling | Children of the same parent | 25 and 14 |
| Leaf | A node with no children | 25, 14, 30 |
| Internal node | A node with at least one child | 12, 18, 7 |
| Ancestor | Nodes on the path from the root to a node | 25's ancestors: 18, 12 |
| Descendant | All nodes below a node | 18's descendants: 25, 14 |
| Subtree | A node and all its descendants | the subtree rooted at 18 |
| Depth | The number of edges from the root to a node | 25's depth is 2 |
| Height | The number of edges from a node to its farthest leaf | 12's height is 2 |
| Branching factor | A node's number of children | 2 for 12 |

**Depth and height** are frequently confused. Depth is measured from above, height
from below. The root's depth is zero and leaves have the largest depth; leaves have
height zero and the root has the largest height. A tree's height is the height of its
root.

A structure formed by multiple disconnected trees is called a **forest**. The
representation in the Disjoint Sets lesson was a forest: each group was a separate
tree.

#### Where Trees Appear

A tree is the structure of any relationship defined as "everything has one thing
above it, but a thing above can have more than one thing below it":

- **File system.** Directories and files; from the root directory to the leaves. The
  directory hierarchy in the Linux curriculum has this structure.
- **Document structure.** Nested tags in markup languages; every tag has one
  container and can have multiple contents.
- **Parse tree.** The abstract syntax tree established in the How Computers Work
  course; expression precedence was encoded in the shape of the tree.
- **Decision structures.** A question at every node, an answer on every branch;
  decision trees in machine learning follow this arrangement.
- **Organization charts and category hierarchies.** Direct modeling.

Such a wide range of use means that the operations defined on trees — traversal,
search, depth computation — turn up again and again everywhere.

#### Representation Options

A tree is stored in three main forms.

**Child lists.** Every node holds a list of its children. This is the most natural
representation for general trees; the branching factor can vary. Its cost is a list
structure per node.

**First child – next sibling.** Every node holds two links: its first child and its
next sibling. A variable number of children is represented with a fixed number of
links; the general tree is reduced to a binary structure.

**Array representation.** Nodes are held in an array, and the relationship is
computed with index arithmetic. This applies only if the tree's shape is regular; it
will be defined for binary trees in the next lesson.

```python
class TreeNode:
    """General tree node: a value and a list of children."""

    def __init__(self, value: int) -> None:
        self.value = value
        self.children: list["TreeNode"] = []

    def add_child(self, child: "TreeNode") -> "TreeNode":
        self.children.append(child)
        return child


def height(node: TreeNode) -> int:
    """Number of edges from the node to its farthest leaf."""
    if not node.children:
        return 0                                  # a leaf's height is zero
    return 1 + max(height(c) for c in node.children)


def node_count(node: TreeNode) -> int:
    return 1 + sum(node_count(c) for c in node.children)


def leaf_count(node: TreeNode) -> int:
    if not node.children:
        return 1
    return sum(leaf_count(c) for c in node.children)


root = TreeNode(12)
left = root.add_child(TreeNode(18))
right = root.add_child(TreeNode(7))
left.add_child(TreeNode(25))
left.add_child(TreeNode(14))
right.add_child(TreeNode(30))

print(height(root), node_count(root), leaf_count(root))   # 2 6 3
print(height(left), height(right))                          # 1 1
```

It is not a coincidence that all three functions are written recursively: a tree's
definition is itself recursive — a tree is a root and its subtrees. The Programming
Fundamentals course stated that "recursion is natural when a problem's definition
branches"; trees are the canonical example of that statement.

#### Verifying the Structure

Whether a structure is really a tree is tested with two conditions: the edge count
must be one less than the node count, and the structure must be connected. Together,
the two also guarantee acyclicity.

In practice a third test is also applied: every node must be reached from only one
place above it. If a node has edges from two separate parents, the structure is not a
tree but a general graph; traversal algorithms visit that node twice and the result
breaks.

#### Why Height Matters

The cost of almost every operation on a tree is proportional not to the node count
but to the **height**: a path from the root down to a leaf is followed.

This makes one question directly important: what can the height of an $n$-node tree
be?

- **Best case:** If every node distributes its children in a balanced way, the
  height is $O(\log n)$.
- **Worst case:** If every node has a single child, the tree turns into a linked
  list and the height is $O(n)$.

For this reason, the first question to ask when evaluating a tree structure is what
bounds its height. The gap between the two extremes is the central concern of the
rest of this topic: keeping search trees balanced is exactly the effort of keeping
height within a logarithmic bound.

#### Summary

- A tree is an acyclic, connected node structure; a tree with $n$ nodes has $n-1$
  edges.
- In a rooted tree, edges point away from the root; every node except the root has
  exactly one parent.
- Depth is measured downward from the root, height from a node to a leaf; a tree's
  height is the height of its root.
- Trees are the model for every branching relationship, from file systems to parse
  structures.
- Representation is done with child lists, first child–next sibling, or index
  arithmetic.
- Operation costs are proportional to height, not node count; height varies between
  logarithmic and linear depending on balance.

#### Next Step

In general trees the branching factor varies, and this complicates both
representation and analysis. The next lesson takes up the special case where every
node has at most two children — binary trees — and the regular representation
options this constraint brings.

### Binary Trees

Source: https://academia.sh/en/courses/data-structures/binary-trees

The at-most-two-children constraint, the definitions of full and complete trees, the height–node count relationship, and array representation.

In a general tree, how many children a node will have is unpredictable; this
complicates both representation and cost analysis. A **binary tree** limits branching
to at most two: every node can have a left child and a right child, or neither.

The constraint is not merely a simplification. Two children are the natural
counterpart of binary decisions in the form of "greater or smaller," "left or right,"
"yes or no"; this is why search trees, decision trees, and expression trees are
always binary.

#### Left and Right Are Separate Information

In a general tree, the order of children is usually meaningless. In a binary tree,
though, left and right are **separate positions**: whether a node's single child is
on the left or the right is part of the structure.

This distinction gains meaning in later lessons: in a search tree, the left carries
smaller values and the right carries larger ones; in an expression tree representing
subtraction, swapping left and right changes the result.

#### Shape Classes

Three definitions are commonly used and commonly confused.

**Full binary tree:** Every node has either zero or two children; no node has a
single child.

**Complete binary tree:** Every level except possibly the last is entirely full, and
the nodes on the last level are packed from left to right. A gap can occur only at
the right end.

**Perfect binary tree:** Every level is entirely full; leaves are all at the same
depth.

```
     full but not complete    complete but not perfect      perfect
        (a)                        (a)                    (a)
       /   \                      /   \                  /   \
     (b)   (c)                  (b)   (c)              (b)   (c)
          /   \                /   \   /              /  \   /  \
        (d)   (e)            (d)  (e)(f)            (d) (e)(f) (g)
```

A perfect tree is both full and complete. The concept of a complete tree will be the
foundation of the heap structure in later lessons: gaps occurring only at the right
end is what makes it possible to fit the tree into an array.

#### Height and Node Count

In a binary tree, level $d$ holds at most $2^d$ nodes ($d$ being the depth). Two
bounds follow from this.

The **maximum** number of nodes in a binary tree of height $h$:

$$
1 + 2 + 4 + \dots + 2^{h} = 2^{h+1} - 1
$$

Read in reverse, the **minimum** height of a tree with $n$ nodes:

$$
h \geq \log_2(n + 1) - 1
$$

In the worst case, every node has a single child and the height is $n - 1$.

These two bounds quantify the previous lesson's closing question. A binary tree with
one thousand nodes has a height around nine if balanced, and nine hundred ninety-nine
if degenerate. Since search cost is proportional to height, the difference between
the two is more than a hundredfold.

#### Linked Representation

The general representation is every node holding two links:

```python
class BinaryNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "BinaryNode | None" = None
        self.right: "BinaryNode | None" = None


def node_count(node: BinaryNode | None) -> int:
    if node is None:
        return 0
    return 1 + node_count(node.left) + node_count(node.right)


def height(node: BinaryNode | None) -> int:
    if node is None:
        return -1                       # an empty tree's height is treated as -1
    return 1 + max(height(node.left), height(node.right))


def is_full(node: BinaryNode | None) -> bool:
    if node is None:
        return True
    if (node.left is None) != (node.right is None):
        return False                    # a single-child node was found
    return is_full(node.left) and is_full(node.right)


root = BinaryNode(12)
root.left = BinaryNode(18)
root.right = BinaryNode(7)
root.left.left = BinaryNode(25)
root.left.right = BinaryNode(14)

print(node_count(root), height(root))    # 5 2
print(is_full(root))                          # True
root.right.left = BinaryNode(30)                 # a single child added to node 7
print(is_full(root))                          # False
```

Treating an empty tree's height as $-1$ is a convention; a single-node tree's height
then comes out to $0$, staying consistent with the definition from the previous
lesson.

#### Array Representation

If the tree is **complete**, links are not needed at all. Nodes are placed into an
array level by level, from left to right; the relationship is computed with index
arithmetic:

$$
\text{left}(i) = 2i + 1, \qquad \text{right}(i) = 2i + 2, \qquad \text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor
$$

```python
tree = [12, 18, 7, 25, 14, 30]      # complete binary tree, in level order

def left(i: int) -> int: return 2 * i + 1
def right(i: int) -> int: return 2 * i + 2
def parent(i: int) -> int: return (i - 1) // 2

print(tree[0], tree[left(0)], tree[right(0)])       # 12 18 7
print(tree[left(1)], tree[right(1)])                # 25 14
print(tree[parent(5)], tree[parent(4)])             # 7 18
```

The advantages of this representation are the same as the array discussion in the
first topic: there is no pointer overhead, and because nodes sit contiguously, cache
behavior is good.

Its constraint is that the tree must be complete. If the tree is sparse — a
degenerate chain, for example — the array representation requires $2^{h+1}$ slots and
most of it stays empty. For this reason the array representation is used in
structures whose shape is guaranteed; the heap is the main example of this.

#### What "Balanced" Means

The word "balanced" does not have a single definition. Three criteria are common:
the difference between subtree heights at every node being bounded, the ratio of
subtree sizes at every node being bounded, and leaves being at the same depth.

All three serve the same purpose — keeping height logarithmic — but different
structures choose different criteria. All three will appear in later lessons: height
difference in AVL trees, black node count in red–black trees, and equal depth in 2-3
trees.

#### The Number of Binary Trees

A side note shows how varied tree shapes can be: the number of distinct binary tree
shapes with $n$ nodes grows quickly — there are five distinct shapes with three
nodes and fourteen with four. These numbers are known as Catalan numbers and are the
solution to a counting problem: once a root is chosen for $n$ nodes, every way of
dividing the remaining nodes between the left and right subtrees produces a distinct
shape, so the count grows by roughly a factor of four per node.

The practical consequence is this: the same data set can be stored in very different
shapes depending on insertion order, and shape determines cost. Only a small fraction
of these shapes are balanced; relying on a random shape means staying exposed to the
worst case. This is the rationale behind the concept of balancing.

#### Summary

- In a binary tree every node has at most two children, and left and right are
  separate positions.
- A full tree has no single-child node; a complete tree has a gap only at the right
  end of the last level; a perfect tree has every level full.
- A tree of height $h$ holds at most $2^{h+1}-1$ nodes; the minimum height of an
  $n$-node tree is logarithmic, and linear in the worst case.
- In the linked representation every node holds two links; an empty tree's height is
  counted as $-1$.
- Complete trees can be represented with an array: left $2i+1$, right $2i+2$, parent
  $\lfloor (i-1)/2 \rfloor$.
- The same data set can be stored in many different tree shapes; shape determines
  cost.

#### Next Step

The tree has been built, but it has not yet been traversed. There is more than one
way to visit all the nodes of a tree, and which way is chosen determines the
ordering obtained. The next lesson takes up the four basic traversal orders and which
problem each is used for.

### Tree Traversals

Source: https://academia.sh/en/courses/data-structures/tree-traversals

Preorder, inorder, and postorder traversal, level-order traversal, recursive and stack-based forms, and their uses.

There is only one natural way to traverse a linear structure: from start to end. In a
tree, however, every node has at least two directions, and in which order to proceed
is a decision.

This lesson defines the four basic traversal patterns. All four visit every node
exactly once, so their cost is $O(n)$; where they differ is the **order of the
visit**, and this order determines which problem a traversal can solve.

#### Three Depth Traversals

At a node in a binary tree there are three tasks: visiting the node itself,
traversing the left subtree, and traversing the right subtree. Where the node's
visit falls within this triple gives the traversal its name.

- **Preorder:** Node first, then left, then right.
- **Inorder:** Left first, then node, then right.
- **Postorder:** Left first, then right, then node.

Notice that the left subtree is always traversed before the right; all three
patterns share this common rule.

```
            (12)
           /    \
       (18)      (7)
      /   \        \
   (25)   (14)     (30)
```

| Traversal | Order |
|---|---|
| Preorder | 12, 18, 25, 14, 7, 30 |
| Inorder | 25, 18, 14, 12, 7, 30 |
| Postorder | 25, 14, 18, 30, 7, 12 |

```python
class BinaryNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "BinaryNode | None" = None
        self.right: "BinaryNode | None" = None


def preorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        result.append(node.value)          # node first
        preorder(node.left, result)
        preorder(node.right, result)
    return result


def inorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        inorder(node.left, result)
        result.append(node.value)          # node in the middle
        inorder(node.right, result)
    return result


def postorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.value)          # node last
    return result


root = BinaryNode(12)
root.left = BinaryNode(18); root.right = BinaryNode(7)
root.left.left = BinaryNode(25); root.left.right = BinaryNode(14)
root.right.right = BinaryNode(30)

print(preorder(root))       # [12, 18, 25, 14, 7, 30]
print(inorder(root))        # [25, 18, 14, 12, 7, 30]
print(postorder(root))      # [25, 14, 18, 30, 7, 12]
```

The only difference between the three functions is where the `append` line sits.
This shows why the traversal patterns are considered members of the same family.

#### Which Traversal, Where

The difference in order determines which problems a traversal fits.

**Preorder** processes a node before its children. It suits **copying** a structure
or **serializing** it: child nodes cannot be attached before the parent node exists.
Printing a directory's name before its contents when displaying a directory tree
follows this same order.

**Inorder** gives elements in **sorted order** for binary search trees. This is the
main result of the next lesson; for now it is enough to note that the order can be
meaningful.

**Postorder** processes a node after its children. It is required for **freeing** a
tree: if the parent node is freed before its children, access to the children is
lost. For the same reason it is used in **expression evaluation** — an operator's
value cannot be found before its operands are computed. The postfix notation from
the Stacks lesson is the postorder traversal of an expression tree.

**Level order** traverses the tree layer by layer, and is the subject of the next
section.

#### Traversal with a Stack

The recursive form uses the call stack implicitly. The same traversal can also be
written by keeping the stack explicitly; this is the application to trees of the
"carrying the stack by hand" transformation from the Programming Fundamentals
course.

```python
def preorder_stack(root) -> list[int]:
    """Preorder traversal; an explicit stack instead of recursion."""
    if root is None:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right is not None:
            stack.append(node.right)        # right is pushed first
        if node.left is not None:
            stack.append(node.left)         # left is pushed second: popped first
    return result


print(preorder_stack(root))    # [12, 18, 25, 14, 7, 30]
```

Pushing the right child first is because a stack works in reverse order: last in,
first out, so the left child is processed first. If this detail is skipped, the
traversal goes right to left, and the result silently changes.

The rationale for using an explicit stack is the same as stated in the previous
course: when depth grows with the data, the call stack can be exhausted. Production
code that works with deep trees therefore often uses an explicit stack.

#### Level-Order Traversal

The fourth pattern proceeds along **breadth**, not depth: first the root, then every
node at depth 1, then those at depth 2.

Its structure is the same as a depth traversal; the only difference is using a
**queue** instead of a stack.

```python
from collections import deque

def level_order(root) -> list[int]:
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()           # first in, first out
        result.append(node.value)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
    return result


def by_levels(root) -> list[list[int]]:
    """Returns each level in a separate list."""
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):       # current queue length = level width
            node = queue.popleft()
            level.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(level)
    return result


print(level_order(root))        # [12, 18, 7, 25, 14, 30]
print(by_levels(root))          # [[12], [18, 7], [25, 14, 30]]
```

The fact that using a queue instead of a stack completely changes the traversal
pattern makes concrete why these two abstract types are defined separately. The
same duality will repeat exactly between depth-first and breadth-first search in the
graphs topic.

The loop inside `by_levels` determines the level boundary by reading the queue's
current length — newly added nodes are left for the next round.

#### Cost

Traversal is the basis of almost every operation defined on a tree: counting nodes,
computing height, copying, comparing, and freeing — all of them are a specialized
form of some traversal pattern.

All four traversals visit every node once: the time cost is $O(n)$.

Memory costs diverge. Depth traversals hold at most as many nodes on the stack as
the tree's height — $O(\log n)$ for a balanced tree, $O(n)$ for a degenerate one.
Level-order traversal holds as many nodes in the queue as the width of the widest
level; in a perfect tree, this is the node count of the last level, that is, $O(n)$.

Depth traversal uses less memory on wide, shallow trees; level traversal uses less
on deep, narrow trees.

#### Summary

- Preorder, inorder, and postorder traversals differ only in when the node is
  visited; all three traverse the left subtree before the right.
- Preorder suits copying and serialization, postorder suits freeing and expression
  evaluation, inorder suits sorted output in search trees.
- Recursive traversal uses the call stack implicitly; the explicit-stack form is
  safe on deep trees.
- Using a queue instead of a stack makes the traversal level order.
- All four traversals have $O(n)$ time cost; memory cost depends on height for
  depth traversals and on the widest level for level-order traversal.

#### Next Step

Traversal covers the entire tree. To **search** for a value, however, it should not
be necessary to traverse the whole tree; being able to choose the correct branch at
every node is enough. The next lesson defines the ordering rule that makes this
possible — the binary search tree.

### Binary Search Trees

Source: https://academia.sh/en/courses/data-structures/binary-search-trees

The ordering invariant, search–insert–delete operations, the three deletion cases, and the degenerate tree problem.

The previous lesson showed that traversing every node of a tree is $O(n)$. This is
not good enough for search; linear search in an array has the same cost, and the
tree provides no gain at all.

The gain appears once an **ordering** is added to the tree. If which branch to take
at every node can be determined by a comparison, search traverses only a single
path, not the whole tree.

#### The Ordering Invariant

A **binary search tree** is a binary tree that satisfies the following condition at
every node:

> Every value in the left subtree is smaller than the node's value, and every value
> in the right subtree is larger.

The condition must hold for the **entire subtree**; looking only at the immediate
children is not enough. This is an **invariant** in the sense defined in the
Programming Fundamentals course: it must remain true before and after every
operation.

```
            (12)
           /    \
        (7)      (25)
       /   \        \
    (3)    (10)     (30)
```

In this tree, every value in the subtree rooted at `25` is greater than $12$; every
value in the subtree rooted at `7` is smaller. The same condition holds separately
at every node.

The invariant has a direct consequence connected to the previous lesson: **inorder
traversal gives the values in ascending order.** Because the left subtree is
traversed first, then the node is visited, and finally the right subtree is
traversed, the order arises on its own.

#### Search

Search starts at the root and makes a single comparison at every node:

- If the target value equals the node, it has been found.
- If it is smaller, descend into the left subtree; if larger, into the right
  subtree.
- If an empty link is reached, the value is not in the tree.

At every step, one of the subtrees is eliminated entirely. This is the tree
counterpart of binary search on a sorted array, and its cost is proportional to
**height**.

```python
class BSTNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "BSTNode | None" = None
        self.right: "BSTNode | None" = None


def search(root: BSTNode | None, target: int) -> tuple[bool, int]:
    """Searches for the target; returns (found, comparison count)."""
    steps = 0
    node = root
    while node is not None:
        steps += 1
        if target == node.value:
            return True, steps
        node = node.left if target < node.value else node.right
    return False, steps


def insert(root: BSTNode | None, value: int) -> BSTNode:
    """Places the value in its position; returns the root. A duplicate is not inserted."""
    if root is None:
        return BSTNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root


def inorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        inorder(node.left, result)
        result.append(node.value)
        inorder(node.right, result)
    return result


root = None
for value in (12, 7, 25, 3, 10, 30):
    root = insert(root, value)

print(inorder(root))        # [3, 7, 10, 12, 25, 30]  — sorted
print(search(root, 10))     # (True, 3)
print(search(root, 11))     # (False, 3)
```

The value `10` is found in three comparisons: `12 → 7 → 10`. In this six-element
tree, linear search would make six comparisons in the worst case.

#### Insertion

Insertion is a failed search: the position where the value should sit is searched
for, and once an empty link is reached, the new node is attached there. The new node
is always a **leaf**; no existing link changes.

This simplicity also preserves the ordering invariant on its own: since the node is
placed at the end of the search path, it already satisfies the conditions of all its
ancestor nodes.

What happens with duplicate values is a design decision: they can be ignored,
placed in the right subtree, or tracked with a counter in the node. The
implementation above chose the first option; if multiset behavior is wanted, the
counter approach is suitable.

#### Deletion: Three Cases

Deletion is the most delicate operation on a tree; there are three cases depending
on the number of children the deleted node has.

**Leaf node.** It is removed directly; the parent's corresponding link is cleared.

**Single-child node.** The node is removed, and its one child is attached in its
place. The entire subtree is effectively moved up; the ordering invariant is
preserved.

**Two-child node.** It cannot be removed directly — two subtrees do not fit into
one link. The solution is to replace the node's value with its **successor**: the
smallest value in the right subtree. This value can take its place because it is
larger than the deleted node but smaller than every value in the right subtree.
Since the successor node cannot have a left child, deleting it reduces to one of the
first two cases.

```python
def smallest(node: BSTNode) -> BSTNode:
    while node.left is not None:
        node = node.left
    return node


def delete(root: BSTNode | None, value: int) -> BSTNode | None:
    if root is None:
        return None
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        if root.left is None:                 # leaf or single child (right)
            return root.right
        if root.right is None:                # single child (left)
            return root.left
        succ = smallest(root.right)           # two children: replace with successor
        root.value = succ.value
        root.right = delete(root.right, succ.value)
    return root


root = None
for value in (12, 7, 25, 3, 10, 30):
    root = insert(root, value)

root = delete(root, 3)            # leaf
print(inorder(root))        # [7, 10, 12, 25, 30]

root = delete(root, 25)           # single child
print(inorder(root))        # [7, 10, 12, 30]

root = delete(root, 12)           # two children: the root
print(inorder(root))        # [7, 10, 30]
```

Inorder traversal staying sorted after every deletion is evidence that the invariant
is preserved. This is the standard way to test a data structure's correctness:
checking the invariant after every operation.

#### The Degenerate Tree Problem

The promise of a binary search tree is that all operations are proportional to
height. The value of that promise depends on the height being small — and there is
no guarantee of that.

If values are inserted in ascending order, every new node attaches to the right; the
tree turns into a linked list:

```python
ascending = None
for value in (3, 7, 10, 12, 25, 30):        # sorted insertion
    ascending = insert(ascending, value)

mixed = None
for value in (12, 7, 25, 3, 10, 30):        # balanced order
    mixed = insert(mixed, value)

print(search(ascending, 30))        # (True, 6)  — every node was traversed
print(search(mixed, 30))            # (True, 3)
```

The same six values, the same structure, a twofold difference. When input arrives
sorted — a situation frequently encountered in real data — the tree slips into its
worst case.

This is the starting point of the next three lessons: keeping the tree's height
logarithmic regardless of insertion order.

#### Cost Table

| Structure | Search | Insert | Delete | Sorted traversal |
|---|---|---|---|---|
| Hash table | $O(1)$ average | $O(1)$ average | $O(1)$ average | Not supported |
| Binary search tree (balanced) | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
| Binary search tree (degenerate) | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |

#### Summary

- A binary search tree rests on the invariant that at every node the left subtree
  carries smaller values and the right subtree carries larger ones.
- As a consequence of the invariant, inorder traversal gives the values in
  ascending order.
- Search eliminates one subtree at every step; the cost is proportional to height.
- Insertion attaches a leaf at the end of a failed search; existing links do not
  change.
- Deletion has three cases; a two-child node is reduced to one of the first two
  cases by replacing it with the smallest value in its right subtree.
- There is no height guarantee: sorted input turns the tree into a linked list and
  all operations drop to linear.

#### Next Step

The problem has been defined: height depends on insertion order. The solution is to
check the tree after every change and rearrange it when needed. The next lesson
takes up the rotation operation that performs this rearrangement, and the two
classic tree families that guarantee balance.

### Balanced Search Trees

Source: https://academia.sh/en/courses/data-structures/balanced-search-trees

The rotation operation, the AVL balance criterion and its four cases, red–black tree color invariants, and a comparison of the two families.

The previous lesson ended with a problem: a binary search tree's height depends on
insertion order, and sorted input turns the tree into a linked list.

The solution is to check the tree after every change and **rearrange** it whenever
imbalance occurs. This lesson's subject is the operation that performs the
rearrangement, and two classic rule sets that say when to apply it.

#### Rotation

**Rotation** is a local operation that changes a tree's height by redirecting a
link. Its most important property is that **it does not break the ordering
invariant.**

```
    right rotation (about y)          left rotation
         (y)                (x)              (x)                (y)
        /   \              /   \            /   \              /   \
     (x)     C     →      A    (y)        A     (y)     →    (x)     C
    /   \                     /   \            /   \        /   \
   A     B                   B     C          B     C      A     B
```

In a right rotation, `x` moves up and `y` moves down; subtree `B` moves from `x`'s
right to `y`'s left. Nothing changes in terms of ordering: the relation
`A < x < B < y < C` holds in both forms. The only thing that changes is height.

A rotation writes a fixed number of links; its cost is $O(1)$.

```python
class AVLNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "AVLNode | None" = None
        self.right: "AVLNode | None" = None
        self.height = 0                      # leaf: 0


def h(node: AVLNode | None) -> int:
    return -1 if node is None else node.height


def update(node: AVLNode) -> None:
    node.height = 1 + max(h(node.left), h(node.right))


def balance(node: AVLNode | None) -> int:
    """Left height minus right height."""
    return 0 if node is None else h(node.left) - h(node.right)


def rotate_right(y: AVLNode) -> AVLNode:
    x = y.left
    y.left = x.right                # subtree B changes place
    x.right = y
    update(y); update(x)     # the lower node is updated first
    return x                             # new root


def rotate_left(x: AVLNode) -> AVLNode:
    y = x.right
    x.right = y.left
    y.left = x
    update(x); update(y)
    return y
```

The order of the height update matters: the lower node must be updated first,
because the height of the one above depends on it.

#### AVL Tree

An **AVL tree** enforces the following condition at every node:

> The difference between the left and right subtrees' heights is at most one.

This difference is the node's **balance factor**. Its value must be $-1$, $0$, or
$+1$; when it becomes $\pm 2$, there is imbalance, and it is corrected.

The condition is strict, and in exchange it gives a tight height bound: the height
of an AVL tree with $n$ nodes never exceeds $1.44 \log_2 n$. Search, insertion, and
deletion are therefore always $O(\log n)$ — a degenerate case is impossible.

#### Four Cases

Imbalance after insertion arises in four forms. Their names describe the path from
the unbalanced node to the inserted node.

| Case | Symptom | Fix |
|---|---|---|
| Left–left | Balance $> 1$, left child's balance $\geq 0$ | Right rotation |
| Right–right | Balance $< -1$, right child's balance $\leq 0$ | Left rotation |
| Left–right | Balance $> 1$, left child's balance $< 0$ | Rotate the left child left, then rotate right |
| Right–left | Balance $< -1$, right child's balance $> 0$ | Rotate the right child right, then rotate left |

In the last two cases a single rotation is not enough: the imbalance is "zigzag"
shaped, and it is first straightened out, then corrected.

```python
def insert_avl(root: AVLNode | None, value: int) -> AVLNode:
    if root is None:
        return AVLNode(value)
    if value < root.value:
        root.left = insert_avl(root.left, value)
    elif value > root.value:
        root.right = insert_avl(root.right, value)
    else:
        return root                                   # duplicate value

    update(root)
    d = balance(root)

    if d > 1 and balance(root.left) >= 0:             # left–left
        return rotate_right(root)
    if d < -1 and balance(root.right) <= 0:           # right–right
        return rotate_left(root)
    if d > 1:                                         # left–right
        root.left = rotate_left(root.left)
        return rotate_right(root)
    if d < -1:                                        # right–left
        root.right = rotate_right(root.right)
        return rotate_left(root)
    return root


def inorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        inorder(node.left, result)
        result.append(node.value)
        inorder(node.right, result)
    return result


# Sorted insertion: this would degenerate in a plain search tree.
root = None
for value in (3, 7, 10, 12, 25, 30):
    root = insert_avl(root, value)

print(inorder(root))        # [3, 7, 10, 12, 25, 30]
print(root.value)             # 12   — the root settled in the middle on its own
print(h(root))                # 2    — this would be 5 in a degenerate tree
```

Inserting the six values in ascending order produced a chain of height five in the
previous lesson. The AVL rule keeps the height at two on the same input; the
rotations ran on their own during insertion.

At most **one** rotation (or a double rotation) is needed after an insertion;
height updates are performed along the path down from the root. The cost of
insertion therefore stays $O(\log n)$.

#### Red–Black Trees

The second classic family tracks balance not with heights but with **colors**.
Every node is colored red or black, and four invariants are maintained:

1. The root is black.
2. A red node's children are black — two red nodes cannot be consecutive.
3. Every path from the root to any empty link contains the same number of black
   nodes.
4. Empty links count as black.

The third condition ensures the tree is perfectly balanced in terms of "black
height." The longest path can be at most twice the shortest — because the longest
path alternates red and black, while the shortest is entirely black. From this the
height bound follows:

$$
h \leq 2 \log_2 (n + 1)
$$

This is looser than AVL's $1.44 \log_2 n$ bound; the tree can be slightly deeper.
In exchange, the amount of rearrangement needed to maintain balance is small: a
constant number of rotations suffices for insertion and deletion, whereas in AVL a
chain of rotations up to the root's path can occur during deletion.

#### Choosing Between the Two Families

| Criterion | AVL | Red–black |
|---|---|---|
| Height bound | $\approx 1.44 \log_2 n$ | $\approx 2 \log_2 n$ |
| Search | Slightly faster | Slightly slower |
| Insert/delete | More rotations | Fewer rotations |
| Suited to | Read-heavy | Write-heavy |

General-purpose libraries' ordered map and ordered set structures mostly use
red–black trees: more predictable update cost is worth more, in general use, than
the difference in search speed.

The shared cost of both families is code complexity. Deletion cases are especially
numerous and are a common source of error in hand-written implementations. The skip
list from the Linear Structures topic is an alternative, since it gives the same
expected cost with far shorter code — the difference is that its guarantee is
expected, not certain.

#### Summary

- Rotation is a constant-cost operation that changes height by redirecting links
  while preserving the ordering invariant.
- In an AVL tree every node's balance factor must be $-1$, $0$, or $+1$; a
  violation is fixed with one of four cases.
- Zigzag-shaped imbalances (left–right, right–left) are first straightened with a
  single rotation.
- The AVL height bound is about $1.44 \log_2 n$; a degenerate case is impossible.
- A red–black tree tracks balance with color invariants; its bound is looser but it
  requires fewer rotations on update.
- AVL is preferred under a read-heavy load, red–black under a write-heavy one.

#### Next Step

In binary trees, balance is repaired after the fact with rotations. A different
approach is to hold more than one key per node and keep **all of the tree's leaves
at the same depth**. The next lesson takes up 2-3 trees, which build on this idea.

### 2-3 and 2-3-4 Trees

Source: https://academia.sh/en/courses/data-structures/2-3-and-2-3-4-trees

Multiple keys per node, growth by splitting upward, perfect depth balance, and the correspondence with red–black trees.

The previous lesson repaired balance with rotations: the tree breaks, then is
fixed. This lesson's approach is different — the tree **never breaks**, because the
way it grows preserves balance by definition.

The idea is to give up the binary constraint: a node can carry more than one key.

#### Two Node Types

A **2-3 tree** has two kinds of nodes:

- **2-node:** One key, two children. The left subtree carries smaller values, the
  right carries larger ones — an ordinary search tree node.
- **3-node:** Two keys, three children. The left subtree carries values smaller
  than the first key, the middle subtree carries values between the two keys, and
  the right subtree carries values larger than the second key.

```
        [7 | 12]            ← 3-node: two keys, three children
       /    |    \
    [3]   [10]  [25 | 30]
```

The structure's defining rule is this: **all leaves are at the same depth.** This is
not a property arranged afterward; it is a direct consequence of the insertion
method.

#### Search

Search resembles that of a binary tree; the only difference is comparing against
more than one key within a node. If the key is found in the node, search ends; if
not, it descends into the corresponding child based on which range the value falls
into.

The number of comparisons within a node is at most two, that is, constant. The cost
is again proportional to height.

#### Insertion: Growth from the Bottom Up

Insertion always happens at a leaf. There are three cases:

**If the leaf is a 2-node**, the key is added and the node becomes a 3-node. The
tree's shape does not change.

**If the leaf is a 3-node**, a node with three keys is temporarily formed. This
node is **split**: the middle key **is promoted** to the node above, and the
remaining two keys become two separate 2-nodes.

**If the promoted key overflows the node above it as well**, the same split
repeats one level up. Splitting can continue all the way to the root; if the root
splits, a new root is formed and **the tree's height increases by one.**

This last point is the source of the structure's balance guarantee. The tree grows
from the **root**, not from the leaves; all leaves descend one level at the same
time, so a depth difference never arises.

```python
class Node23:
    """2-3 tree node: one or two keys; zero, two, or three children."""

    def __init__(self, keys: list[int], children: list | None = None) -> None:
        self.keys = keys
        self.children = children or []

    def is_leaf(self) -> bool:
        return not self.children


def _insert(node: Node23, value: int):
    """Returns (node, promoted); promoted = (key, left, right) or None."""
    if node.is_leaf():
        keys = sorted(node.keys + [value])
        if len(keys) <= 2:
            return Node23(keys), None            # 2-node → 3-node
        middle = keys[1]                            # overflowed: promote the middle
        return None, (middle, Node23([keys[0]]), Node23([keys[2]]))

    i = 0
    while i < len(node.keys) and value > node.keys[i]:
        i += 1
    child, promoted = _insert(node.children[i], value)
    if promoted is None:
        node.children[i] = child
        return node, None

    key, left, right = promoted                           # a key came up from below
    keys = node.keys[:i] + [key] + node.keys[i:]
    children = node.children[:i] + [left, right] + node.children[i + 1:]
    if len(keys) <= 2:
        return Node23(keys, children), None
    middle = keys[1]                                # this node overflowed too
    return None, (middle,
                  Node23([keys[0]], children[:2]),
                  Node23([keys[2]], children[2:]))


def insert(root: Node23 | None, value: int) -> Node23:
    if root is None:
        return Node23([value])
    node, promoted = _insert(root, value)
    if promoted is None:
        return node
    key, left, right = promoted
    return Node23([key], [left, right])               # root split: height increased


def levels(root: Node23) -> list[list[list[int]]]:
    """Shows the tree level by level, as lists of node key lists."""
    result, row = [], [root]
    while row:
        result.append([d.keys for d in row])
        next_row = []
        for d in row:
            next_row.extend(d.children)
        row = next_row
    return result


root = None
for value in (3, 7, 10, 12, 25, 30):          # sorted insertion
    root = insert(root, value)
    print(value, "->", levels(root))

# 3  -> [[[3]]]
# 7  -> [[[3, 7]]]
# 10 -> [[[7]], [[3], [10]]]
# 12 -> [[[7]], [[3], [10, 12]]]
# 25 -> [[[7, 12]], [[3], [10], [25]]]
# 30 -> [[[7, 12]], [[3], [10], [25, 30]]]
```

The output shows step by step how the growth proceeds. On the third insertion the
root overflows, splits, and the tree rises to two levels. On the fifth insertion a
leaf overflows; the middle key is promoted to the root, and the root becomes a
3-node.

What stands out is that the input is **sorted**. The same order produced a chain of
height five in a plain binary search tree; here the height is one.

#### 2-3-4 Trees

Extending the same idea one step further gives a **2-3-4 tree**: nodes can carry
one, two, or three keys. The split threshold rises to four keys; the rule is the
same.

The added flexibility makes splits rarer. In exchange, the number of comparisons
within a node increases and the node structure grows.

#### Correspondence with Red–Black Trees

There is a one-to-one correspondence between 2-3-4 trees and the red–black trees
from the previous lesson: a 2-3-4 tree can be converted into a red–black tree by
expanding its nodes into a binary structure.

The correspondence is built as follows: a 2-node is a black node; a 3-node is a
black node with a red child attached to it; a 4-node is a black node with two red
children. Red links mean "actually part of the same node."

This correspondence explains the origin of the red–black rules. Forbidding two
consecutive red nodes is the same as a node not carrying more than three keys. The
equal black count on every path is the same as all leaves being at the same depth.

In other words, the two structures are two representations of the same idea: one
holds multiple keys per node, the other encodes the same information with colors in
a binary tree. The binary representation is preferred in implementation because it
keeps the node structure fixed.

#### Height Bound

Since all leaves are at the same depth, height is computed directly. Given that
every node carries at least two and at most three children:

$$
\log_3 (n+1) - 1 \leq h \leq \log_2 (n+1) - 1
$$

It is logarithmic at both ends; search, insertion, and deletion are $O(\log n)$.
Deletion is the mirror image of insertion: if a node is left with no keys, it
borrows from a sibling; if the sibling cannot give one either, the two nodes are
merged and the deficit is carried up a level.

The point to note in deletion is that the deficit, too, can propagate toward the
root: if the chain of merges reaches the root, the root is replaced by its single
child and the tree's height decreases by one. Just like growth, shrinkage happens
only at the root; for this reason balance is never broken.

#### Summary

- In a 2-3 tree, nodes carry one or two keys; a 2-node has two children, a 3-node
  has three.
- All leaves are at the same depth, and this is a direct consequence of the
  insertion method.
- An overflowing node is split and the middle key is promoted to the node above;
  when the root splits, the height increases by one.
- Because the tree grows from the root rather than the leaves, imbalance never
  arises; even sorted input does not produce a degenerate tree.
- A 2-3-4 tree is the same idea extended to three keys, and it maps one-to-one onto
  a red–black tree.
- Height lies between $\log_3(n+1) - 1$ and $\log_2(n+1) - 1$; all operations are
  logarithmic.

#### Next Step

Raising the number of keys per node from two to three made the tree shallower.
What happens if that number is raised into the hundreds? This question becomes
critical when data resides on disk rather than in memory. The next lesson takes up
B-trees, designed around block-based storage.

### B-Trees

Source: https://academia.sh/en/courses/data-structures/b-trees

Design driven by block-based storage, high branching factor, the B+ tree leaf chain, and index usage.

The previous lesson showed that increasing the number of keys per node shortens the
tree. This lesson asks: why stop that number at two or three?

The answer depends on where the data resides. If the data is in memory, the difference
is small — memory access is already cheap. If the data is **on disk**, the situation
changes, and this change has led an entire family of data structures to be designed
around that condition.

#### The Block Reality

The memory hierarchy in the How Computers Work course placed persistent storage at
the lowest layer: access is orders of magnitude slower than main memory.

The second, more decisive fact is that persistent storage is read at the **block**
level. Even when only a single byte is requested, the entire block — on the order of
kilobytes — is fetched. What determines the cost, therefore, is not the number of
bytes read but **how many blocks are read**.

This directly changes tree design. In an in-memory tree, the goal is to reduce the
number of comparisons; in a tree on disk, the goal is to reduce **the number of node
visits**. Every node visit is a block read.

The consequence is clear: a node should be large enough to fill a block. If the node
is smaller than the block, part of the fetched block goes to waste; if it is larger, a
single node requires reading multiple blocks. Either way, the number of reads
increases unnecessarily.

#### The B-Tree

A **B-tree** is the generalized form of the 2-3 tree. A parameter $t$ (the minimum
degree) is chosen, and the following rules hold:

- Every node except the root holds at least $t-1$ and at most $2t-1$ keys.
- An internal node with $k$ keys has $k+1$ children.
- All leaves are at the same depth.

Setting $t = 2$ yields the 2-3-4 tree; in practice, $t$ is chosen as the largest value
for which the node still fits in a block — on the order of hundreds.

Insertion and deletion follow the same split and merge rules as the previous lesson.
An overflowing node is split in two and the middle key is promoted; a node left
without a key either borrows from a sibling or merges with one.

#### The Consequence for Height

A high branching factor reduces height dramatically:

$$
h \approx \log_{b} n
$$

Here $b$ is the average branching factor.

```python
import math

def height(record_count: int, branching: int) -> int:
    """Approximate tree height given a branching factor."""
    return math.ceil(math.log(record_count, branching))


for branching in (2, 3, 100, 500):
    print(branching, height(1_000_000, branching), height(1_000_000_000, branching))

# 2   20 30
# 3   13 19
# 100 3  5
# 500 3  4
```

One million records require twenty node visits in a binary tree, and three in a
B-tree with a branching factor of one hundred. When disk access is the dominant cost,
that is the difference between twenty block reads and three.

Even with a billion records, the depth is five. Once the root and upper levels are
cached in memory, the actual number of disk accesses typically drops to one or two
blocks.

#### The B+ Tree

The commonly used variant is the **B+ tree**, and it introduces two changes:

**Records are kept only in the leaves.** Internal nodes carry only routing keys. This
lets internal nodes fit more keys — the branching factor increases and the tree
becomes even shorter.

**Leaves are linked to one another.** Each leaf points to the next, so the leaves
form a sorted linked list.

The second change transforms range queries. A query such as "all records with a
value between 100 and 200" would require repeatedly traversing a plain B-tree. In a
B+ tree, the starting point is searched for once, and the leaf chain is then followed
in order.

This is why nearly all database indexes are B+ trees: both point lookups and range
scans are handled efficiently by the same structure. Index design in the Databases
curriculum builds directly on this structure.

#### Comparison

| Metric | Balanced binary tree | B-tree / B+ tree |
|---|---|---|
| Node size | Small (a few links) | Block-sized |
| Height ($10^6$ records) | ~20 | ~3 |
| Suitable environment | Memory | Disk, network, block-based storage |
| Range query | Tree traversal | Leaf chain in a B+ tree |
| Search within a node | None | Binary search or linear scan |

The last row reveals a detail: the total number of **comparisons** in a B-tree is not
lower than in a binary tree. Keys are also searched within each node, and the total
number of comparisons ends up similar. What is gained is not comparisons but the
number of **block reads**.

This is the clearest example that choosing a data structure cannot be separated from
its hardware context: the same algorithm makes a different structure correct in a
different memory hierarchy.

#### Search Within a Node

When a node holds hundreds of keys, choosing the correct child within that node
becomes a search problem in its own right. Two options exist, and the choice is
guided by observations from earlier courses.

**Binary search** makes the number of comparisons logarithmic. **Linear scan**
performs more comparisons but reads keys contiguously and takes full advantage of
cache lines.

Since the node fits in a block and the block is already in memory, the difference
between the two methods is small; implementations often combine them — linear search
for small nodes, binary search for large ones.

This detail illustrates, once more, a lesson the course keeps repeating: the number
of comparisons alone is not a sufficient metric; how many times each level of memory
is accessed must also be counted.

#### Write Overhead and Durability

The second fact of block-based storage is that writing is more expensive than
reading. Even if a single key in a node changes, the entire block is rewritten.

This gives rise to two design decisions. Keeping nodes **more than half full**
reduces how often splits and merges occur. **Batching** writes lets successive
changes to the same block combine into a single write.

The durability requirement follows from the same fact: if the system halts during a
split, the structure can be left inconsistent. Databases manage this risk by writing
changes to a log first — the data-structure-level counterpart of the write-ahead log
idea from the How Computers Work course.

#### Uses

- **Database indexes.** Primary and secondary indexes are kept as B+ trees.
- **File systems.** Storing directory entries and block mappings.
- **Key-value stores.** Implementations that require ordered access.
- **File formats.** Index blocks embedded in large data files.

What these structures share is that the memory hierarchy layer they are designed for
is known explicitly; the same tree is built with different parameters for a
different layer.

For write-heavy workloads, an alternative family — log-structured merge trees — may
be preferred: they batch writes and write them to disk sequentially. Comparing the
two families is a topic of the Databases curriculum.

#### Summary

- Persistent storage is read at the block level; the number of blocks read determines
  the cost.
- In a B-tree, node size is matched to the block; the branching factor reaches the
  order of hundreds.
- Height is proportional to $\log_b n$; three node visits suffice for a million
  records.
- The rules are the generalized form of the 2-3 tree: splitting, promotion,
  borrowing, and merging.
- In a B+ tree, records are kept only in the leaves and the leaves are chained; range
  queries reduce to a sequential scan.
- The gain lies not in the number of comparisons but in the number of block reads.

#### Next Step

The trees covered so far preserved full ordering. In some problems, however, only
fast access to the **smallest** (or largest) element is needed; full ordering is an
unnecessary cost. The next lesson covers the heap structure, which works under this
relaxed condition, and the priority queue it implements.

### Heaps

Source: https://academia.sh/en/courses/data-structures/heaps

Priority queues, the heap condition, array representation, sift-up and sift-down, and the linear cost of building a heap.

The queues lesson left a question open: what happens when the order elements arrived
in does not matter, but their **priority** does? An operating system decides which
process to run, and a routing algorithm decides which node to expand, by looking at
priority.

A **priority queue** is the abstract data type that answers this question: elements
are inserted, and the one removed is always the **highest-priority** one.

#### Full Ordering Is Not Required

A priority queue can be implemented with a sorted structure — each insertion is
placed in order, and the front is removed. But this does more work than necessary:
the queue only needs to know the **next** element; the exact order of the rest does
not matter.

A **heap** strikes a balance between full ordering and no ordering at all. Its
condition is:

> Every node's value is less than or equal to the values of its children (a min-heap).

This is a **partial** ordering. There is no relationship between siblings; order is
maintained only along the parent–child axis. That the root is the smallest element
follows directly from this condition.

A max-heap is the reverse condition and holds the largest element at the root.

#### Complete Tree and Array Representation

A heap is always a **complete binary tree**: levels fill from left to right, and any
gap appears only at the right end of the last level. This shape guarantee makes the
array representation from the binary trees lesson directly applicable:

$$
\text{left}(i) = 2i+1, \qquad \text{right}(i) = 2i+2, \qquad \text{parent}(i) = \left\lfloor \tfrac{i-1}{2} \right\rfloor
$$

The heap holding no pointers has two consequences: there is no memory overhead, and
cache behavior is good because elements sit contiguously. The tree structure is only
conceptual; the underlying data is a plain array.

#### Two Sift Operations

The heap condition is restored through two local repair operations.

**Sift-up** is used on insertion. The new element is placed at the end of the array —
the tree's last leaf — and swapped upward with its parent until the condition holds.

**Sift-down** is used on removal. When the root is removed, the last element takes
its place and is swapped downward with its smaller child until the condition holds.

Both operations move along a path from the root to a leaf; their cost is
$O(\log n)$.

```python
class Heap:
    """Min-heap: the root is always the smallest element."""

    def __init__(self) -> None:
        self._data: list[int] = []

    def __len__(self) -> int:
        return len(self._data)

    def insert(self, value: int) -> None:
        self._data.append(value)
        self._sift_up(len(self._data) - 1)

    def smallest(self) -> int:
        if not self._data:
            raise IndexError("heap is empty")
        return self._data[0]

    def remove(self) -> int:
        if not self._data:
            raise IndexError("heap is empty")
        smallest = self._data[0]
        last = self._data.pop()
        if self._data:
            self._data[0] = last            # last element is moved to the root
            self._sift_down(0)
        return smallest

    def _sift_up(self, i: int) -> None:
        while i > 0:
            parent = (i - 1) // 2
            if self._data[i] >= self._data[parent]:
                break                      # condition holds
            self._data[i], self._data[parent] = self._data[parent], self._data[i]
            i = parent

    def _sift_down(self, i: int) -> None:
        n = len(self._data)
        while True:
            smallest, left, right = i, 2 * i + 1, 2 * i + 2
            if left < n and self._data[left] < self._data[smallest]:
                smallest = left
            if right < n and self._data[right] < self._data[smallest]:
                smallest = right
            if smallest == i:
                break
            self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
            i = smallest


h = Heap()
for measurement in (25, 7, 30, 12, 18, 3):
    h.insert(measurement)

print(h.smallest(), len(h))        # 3 6
print([h.remove() for _ in range(6)])   # [3, 7, 12, 18, 25, 30]
```

Elements coming out in sorted order during removal does not mean the heap itself is
sorted: the array is never fully sorted at any point. The sorted output arises from
each removal selecting the smallest.

#### The Cost of Building a Heap

If an array already exists and the whole thing needs to become a heap, inserting each
element one at a time takes $O(n \log n)$. A better way exists: apply sift-down going
backward, starting from the **last internal node** in the array.

```python
def build_heap(data: list[int]) -> Heap:
    """Turns an existing array into a heap in place: O(n)."""
    h = Heap()
    h._data = list(data)
    for i in range(len(data) // 2 - 1, -1, -1):     # from the last internal node to the root
        h._sift_down(i)
    return h


h = build_heap([25, 7, 30, 12, 18, 3])
print(h.smallest())                 # 3
print([h.remove() for _ in range(6)])    # [3, 7, 12, 18, 25, 30]
```

Contrary to intuition, this method's cost is not $O(n \log n)$ but $O(n)$. The reason
lies in the distribution of nodes: half the nodes are leaves and are never sifted; a
quarter sift one level, an eighth sift two levels. The total ends up markedly smaller
than the assumption that every node pays the maximum cost would suggest. The precise
analysis belongs to the **Algorithms** course.

#### Uses

**Priority scheduling.** Operating system process selection, choosing the next event
in event-driven simulations.

**Graph algorithms.** Shortest-path and minimum-spanning-tree algorithms pull the
cheapest edge in line from the heap. These algorithms are covered in the
**Algorithms** course.

**Top-k elements.** Finding the largest hundred values among millions does not
require sorting all of them: a heap of a hundred elements is kept, and each new value
is compared against the root. Memory is $O(k)$ and the cost is $O(n \log k)$.

**Streaming median.** A two-heap pattern introduced in the Programming Fundamentals
course: keeping the smaller half in a max-heap and the larger half in a min-heap
gives the median in constant time.

**Sorting.** Placing every element into a heap and removing them one at a time is an
$O(n \log n)$ sorting algorithm known as heapsort.

One detail becomes important in algorithms that use a priority queue: if the
priority of an element already in the heap changes later, the structure does not
correct itself. Either a priority-update operation is implemented separately, or the
old entry is treated as invalid and a new one is inserted; the second approach is
simpler and lets invalid entries accumulate in the heap.

#### Cost Table

| Operation | Heap | Sorted array | Unsorted array |
|---|---|---|---|
| View smallest | $O(1)$ | $O(1)$ | $O(n)$ |
| Insertion | $O(\log n)$ | $O(n)$ | $O(1)$ |
| Remove smallest | $O(\log n)$ | $O(1)$* | $O(n)$ |
| Build heap | $O(n)$ | $O(n \log n)$ | $O(1)$ |
| Search (random element) | $O(n)$ | $O(\log n)$ | $O(n)$ |

\* $O(n)$ if removal from the front requires shifting.

The last row is the heap's limitation: finding any element other than the root
requires traversing the entire structure. A heap is designed for **access to the
extreme element**, not for sorting.

#### Summary

- A priority queue is the abstract type that returns the highest-priority element on
  removal.
- The heap condition is a partial ordering: a parent is smaller than its children,
  and there is no relationship between siblings.
- A heap is always a complete binary tree and is represented as an array; there is no
  pointer overhead.
- Insertion repairs the condition with sift-up, removal with sift-down; both are
  logarithmic.
- Building a heap from an existing array is cheaper than inserting one at a time and
  runs in linear time.
- A heap is designed for access to the extreme element; searching for a random
  element is linear.

#### Next Step

The search structures covered so far compared keys as whole units. When keys are
strings, a different possibility arises: shared prefixes can be stored once, and
comparison can proceed character by character. The next lesson covers the trie,
which is built on this idea.

### Tries

Source: https://academia.sh/en/courses/data-structures/tries

The key becoming a path, sharing common prefixes, prefix queries, and the memory–speed trade-off.

The search structures covered so far compared keys **as whole units**: whether two
strings are equal, or which one is larger. When keys are strings, each of these
comparisons means, in the worst case, examining as many characters as the string's
length.

A different approach is to treat the key not as a whole but as a **sequence of
characters**. In that case, the key becomes not a node in the tree but a **path**;
comparison proceeds not all at once but character by character.

#### A Key Is a Path

In a **trie**, each edge corresponds to a character. The characters along the path
from the root to a node form the prefix that node represents.

```
        (root)
       /      \
     r          w
     |          |
     a          a
     |         / \
     t        v   i
     |        |   |
     e*       e*  t*     (* : a key ends here)
     |
     s*
```

This tree stores four keys: `rate`, `rates`, `wave`, `wait`. The `rate` and `rates`
keys share a common prefix that is stored once; the only thing distinguishing them is
that the `e` node is also marked as an end of key.

An **end-of-key marker** is required: traversing a path does not mean that path is a
key. The path `ra` exists, but `ra` is not a key. Without this marker, the structure
could only say which prefixes exist, not which strings are actually stored.

#### Cost: Dependent on Length, Not Count

Searching a trie means following the key's characters in order. The number of steps
equals the key's **length** — independent of how many keys the tree holds.

$$
O(m), \quad m = \text{key length}
$$

This is an interesting contrast with the $O(\log n)$ of a balanced search tree: even
with a million keys, searching for a ten-character key takes ten steps.

The comparison with a hash table is subtler. Search in a hash table is considered
"constant," but computing the hash value reads the entire key — that is, $O(m)$.
The two structures have the same order of point-lookup cost; where they diverge is
in operations the hash table cannot offer.

```python
class Trie:
    """Stores character sequences by sharing prefixes."""

    def __init__(self) -> None:
        self.children: dict[str, "Trie"] = {}
        self.is_end_of_key = False

    def insert(self, word: str) -> None:
        node = self
        for char in word:
            node = node.children.setdefault(char, Trie())
        node.is_end_of_key = True

    def _find_node(self, prefix: str) -> "Trie | None":
        node = self
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def contains(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end_of_key

    def has_prefix(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def words_with_prefix(self, prefix: str) -> list[str]:
        """Returns all keys starting with the given prefix, sorted."""
        start = self._find_node(prefix)
        if start is None:
            return []
        result: list[str] = []

        def walk(node: "Trie", accumulated: str) -> None:
            if node.is_end_of_key:
                result.append(prefix + accumulated)
            for char in sorted(node.children):        # sorted traversal
                walk(node.children[char], accumulated + char)

        walk(start, "")
        return result


trie = Trie()
for word in ("cat", "cats", "car", "dog", "door"):
    trie.insert(word)

print(trie.contains("cats"), trie.contains("ca"))   # True False
print(trie.has_prefix("ca"))                        # True
print(trie.words_with_prefix("ca"))     # ['car', 'cat', 'cats']
print(trie.words_with_prefix("do"))     # ['dog', 'door']
print(trie.words_with_prefix("xy"))     # []
```

The fact that `contains("ca")` returns false demonstrates the function of the
end-of-key marker: the path exists, but the key does not.

#### Prefix Queries

The trie's distinguishing capability lies in the last two calls. Finding all keys
that start with a prefix requires **scanning every key** in a hash table; in a trie,
it suffices to descend to the prefix node and traverse its subtree.

Typical uses:

- **Autocomplete.** Candidates starting with the prefix the user has typed.
- **Dictionaries and spell checking.** Tracking existing prefixes, possible
  completions; spelling suggestions are produced by a traversal that allows small
  deviations in the tree.
- **Routing tables.** Longest-prefix matching in the Computer Networks curriculum is
  done with a trie that operates on address bits.
- **Sorted traversal.** Traversing the subtree in order yields keys in lexicographic
  order — an operation a hash table cannot offer.

#### The Memory Trade-off

The cost of a trie is memory. A node is created for every character, and every node
carries a child mapping. For a set with a large alphabet and keys that do not share
common prefixes, the tree can end up larger than its own data.

Two common compressions exist:

**Path compression.** Chains of single-child nodes are collapsed into a single node,
and an edge carries a character sequence instead of a single character. This
structure is called a compressed trie (radix tree); it yields a large gain when
there are few keys and the keys are long.

**Choice of child representation.** For small alphabets, a fixed-size array (one
slot per character) is fast but wastes space in sparse nodes; using a map reduces
space at some cost to access speed.

#### Bit-Level Tries

Keys need not be strings. The **bit sequence** of any value can also serve as a
path; in that case each node has at most two children, and the structure becomes a
binary tree.

Its best-known application is network routing. An address prefix is the first $k$
bits of the address; longest-prefix matching means descending from the root and
finding the deepest matching node. Routing table lookup in the Computer Networks
curriculum is done with this structure.

The second application is dictionaries with integer keys. Compressed tries operating
at the bit level are used as an alternative to hash tables: they offer sorted
traversal and prefix queries, require no hash computation, and their worst-case
guarantee is bounded by key width.

The bit-level operations from the How Computers Work course are used directly here
as well: at each step, the relevant bit is read through shifting and masking.

#### Comparison

| Metric | Trie | Hash table | Balanced search tree |
|---|---|---|---|
| Point lookup | $O(m)$ | $O(m)$ average | $O(m \log n)$ |
| Prefix query | Direct | Not supported | Partially, via range query |
| Sorted traversal | Yes | No | Yes |
| Memory | High | Moderate | Moderate |
| Worst case | $O(m)$ | $O(n \cdot m)$ | $O(m \log n)$ |

The values in the table assume keys are strings; for numeric keys, comparison has
constant cost, and comparison-based structures take the lead.

The $\log n$ factor in a balanced search tree comes from performing a string
comparison at every node — a trie has no such factor.

#### Summary

- In a trie, a key is stored not in a node but in a path descending from the root;
  common prefixes are kept once.
- An end-of-key marker is required; a path existing does not mean that path is a
  key.
- Search cost depends on key length and is independent of the number of stored
  keys.
- Listing all keys starting with a prefix means traversing the prefix node's
  subtree.
- The cost is memory; path compression and the choice of child representation
  reduce that cost.
- Prefix queries and sorted traversal, which a hash table cannot offer, are this
  structure's reason for existing.

#### Next Step

The structures covered so far operated on individual keys. In some problems,
however, the query concerns a range: "what is the sum of the values between these
two indices" — and this query is asked repeatedly while the data keeps changing. The
next lesson covers structures that answer this question at logarithmic cost.

### Segment and Fenwick Trees

Source: https://academia.sh/en/courses/data-structures/segment-trees

Situations that require both range queries and point updates together, the segment tree, and the Fenwick tree.

Suppose these two operations are performed repeatedly on an array of measurements:
ask for the sum of the values in a given range, and update a single value. If both
happen often, none of the structures covered so far give a good answer.

#### Two Extreme Solutions

**Raw array.** An update is a single write: $O(1)$. A range sum, however, walks
every element in the range: $O(n)$.

**Prefix-sum array.** If the running totals from the start are precomputed, the sum
of any range is the difference of two values: $O(1)$. In exchange, when a single
value changes, every prefix sum after it must be recomputed: $O(n)$.

```python
measurements = [12, 18, 7, 25, 14, 30]

prefix_sums = [0] * (len(measurements) + 1)
for i, value in enumerate(measurements):
    prefix_sums[i + 1] = prefix_sums[i] + value

print(prefix_sums)                # [0, 12, 30, 37, 62, 76, 106]
print(prefix_sums[4] - prefix_sums[1])        # 50   — range 1..3: 18 + 7 + 25
```

Both solutions make one operation constant and the other linear. If both happen
often, neither is sufficient; what is needed is a structure that makes **both
operations logarithmic**.

#### The Segment Tree

A **segment tree** divides the array in half, recursively: the root represents the
whole array, its children represent its halves, and their children represent
quarters. Every node stores a summary of its own range — here, its sum.

```
                [0..5] = 106
             /                \
        [0..2] = 37        [3..5] = 69
        /      \            /       \
   [0..1]=30  [2..2]=7  [3..4]=39  [5..5]=30
    /    \                 /   \
 [0]=12 [1]=18         [3]=25 [4]=14
```

The figure above is the tree's **conceptual** shape. The implementation below keeps the
tree in a flat `2n` array, and when `n` is not a power of two the internal nodes do not
line up with these halves: for a six-element array the root's children cover `[2..5]` and
`[0..1]`, not `[0..2]` and `[3..5]`. The answers to queries do not change; only the ranges
the nodes cover shift.

A **query** expresses the requested range as a union of nodes in the tree. Any range
can be covered with at most $O(\log n)$ nodes; this is the source of the query cost.

An **update** changes the relevant leaf and recomputes every summary along the path
from the leaf to the root — again $O(\log n)$.

```python
class SegmentTree:
    """Range sum query and point update; both O(log n)."""

    def __init__(self, data: list[int]) -> None:
        self._n = len(data)
        self._tree = [0] * (2 * self._n)          # leaves occupy the second half
        for i, value in enumerate(data):
            self._tree[self._n + i] = value
        for i in range(self._n - 1, 0, -1):       # internal nodes, bottom-up
            self._tree[i] = self._tree[2 * i] + self._tree[2 * i + 1]

    def update(self, index: int, value: int) -> None:
        i = self._n + index
        self._tree[i] = value
        i //= 2
        while i >= 1:                             # refresh summaries up to the root
            self._tree[i] = self._tree[2 * i] + self._tree[2 * i + 1]
            i //= 2

    def range_sum(self, left: int, right: int) -> int:
        """Sum of the half-open range [left, right)."""
        result = 0
        l, r = self._n + left, self._n + right
        while l < r:
            if l % 2 == 1:                        # left bound is a right child: take it
                result += self._tree[l]
                l += 1
            if r % 2 == 1:                        # right bound is a right child: take it
                r -= 1
                result += self._tree[r]
            l //= 2
            r //= 2
        return result


tree = SegmentTree([12, 18, 7, 25, 14, 30])
print(tree.range_sum(0, 6))          # 106  — whole array
print(tree.range_sum(1, 4))          # 50   — 18 + 7 + 25
tree.update(2, 100)                  # 7 becomes 100
print(tree.range_sum(1, 4))          # 143
print(tree.range_sum(0, 6))          # 199
```

The generality of the structure stands out: the combining operation can be maximum,
minimum, greatest common divisor, or any operation with the associative property,
instead of sum. Only the summary stored in the nodes and the combining line change.

#### The Fenwick Tree

A **Fenwick tree** (binary indexed tree) is a more compact structure concerned only
with prefix sums. It does the same job with a single array of $n$ slots; it uses
half the memory of a segment tree, and its code is noticeably shorter.

The idea is that each index stores the sum of a specific range, and the length of
that range is determined by the **lowest set bit** in the index's binary
representation. The `x & -x` idiom from the How Computers Work course is used
directly here.

```python
class FenwickTree:
    """Prefix sum and point update; O(log n)."""

    def __init__(self, size: int) -> None:
        self._tree = [0] * (size + 1)            # 1-based index

    def add(self, index: int, increment: int) -> None:
        i = index + 1
        while i < len(self._tree):
            self._tree[i] += increment
            i += i & -i                          # next responsible index

    def prefix_sum(self, index: int) -> int:
        """Sum of the range [0, index)."""
        result, i = 0, index
        while i > 0:
            result += self._tree[i]
            i -= i & -i                          # drop the lowest set bit
        return result

    def range_sum(self, left: int, right: int) -> int:
        return self.prefix_sum(right) - self.prefix_sum(left)


fenwick = FenwickTree(6)
for i, value in enumerate([12, 18, 7, 25, 14, 30]):
    fenwick.add(i, value)

print(fenwick.prefix_sum(6))            # 106
print(fenwick.range_sum(1, 4))          # 50
fenwick.add(2, 93)                      # 7 + 93 = 100
print(fenwick.range_sum(1, 4))          # 143
```

The Fenwick tree takes updates as an **increment**; to set a value directly, the
difference from the old value is added. This follows from the structure's
prefix-sum-oriented design.

#### Which Structure, When

| Structure | Range query | Point update | Memory | Generality |
|---|---|---|---|---|
| Raw array | $O(n)$ | $O(1)$ | $n$ | Full |
| Prefix-sum array | $O(1)$ | $O(n)$ | $n$ | Sum only |
| Segment tree | $O(\log n)$ | $O(\log n)$ | $2n$ | Any associative operation |
| Fenwick tree | $O(\log n)$ | $O(\log n)$ | $n$ | Sum and operations with an inverse |

Selection criteria:

- If the data does not change, a **prefix-sum array** is best; no extra structure is
  needed.
- If only the total is queried, **Fenwick** is sufficient: less memory, shorter code.
- If operations without an inverse, such as minimum or maximum, or range updates are
  needed, a **segment tree** is used.

An extension of the segment tree makes range updates logarithmic as well: the
update is not propagated downward immediately but is kept at the node as a "pending
change" and applied only once that subtree is descended into. This technique is
covered in advanced algorithm topics.

#### Uses

Range queries are a common need for systems that work with time series and ordered
data: the sum or maximum of measurements in a time interval, the number of records
in a given range of a ranking, counting objects in a region of a game world.

If the data does not change, the same questions are answered with precomputed
summaries; the reason these structures exist is that the data **keeps changing**.

#### Summary

- A raw array makes updates constant, and a prefix-sum array makes queries constant;
  if both are needed often, neither is sufficient.
- A segment tree divides the array in half and stores a summary of each subrange at
  every node; query and update are $O(\log n)$.
- Any range can be covered with at most a logarithmic number of nodes.
- By changing the combining operation, the same structure is used for minimum,
  maximum, or other associative operations.
- A Fenwick tree is concerned only with prefix sums; it gives the same cost with
  half the memory and shorter code.
- The reason these structures exist is that the data changes; for static data,
  precomputed summaries suffice.

#### Next Step

Range queries were one-dimensional: indices sat on a line. If positional data has
two or more dimensions — points on a map, records in a feature space — how does the
splitting idea extend? The next lesson covers this topic's final structure:
multidimensional trees.

### Multidimensional Trees

Source: https://academia.sh/en/courses/data-structures/multidimensional-trees

Spatial queries, alternating splits in a k-d tree, nearest-neighbor search, pruning, and the curse of dimensionality.

The search structures covered so far ordered along a single axis: at every node, the
question "smaller or larger" was answered against a single value.

Some data does not fit on a single axis. A point on a map carries two coordinates, a
sensor reading carries temperature and humidity, a document embedding carries
hundreds of numbers. The questions asked of such data are different too:
**"which record is nearest to this point"** or **"which points lie inside this
rectangle"**.

#### Why One-Dimensional Structures Fall Short

If points are ordered only by their first coordinate, points that are close on that
axis can be found. But two points close in the first coordinate can be far apart in
the second; the ordering carries no information about actual proximity.

Even if two separate indexes are kept — one per axis — the result does not change:
each index yields a candidate list along one axis, but computing their intersection
requires walking every candidate.

What is needed is a structure that splits the space by considering **all dimensions
together**.

#### The k-d Tree

A **k-d tree** is the multidimensional generalization of the binary search tree. Its
only difference is which dimension the comparison at each node is made against: the
split dimension is chosen **alternately, based on depth**.

In a two-dimensional set, the root splits on the first coordinate, its children on
the second, and its grandchildren on the first again. Every node divides the space
in two with a line; the subtrees correspond to these half-planes.

```python
class KdNode:
    def __init__(self, point: tuple[float, ...], axis: int) -> None:
        self.point = point
        self.axis = axis
        self.left: "KdNode | None" = None
        self.right: "KdNode | None" = None


def build_kd(points: list[tuple[float, ...]], depth: int = 0) -> KdNode | None:
    """Builds a balanced k-d tree by choosing the median point."""
    if not points:
        return None
    dim = len(points[0])
    axis = depth % dim                              # alternating split
    ordered = sorted(points, key=lambda p: p[axis])
    mid = len(ordered) // 2
    node = KdNode(ordered[mid], axis)
    node.left = build_kd(ordered[:mid], depth + 1)
    node.right = build_kd(ordered[mid + 1:], depth + 1)
    return node


points = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
root = build_kd(points)
print(root.point, root.axis)                        # (7, 2) 0
print(root.left.point, root.right.point)             # (5, 4) (9, 6)
```

The median point is chosen during construction, so the two subtrees end up equal in
size and height stays at $O(\log n)$. When the median is selected via sorting,
construction takes $O(n \log^2 n)$; with a linear-time selection algorithm, it drops
to $O(n \log n)$. Selection algorithms are a topic of the **Algorithms** course.

#### Nearest-Neighbor Search

The core idea of the search is pruning: a subtree is never visited if it is
certainly farther than the best candidate found so far.

The steps are:

1. Descend the tree by checking which side the query point falls on; the leaf
   reached is the first candidate.
2. On the way back up, test at each node whether the node itself is closer.
3. If the distance to the splitting line is **smaller** than the best distance found
   so far, the other subtree is also visited; if it is larger, the entire subtree is
   ruled out.

The third step provides all the efficiency: the distance to the splitting line is a
lower bound on the distance to any point on that side.

```python
def sq_dist(a: tuple[float, ...], b: tuple[float, ...]) -> float:
    """Squared distance; taking the square root would not change the ordering."""
    return sum((x - y) ** 2 for x, y in zip(a, b))


def nearest(node: KdNode | None, target: tuple[float, ...],
            best=None, counter=None):
    """Returns (nearest point, number of nodes visited)."""
    counter = {"n": 0} if counter is None else counter
    if node is None:
        return best, counter["n"]

    counter["n"] += 1
    if best is None or sq_dist(node.point, target) < sq_dist(best, target):
        best = node.point

    axis = node.axis
    diff = target[axis] - node.point[axis]
    near, far = (node.left, node.right) if diff < 0 else (node.right, node.left)

    best, _ = nearest(near, target, best, counter)             # near side first
    if diff ** 2 < sq_dist(best, target):                       # pruning test
        best, _ = nearest(far, target, best, counter)
    return best, counter["n"]


print(nearest(root, (9, 2)))      # ((8, 1), 3)
print(nearest(root, (4, 6)))      # ((4, 7), 3)
```

In the first query, only three nodes of the six-point tree were visited; three nodes
were pruned away. Squared distance is used to avoid computing a square root — an
unnecessary operation as long as the ordering does not change.

#### Range Query

A rectangle (or multidimensional box) query uses the same pruning logic: if the
node's splitting line lies entirely on one side of the query box, the other subtree
is never visited.

This is the spatial counterpart of the idea behind segment trees: the query is
covered by a subset of the nodes in the tree.

#### The Curse of Dimensionality

The k-d tree's promise holds in low dimensions. As the number of dimensions grows,
pruning stops working.

The reason is intuitive: in a high-dimensional space, distances between points
converge toward one another, and the distance to the splitting line comes out
smaller than the best candidate almost every time. The pruning condition is never
met, both subtrees are visited, and the search degenerates into a linear scan.

The practical rule of thumb is: $n \gg 2^{k}$ must hold ($k$ being the number of
dimensions). With twenty dimensions and a thousand points, a k-d tree is no faster
than a linear scan — and it uses extra memory besides.

This is not merely a data-structure detail; it is a general property of
high-dimensional data, and it also sets the limit for distance-based methods in
machine learning.

Insertion and deletion are also possible, but a k-d tree cannot maintain its balance
under these operations: no repair operation like rotation is defined for it. If the
data changes frequently, the tree is rebuilt at intervals.

#### Other Spatial Structures

| Structure | Split shape | Suitable use |
|---|---|---|
| Grid | Fixed-size cells | Uniformly distributed data, fixed-radius queries |
| Quadtree | Every node splits the area into four | Two-dimensional, uneven density |
| k-d tree | Alternating single axis | Moderate dimension, point data |
| R-tree | Bounding rectangles | Area data, not points; disk-based indexes |

For high-dimensional data — such as document and image embeddings — exact
nearest-neighbor search is abandoned in favor of **approximate** methods. These
methods give probabilistic guarantees, much like the skip list from the linear
structures topic, and form the basis of vector databases; they are covered in the
AI Engineering curriculum.

#### Summary

- Spatial queries cannot be answered with one-dimensional ordering; proximity
  depends on all dimensions together.
- A k-d tree chooses the split dimension alternately based on depth; every node
  divides the space in two.
- Choosing the median point keeps height logarithmic.
- Nearest-neighbor search uses the distance to the splitting line as a lower bound
  and prunes subtrees.
- Squared distance is used to avoid computing a square root; it does not change the
  ordering.
- As the number of dimensions grows, pruning loses its effect and the search
  degenerates into a linear scan; the practical rule of thumb is $n \gg 2^k$.

#### Next Step

Trees were acyclic, single-parent structures. When that constraint is lifted — when
a node can have more than one "parent" and cycles are allowed — the resulting
structure is far more general, and it is the natural model for problems such as
networks, maps, and dependency relationships. The course's final topic covers
graphs.

## Graphs

The concept of a graph, representation options, breadth-first and depth-first search, and topological sort.

### The Concept of a Graph

Source: https://academia.sh/en/courses/data-structures/concept-of-a-graph

Vertex and edge definitions, directed and undirected graphs, weight, degree, path, and cycle concepts.

Trees carried two constraints: no cycles, and every node had exactly one parent. Removing
those constraints produces the most general structure for modeling relationships.

A **graph** consists of vertices and the edges that connect them. Such a simple
definition having such a wide range of applications comes from the relationship itself
being a fundamental concept: connections between roads, acquaintance between people,
dependency between tasks, links between pages — all of these are the same structure.

#### Basic Terms

A graph is written as $G = (V, E)$: $V$ is the set of vertices, $E$ is the set of edges.

| Term | Meaning |
|---|---|
| Vertex | The unit of the structure; the entity being modeled |
| Edge | A relationship between two vertices |
| Neighbor | Vertices connected by an edge |
| Degree | The number of edges attached to a vertex |
| Path | A sequence of vertices following edges |
| Cycle | A path that returns to the vertex it started from |
| Connected component | A set of vertices that can reach one another within itself |

If one vertex can **reach** another, a path exists between them. A graph in which every
pair of vertices can reach each other is called **connected**; if some pairs cannot, the
graph is split into multiple **components**.

#### Directed and Undirected

In an **undirected graph** an edge is two-way: if an edge exists between `a` and `b`, one
can go from `a` to `b` and from `b` to `a`. It models mutual relationships — a road
between two cities, a friendship between two people.

In a **directed graph** an edge has a direction. It models one-way relationships — a link
from one page to another, one task's dependency on another, a one-way street.

In a directed graph, degree splits into two: **in-degree** (the number of edges arriving
at a vertex) and **out-degree** (the number leaving it). This distinction becomes
decisive in the topological sort lesson.

The concept of a cycle also specializes in directed graphs. A **directed acyclic graph**
is a graph that contains no directed cycle, and it is the natural model of dependency
relationships: a task cannot depend on itself, even indirectly.

#### Weight

A numeric value — a **weight** — can be assigned to edges. Weight carries the cost or
strength of the relationship: the distance between two cities, the latency of a
connection, the duration of an operation.

In an unweighted graph, the "shortest path" is the one using the fewest edges. In a
weighted graph it is the path with the smallest sum of weights, and the two paths can
differ: whether a few long edges or many short edges is cheaper can only be answered by
looking at the weights.

#### Trees Are a Special Case of Graphs

The definition from the previous topic fits into place here: **a tree is an acyclic,
connected, undirected graph.** That a tree with $n$ vertices has $n-1$ edges was a
direct consequence of that definition.

The relationship is built in three steps:

- Removing cycles from a graph produces a **forest**.
- A forest that is connected becomes a **tree**.
- Choosing a vertex of a tree as the root produces a **rooted tree**.

This means every structure from the previous topic is a special case of a graph. The
reverse does not hold: graphs model what trees cannot — cycles, multiple paths, more
than one parent.

The "connected component" question from the disjoint-sets lesson connects here as well:
which vertices belong to the same component as edges are added was tracked there with
union–find.

#### Special Graph Families

| Family | Definition | Example use |
|---|---|---|
| Directed acyclic graph | Directed, no cycles | Task dependencies, build order |
| Bipartite graph | Vertices split into two groups, edges only between groups | Matching problems |
| Complete graph | An edge between every pair of vertices | Worst-case analysis |
| Sparse / dense graph | Edge count close to vertex count / close to its square | Determines the representation choice |

The last row is the subject of the next lesson: the ratio of edge count to vertex count
directly determines which representation is suitable.

Bounds on edge count also follow from this distinction. In a simple, undirected graph
the maximum number of edges is:

$$
\lvert E \rvert \leq \frac{\lvert V \rvert (\lvert V \rvert - 1)}{2}
$$

So edge count is bounded by the square of vertex count. Most real graphs stay far below
this bound — in a road network, each city connects to only a handful of neighbors. This
observation explains why representation choice in practice is made with sparse graphs in
mind.

#### A Modeling Example

Let the connections between measurement stations be modeled as a graph: stations are
vertices, the communication lines between them are edges, and a line's latency is its
weight.

```python
# Undirected, weighted graph: each edge is written once.
edges = [
    ("north",  "center", 4),
    ("south",  "center", 2),
    ("east",   "center", 7),
    ("west",   "north",  3),
    ("west",   "south",  5),
]

vertices = {v for edge in edges for v in edge[:2]}
print(sorted(vertices))        # ['center', 'east', 'north', 'south', 'west']
print(len(vertices), len(edges))     # 5 5

degree: dict[str, int] = {v: 0 for v in vertices}
for a, b, _ in edges:
    degree[a] += 1
    degree[b] += 1

print(sorted(degree.items()))
# [('center', 3), ('east', 1), ('north', 2), ('south', 2), ('west', 2)]
print(sum(degree.values()), 2 * len(edges))    # 10 10
```

The last line shows the most basic identity of graph theory: **the sum of degrees is
twice the number of edges.** Because each edge contributes one to each of two vertices'
degrees, this holds in every undirected graph. A direct consequence is that the number
of odd-degree vertices is always even.

Multi-edges and self-loops — more than one edge between the same pair of vertices, or an
edge from a vertex to itself — are meaningful in some models. Graphs that allow these are
called multigraphs; the definition used in this course, which does not allow them, is a
**simple graph**.

#### Questions Asked with Graphs

As much as the structure itself, the questions asked on it are standard:

- **Reachability:** Is there a path between two vertices?
- **Shortest path:** If one exists, which is the cheapest?
- **Connected components:** How many pieces is the graph split into?
- **Cycle detection:** Does the structure contain a cycle?
- **Ordering:** Is there an execution order consistent with the dependencies?
- **Coverage:** Which set of edges reaches every vertex at the least cost?

Most of these questions require different algorithms depending on whether the graph is
directed and whether it carries weight. The remaining three lessons of this course build
the traversal methods that answer the first four; the shortest-path and coverage
problems, together with the algorithms that bring weights into play, are taken up in the
**Algorithms** course.

#### Summary

- A graph is the most general relationship model, made of vertices and edges.
- An undirected edge shows a mutual relationship, a directed edge a one-way one; in a
  directed graph, in-degree and out-degree are separated.
- Weight carries the cost of a relationship and changes what "shortest path" means.
- A tree is an acyclic, connected graph; forests and rooted trees are specialized forms
  of this definition.
- Directed acyclic graphs are the natural model of dependency relationships.
- The sum of degrees is twice the number of edges; edge count is bounded by the square
  of vertex count.

#### Next Step

The concept of a graph has been defined, but not how it is kept in memory. The choice is
not trivial: the same algorithm runs at different costs depending on the representation.
The next lesson takes up the two basic representations and the criterion that decides
between them.

### Graph Representations

Source: https://academia.sh/en/courses/data-structures/graph-representations

Adjacency matrix versus adjacency list, memory and operation costs, the sparsity criterion, and the edge list.

The concept of a graph is abstract; it has to turn into a representation in code. There
are two basic options, and the difference between them is an instance of this course's
recurring theme: **the same data, a different layout, a different cost.**

The choice depends on the graph's edge density and on which operations will be performed
often. A choice made without knowing these two factors can raise an algorithm's cost by
an entire order unnecessarily.

#### Adjacency Matrix

An **adjacency matrix** is a table of size $\lvert V \rvert \times \lvert V \rvert$. The
cell at row $i$, column $j$ states whether an edge exists between $i$ and $j$; in a
weighted graph it carries the weight.

```python
INF = float("inf")
vertices = ["center", "east", "north", "south", "west"]
index = {name: i for i, name in enumerate(vertices)}
n = len(vertices)

matrix = [[INF] * n for _ in range(n)]
for i in range(n):
    matrix[i][i] = 0

for a, b, weight in [("north", "center", 4), ("south", "center", 2),
                      ("east", "center", 7), ("west", "north", 3),
                      ("west", "south", 5)]:
    matrix[index[a]][index[b]] = weight
    matrix[index[b]][index[a]] = weight           # undirected: both cells

print(matrix[index["west"]][index["north"]])      # 3    — edge exists
print(matrix[index["west"]][index["east"]])       # inf  — no edge
print(sum(1 for x in matrix[index["center"]] if x not in (0, INF)))   # 3 — degree
```

**Advantage:** Whether an edge exists between two vertices is answered by a single read,
in $O(1)$.

**Cost:** Memory is always $O(\lvert V \rvert^2)$ — independent of the number of edges.
Also, listing a vertex's neighbors requires scanning the entire row: $O(\lvert V
\rvert)$.

In an undirected graph the matrix is symmetric about its diagonal; storing only half
halves the memory but does not change the order.

#### Adjacency List

An **adjacency list** keeps, for each vertex, only the list of its neighbors.

```python
from collections import defaultdict

adjacency: dict[str, list[tuple[str, int]]] = defaultdict(list)
for a, b, weight in [("north", "center", 4), ("south", "center", 2),
                      ("east", "center", 7), ("west", "north", 3),
                      ("west", "south", 5)]:
    adjacency[a].append((b, weight))
    adjacency[b].append((a, weight))               # undirected: added both ways

print(sorted(adjacency["center"]))
# [('east', 7), ('north', 4), ('south', 2)]
print(len(adjacency["west"]))                      # 2   — degree read directly
print(any(neighbor == "east" for neighbor, _ in adjacency["west"]))   # False
```

**Advantage:** Memory is $O(\lvert V \rvert + \lvert E \rvert)$ — only existing edges
are stored. Traversing a vertex's neighbors takes time proportional to its degree.

**Cost:** Whether an edge exists between two vertices is found by scanning the list —
$O(\text{degree})$.

#### Sparsity Decides

The deciding criterion is the ratio of edge count to vertex count.

If a graph is **dense** ($\lvert E \rvert \approx \lvert V \rvert^2$), the matrix is
reasonable both in memory and in giving a constant-time edge query.

If a graph is **sparse** ($\lvert E \rvert \approx \lvert V \rvert$), the matrix stays
almost entirely empty. In a road network with ten thousand vertices and thirty thousand
edges, the matrix demands a hundred million cells; the adjacency list gets by with forty
thousand entries.

The large majority of real graphs are sparse: each city connects to a handful of cities,
each person to a few hundred people, each page to a few dozen pages. For this reason
**the default choice is the adjacency list**; the matrix is preferred when vertex count
is small or the graph is dense.

#### A Third Option: The Edge List

The plainest representation is a flat list of edges — this was the `edges` variable from
the previous lesson.

It is unsuited to traversal: finding a vertex's neighbors requires scanning the entire
list. It is, however, the right choice in two situations: algorithms that work **on all
edges** in sequence (such as a minimum-spanning-tree algorithm that sorts edges by
weight and processes them), and cases where the graph needs to be **stored or
transmitted**.

#### Comparison

| Operation | Adjacency matrix | Adjacency list | Edge list |
|---|---|---|---|
| Memory | $O(V^2)$ | $O(V + E)$ | $O(E)$ |
| Edge exists | $O(1)$ | $O(\text{degree})$ | $O(E)$ |
| Traverse neighbors | $O(V)$ | $O(\text{degree})$ | $O(E)$ |
| Add edge | $O(1)$ | $O(1)$ | $O(1)$ |
| Remove edge | $O(1)$ | $O(\text{degree})$ | $O(E)$ |
| Traverse all edges | $O(V^2)$ | $O(V + E)$ | $O(E)$ |

In the table, $V$ and $E$ denote the vertex and edge counts; "degree" is the neighbor
count of the vertex in question and behaves like a small constant in sparse graphs.

Do not let the equality in the fourth row mislead: adding an edge in the matrix is
constant time, but the matrix itself was allocated up front — adding a vertex requires
rebuilding the matrix. In the adjacency list, adding a vertex only opens a new entry.

#### Vertex Identities

In the examples above, vertices were referred to by string names. In large graphs this
produces two costs: a string hash is computed on every access, and every vertex name
sits in memory as a separate object.

The common solution is to give vertices **integer identities**. Names are scanned once,
each name is assigned a sequential number, and from then on every structure uses that
number as an index.

```python
names = ["center", "east", "north", "south", "west"]
identity = {name: i for i, name in enumerate(names)}

neighbor_list: list[list[int]] = [[] for _ in names]
for a, b in [("north", "center"), ("south", "center"), ("east", "center"),
             ("west", "north"), ("west", "south")]:
    neighbor_list[identity[a]].append(identity[b])
    neighbor_list[identity[b]].append(identity[a])

print(neighbor_list[identity["center"]])       # [2, 3, 1]
print([names[i] for i in neighbor_list[identity["center"]]])
# ['north', 'south', 'east']
```

The gain is not only speed: visited markers, distances, and parent records can also be
kept in flat arrays instead of mappings. This is a significant improvement both in
memory and in cache behavior, and it is the standard approach for libraries that work
with large graphs.

#### Effect on Traversal Cost

The cost of the traversal algorithms taken up in the next two lessons depends directly
on the representation. Each vertex is visited once and its neighbors are traversed:

- With an adjacency list the total cost is $O(V + E)$ — each edge is examined twice.
- With an adjacency matrix it is $O(V^2)$ — the entire row is scanned for each vertex,
  even where no edge exists.

In a sparse graph this is the difference between linear and quadratic. Representation
choice is therefore not a detail but a decision that determines the algorithm's cost
class.

As a third option, both representations can be kept together: an adjacency list for
traversal, an additional set for frequent edge tests. This approach, which trades memory
to make both operations cheap, is one of the cases where keeping the same data in more
than one structure is legitimate — a conscious use of the trade-off repeated since the
first lesson of this course.

#### Summary

- The adjacency matrix makes edge queries constant time; its memory is $O(V^2)$
  regardless of edge count.
- The adjacency list stores only existing edges; memory is $O(V + E)$, and traversing
  neighbors costs as much as the degree.
- The list suits sparse graphs, the matrix suits dense ones; most real graphs are
  sparse.
- The edge list is unsuited to traversal but suits algorithms that work over all edges
  and data transmission.
- Traversal algorithm cost depends on the representation: $O(V+E)$ with a list, $O(V^2)$
  with a matrix.

#### Next Step

With a representation in place, traversal can begin. The next lesson takes up
breadth-first search, which scans a graph layer by layer starting from an initial
vertex, and how it solves the unweighted shortest-path problem.

### Breadth-First Search

Source: https://academia.sh/en/courses/data-structures/breadth-first-search

Layer-by-layer traversal with a queue, visited marking, unweighted shortest path, and path reconstruction.

Level-order traversal in trees visited nodes layer by layer, and did so with a queue.
The same idea works in graphs — with one difference: a graph has cycles, and the same
vertex can be reached by more than one path.

**Breadth-first search** is a traversal that advances layer by layer according to
distance from the starting vertex.

#### Visited Marking

In a tree, every node was reached by exactly one path; a graph gives no such guarantee.
Without marking, the same vertex would enter the queue repeatedly, and if a cycle
exists, the traversal would never finish.

For this reason, every graph traversal keeps a **visited set**. A vertex is marked when
it is placed in the queue; a marked vertex is never added again.

The visited set is the only structural addition that separates graph traversals from
tree traversals; everything else is the same. It matters that marking happens
**while adding** to the queue. If it happened while removing instead, the same vertex
could be added multiple times before being removed once, and the queue would grow
unnecessarily.

#### The Algorithm

```python
from collections import deque

def breadth_first_search(adjacency: dict[str, list[str]], start: str):
    """Traverses layer by layer; returns (visit order, distances, parents)."""
    visited = {start}
    distance = {start: 0}
    parent: dict[str, str | None] = {start: None}
    order: list[str] = []
    queue = deque([start])

    while queue:
        vertex = queue.popleft()               # first in, first out
        order.append(vertex)
        for neighbor in adjacency.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)          # mark while adding
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)
    return order, distance, parent


adjacency = {
    "west":   ["north", "south"],
    "north":  ["west", "center"],
    "south":  ["west", "center"],
    "center": ["north", "south", "east"],
    "east":   ["center"],
}

order, distance, parent = breadth_first_search(adjacency, "west")
print(order)          # ['west', 'north', 'south', 'center', 'east']
print(distance)       # {'west': 0, 'north': 1, 'south': 1, 'center': 2, 'east': 3}
```

The visit order follows the layers: first the start, then everything one edge away,
then everything two edges away. The `center` vertex is reachable through both `north`
and `south`; marking ensures only the first of these is considered.

#### Unweighted Shortest Path

The most important property of breadth-first search shows up here: **the distances it
finds are the shortest-path lengths in an unweighted graph.**

The reasoning lies in the layered advance. When a vertex is reached for the first time,
every vertex processed so far is at a closer or equal distance; a shorter path is
therefore impossible to find later. This is a direct consequence of the queue's
first-in-first-out behavior — had a stack been used, the guarantee would disappear.

Once parent records are kept, the path itself can be reconstructed:

```python
def build_path(parent: dict[str, str | None], target: str) -> list[str]:
    """Reconstructs the path to the target from the parent records."""
    if target not in parent:
        return []                              # unreachable
    path = []
    vertex: str | None = target
    while vertex is not None:
        path.append(vertex)
        vertex = parent[vertex]
    return list(reversed(path))


print(build_path(parent, "east"))     # ['west', 'north', 'center', 'east']
print(build_path(parent, "none"))     # []
```

The path is traced backward from the target and then reversed. The same technique is
also used in the weighted shortest-path algorithms taken up in the next course.

Once weight enters the picture, breadth-first search is no longer enough: a few heavy
edges can cost more than many light ones. That case requires algorithms that use a
priority queue instead of a plain queue; the heap from the trees topic is one of the
basic building blocks of graph algorithms for this reason.

The same technique can also be applied **bidirectionally** in searches where the target
is also known: two searches are started — one from the start, one from the target — and
the path is found once they meet. Because each search advances only to half the depth,
the number of vertices visited drops noticeably; the gain is large in graphs with a high
branching factor.

#### Cost

Each vertex enters the queue at most once, and each edge is examined at most twice (once
from each end, in an undirected graph). With an adjacency list the total cost is:

$$
O(\lvert V \rvert + \lvert E \rvert)
$$

The memory cost is the largest number of vertices that can be in the queue at once — the
width of the widest layer. In wide, shallow graphs this number can be large; it is the
same observation made for level-order traversal in trees.

#### Multi-Source Search

Breadth-first search is not limited to a single starting vertex. If multiple vertices
are placed in the queue from the start, the traversal spreads **from all sources at
once**, and the distance found for each vertex is its distance to the nearest source.

```python
def multi_source(adjacency: dict[str, list[str]], sources: list[str]) -> dict[str, int]:
    """Returns, for each vertex, its distance to the nearest source."""
    distance = {s: 0 for s in sources}
    queue = deque(sources)
    while queue:
        vertex = queue.popleft()
        for neighbor in adjacency.get(vertex, []):
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance


print(multi_source(adjacency, ["west", "east"]))
# {'west': 0, 'east': 0, 'north': 1, 'south': 1, 'center': 1}
```

In the single-source search, the distance of the `center` vertex was two; with two
sources it becomes one, because it is a neighbor of `east`.

This pattern solves problems such as "each cell's distance to the nearest water source"
or "each vertex's latency to the nearest server" in a single pass, without running a
separate search for each source. Doing the same work with one search per source would
multiply the cost by the number of sources.

#### Uses

**Fewest-step solution.** When a puzzle's states are vertices and moves are edges,
breadth-first search finds the solution with the fewest moves.

**Connected components.** Starting a search from every unvisited vertex splits the
graph into its components. The question from the disjoint-sets lesson is answered here
by traversal; the difference is that the structure there works while edges arrive as a
stream.

**Bipartiteness test.** Layers are colored alternately with two colors; if an edge is
found between two vertices in the same layer, the graph is not bipartite.

**Spread patterns.** How far and in how many steps information reaches through a
network, an effect spreads through a community, or a fault propagates through a system.

**Web crawling.** Crawlers that follow links use breadth-first search to traverse by
distance from a starting address.

One last caution: the shortest-path guarantee of breadth-first search rests on treating
every edge as equally costly. The moment weights are added, the guarantee disappears
and a priority queue is needed instead of a plain queue; this explains the role of the
heap from the trees topic in graph algorithms. If only part of the weights differ — for
example, some edges cost zero and others cost one — an intermediate solution using a
double-ended queue can also be used.

#### Summary

- Breadth-first search advances layer by layer by distance from the start, using a
  queue.
- Because the same vertex can be reached by more than one path in a graph, visited
  marking is required; marking happens while adding to the queue.
- The distances found are the shortest-path lengths in an unweighted graph; the
  guarantee comes from the queue's first-in-first-out behavior.
- Once parent records are kept, the path itself is reconstructed by tracing backward.
- Cost is $O(V + E)$ with an adjacency list; memory depends on the widest layer.
- Breadth-first search is not enough for weighted graphs; algorithms using a priority
  queue are needed.

#### Next Step

Breadth-first search prioritizes width: everything nearby is visited before anything
farther. The opposite strategy is to follow a single path to its end and only then turn
back. The next lesson takes up that strategy and the different family of problems it
solves.

### Depth-First Search

Source: https://academia.sh/en/courses/data-structures/depth-first-search

Deep traversal with a stack, recursive and explicit-stack forms, discovery–finish times, and cycle detection.

Breadth-first search advanced by distance: nothing farther away was visited before
everything nearby had been. **Depth-first search** follows the opposite strategy — it
follows a path until it is blocked, then returns to the last branching point and tries
another branch.

The structural difference is in a single place: a **stack** is used instead of a queue.
Whatever separates level-order and depth traversal in trees separates these two here as
well.

#### Recursive Form

The stack need not be kept explicitly; recursion uses the call stack for the same
purpose.

```python
def depth_first_search(adjacency: dict[str, list[str]], start: str) -> list[str]:
    """Traverses depth-first; returns the visit order."""
    visited: set[str] = set()
    order: list[str] = []

    def visit(vertex: str) -> None:
        visited.add(vertex)
        order.append(vertex)
        for neighbor in adjacency.get(vertex, []):
            if neighbor not in visited:
                visit(neighbor)                  # descend until blocked

    visit(start)
    return order


adjacency = {
    "west":   ["north", "south"],
    "north":  ["west", "center"],
    "south":  ["west", "center"],
    "center": ["north", "south", "east"],
    "east":   ["center"],
}

print(depth_first_search(adjacency, "west"))
# ['west', 'north', 'center', 'south', 'east']
```

On the same graph, breadth-first search gave the order `['west', 'north', 'south',
'center', 'east']`. In depth-first search, `center` is descended into immediately from
`north`; `south` is only visited once that branch is exhausted.

#### Explicit-Stack Form

The transformation built in the Programming Fundamentals course applies here as well:
an explicit stack can be kept instead of the call stack. In deep graphs this avoids
hitting the recursion limit.

```python
def depth_first_search_stack(adjacency: dict[str, list[str]], start: str) -> list[str]:
    visited: set[str] = set()
    order: list[str] = []
    stack = [start]
    while stack:
        vertex = stack.pop()                     # last in, first out
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
        for neighbor in reversed(adjacency.get(vertex, [])):
            if neighbor not in visited:
                stack.append(neighbor)            # push in reverse: preserves order

    return order


print(depth_first_search_stack(adjacency, "west"))
# ['west', 'north', 'center', 'south', 'east']
```

Pushing neighbors in reverse order rests on the same reasoning as pushing the right
child first in tree traversals: a stack returns items in the reverse of the order they
were pushed.

There is a subtle difference between the two forms: in the explicit-stack version, a
vertex can be pushed onto the stack more than once before being visited. For this
reason it is rechecked when popped. Memory use rises somewhat; behavior stays the same.

#### Discovery and Finish Times

The extra information depth-first search carries is two timestamps for each vertex:

- **Discovery time:** The moment the vertex is first reached.
- **Finish time:** The moment control returns to it after all its descendants have been
  visited.

These two values make it possible to classify the relationship between vertices. If one
vertex's discovery–finish interval fully contains another's, the second is a descendant
of the first; if the intervals do not overlap, the two vertices are in separate
branches. Intervals can never partially overlap — this is a direct consequence of the
stack structure of the traversal.

Finish times form the basis of the topological sort taken up in the next lesson.

#### Cycle Detection

One of the most common uses of depth-first search is looking for a cycle in a directed
graph. The distinction is between "visited" and "still on the stack": if the traversal
returns to a vertex that is **still open**, a cycle exists.

```python
def has_cycle(adjacency: dict[str, list[str]]) -> bool:
    """Tests whether a directed graph contains a cycle."""
    visited: set[str] = set()
    open_set: set[str] = set()                   # currently on the stack

    def visit(vertex: str) -> bool:
        visited.add(vertex)
        open_set.add(vertex)
        for neighbor in adjacency.get(vertex, []):
            if neighbor in open_set:
                return True                       # back edge: cycle
            if neighbor not in visited and visit(neighbor):
                return True
        open_set.discard(vertex)                  # branch completed
        return False

    return any(visit(v) for v in adjacency if v not in visited)


acyclic = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
cyclic = {"a": ["b"], "b": ["c"], "c": ["a"]}

print(has_cycle(acyclic))     # False
print(has_cycle(cyclic))      # True
```

Without the `open_set`, testing with `visited` alone gives a wrong result: in the
`acyclic` graph, vertex `d` is reached by two different paths, but this is not a cycle.
Separating the two concepts is therefore necessary.

#### Comparing the Two Traversals

| Criterion | Breadth-first search | Depth-first search |
|---|---|---|
| Auxiliary structure | Queue | Stack (or recursion) |
| Advance | Layer by layer | Deep along a branch |
| Unweighted shortest path | Finds it | Does not |
| Memory | Widest layer | Deepest path |
| Natural use | Distance, spread, fewest steps | Cycles, ordering, backtracking |
| Cost | $O(V + E)$ | $O(V + E)$ |

The fourth row can be decisive in a practical choice: in a wide, shallow graph, the
queue in breadth-first search grows very large; in a deep, narrow graph, the stack in
depth-first search does.

The third row is the source of the most common mistake: depth-first search finds a
path, but there is no guarantee that the path it finds is the shortest.

#### Iterative Deepening

The comparison table shows a dilemma: breadth-first search finds the shortest path but
can use a great deal of memory; depth-first search uses little memory but does not find
the shortest path.

**Iterative deepening** combines the two. Depth-first search is first run with a depth
limit of one; if no solution is found, the limit is raised to two, and the search is
run again from the start. The limit keeps rising as the search deepens.

At first glance this looks wasteful — the same upper layers are revisited again and
again. But when the branching factor is greater than one, most of the vertices are in
the **last layer**; the repeated work remains a small fraction of the total. The cost
ends up in the same order as breadth-first search.

The gain is in memory: only a single path is kept on the stack at any moment. The first
solution found is also the shallowest one, because no solution was found at smaller
limits.

The method is preferred in problems where the search space is not known in advance and
does not fit in memory — game-tree search, puzzle solving.

#### Uses

- **Cycle detection.** As above; the validity of dependency graphs is checked with this
  test.
- **Connected components.** As with breadth-first search, a traversal is started from
  every unvisited vertex.
- **Topological sort.** The reverse of finish times gives a valid ordering; the subject
  of the next lesson.
- **Backtracking.** Maze solving, puzzle filling, and constraint-satisfaction problems
  are applications of depth-first search over a choice tree.
- **Path finding.** When any path between two vertices is wanted — not necessarily the
  shortest — depth-first search produces a result with less memory.

#### Summary

- Depth-first search follows a path until it is blocked, then returns to the last
  branching point; it uses a stack instead of a queue.
- The recursive form uses the call stack; the explicit-stack form is safe in deep
  graphs.
- Discovery and finish times encode the ancestry relationship between vertices;
  intervals either contain one another or are disjoint.
- Cycle detection requires distinguishing "visited" from "still open."
- Breadth-first search finds the shortest path, depth-first search does not; their
  memory behavior diverges according to the shape of the graph.
- Both traversals cost $O(V + E)$.

#### Next Step

In graphs that model dependency relationships, the real question is this: in what order
should the work be done? The final lesson of the course takes up topological sort, which
produces a valid execution order in directed acyclic graphs, and brings together the
structures this course has built.

### Topological Sort

Source: https://academia.sh/en/courses/data-structures/topological-sort

Producing a valid execution order from a dependency graph, an in-degree-based algorithm, cycle detection, and uses.

Directed acyclic graphs were introduced in the concept-of-a-graph lesson as the natural
model of dependency relationships: an edge means "this task must be done before that
one."

This lesson's question is directly practical: given a set of dependencies, how is a
valid **execution order** found?

#### Definition and Existence Condition

A **topological sort** is an arrangement of all the vertices in a graph such that every
edge goes left to right in the list: if an edge `a → b` exists, `a` comes before `b` in
the list.

Only one condition is needed for such an ordering to exist: **the graph must be
acyclic.** If a cycle exists, every vertex in the cycle would have to come before
itself, which is impossible.

The condition means the sorting algorithm is also a cycle tester: if all vertices
cannot be sorted, the graph contains a cycle.

#### The In-Degree-Based Algorithm

The most intuitive method is to start from the tasks that have no dependencies left.

1. Compute the **in-degree** of every vertex — how many edges arrive at it.
2. Place the vertices with in-degree zero in a queue; these are waiting on nothing.
3. Take a vertex from the queue, add it to the ordering. Remove every edge leaving it:
   decrement the in-degree of its target; if it drops to zero, add it to the queue.
4. Continue until the queue is empty.

If, at the end, the number of vertices in the ordering is less than the total number of
vertices, the remaining vertices are part of a cycle.

```python
from collections import deque

def topological_sort(adjacency: dict[str, list[str]]) -> list[str] | None:
    """Returns a valid ordering; None if a cycle exists."""
    in_degree = {vertex: 0 for vertex in adjacency}
    for vertex in adjacency:
        for target in adjacency[vertex]:
            in_degree[target] += 1

    queue = deque(sorted(v for v in in_degree if in_degree[v] == 0))   # sorted for determinism
    result: list[str] = []

    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        for target in adjacency[vertex]:
            in_degree[target] -= 1                # dependency satisfied
            if in_degree[target] == 0:
                queue.append(target)

    return result if len(result) == len(adjacency) else None


# This curriculum's own prerequisite relationship is a dependency graph.
courses = {
    "bilgisayarlar-nasil-calisir": ["programlama-temelleri"],
    "programlama-temelleri":       ["veri-yapilari"],
    "veri-yapilari":               ["algoritmalar"],
    "modelleme-ve-gosterim":       ["algoritmalar"],
    "algoritmalar":                [],
}

print(topological_sort(courses))
# ['bilgisayarlar-nasil-calisir', 'modelleme-ve-gosterim',
#  'programlama-temelleri', 'veri-yapilari', 'algoritmalar']
```

The result is a reading order in which every course comes after its prerequisites.
`modelleme-ve-gosterim` comes out early because it has no prerequisites; `algoritmalar`
comes out last because it waits on two separate courses.

#### The Ordering Is Not Unique

For the same graph, there are generally several valid orderings. In the example above,
`modelleme-ve-gosterim` can be anywhere in the list as long as it comes before
`algoritmalar`.

This means the algorithm is making a choice: when more than one vertex is in the queue,
which one is taken is free. The implementation above uses alphabetical order so the
output is repeatable; another criterion could be chosen instead — taking the shortest
task first, for example.

The ordering is **unique** only when the graph forms a chain: at every step, exactly one
vertex is in the queue.

#### The Cycle Case

```python
cyclic = {
    "a": ["b"],
    "b": ["c"],
    "c": ["a"],       # cycle: a → b → c → a
}

print(topological_sort(cyclic))     # None
```

Because no vertex has in-degree zero, the queue is empty from the start and the result
stays empty. The length check catches this.

This is an alternative to the depth-first-search-based cycle detection from the
previous lesson. The two answer the same question; the in-degree-based method also
directly gives which vertices **cannot be ordered** when a cycle is found — those that
never enter the ordering. That set contains the vertices on the cycle, but is not limited
to them: a vertex reachable only through a cycle cannot enter the ordering either.

A second, depth-first-search-based method also exists: vertices are sorted by finish
time and the list is reversed. The result is equally valid; which method to choose
depends on the graph's representation and on whether cycle information is needed.

#### Layers and Parallel Execution

The flat list the algorithm produces is meant for sequential execution. If independent
tasks can run in parallel, a more useful output is **layers**: the set of tasks that
can be started at the same time.

Layers are the contents of the queue on each round — the same layer separation as in
breadth-first search:

```python
def layers(adjacency: dict[str, list[str]]) -> list[list[str]] | None:
    in_degree = {v: 0 for v in adjacency}
    for v in adjacency:
        for target in adjacency[v]:
            in_degree[target] += 1

    ready = sorted(v for v in in_degree if in_degree[v] == 0)
    result: list[list[str]] = []
    processed = 0
    while ready:
        result.append(ready)
        processed += len(ready)
        next_ready: list[str] = []
        for vertex in ready:
            for target in adjacency[vertex]:
                in_degree[target] -= 1
                if in_degree[target] == 0:
                    next_ready.append(target)
        ready = sorted(next_ready)
    return result if processed == len(adjacency) else None


print(layers(courses))
# [['bilgisayarlar-nasil-calisir', 'modelleme-ve-gosterim'],
#  ['programlama-temelleri'], ['veri-yapilari'], ['algoritmalar']]
```

The two courses in the first layer can be read at the same time; the second layer can
only start once the first is complete. The number of layers is the shortest time in
which all the work could finish given infinite parallelism — this value is called the
graph's **critical path length**.

#### Cost

Each vertex enters the queue at most once, and each edge is examined exactly once:

$$
O(\lvert V \rvert + \lvert E \rvert)
$$

Computing the in-degrees also scans every edge once; the total cost does not change.

#### Uses

**Build systems.** Dependencies between source files form a graph; which file compiles
first is decided by topological sort. The linking stage from the How Computers Work
course rests on this ordering.

**Package managers.** The install order of dependencies; a circular dependency is a
reason installation is refused.

**Task scheduling.** The execution order of interdependent jobs; in data pipelines, the
order in which steps run is determined this way.

**Spreadsheet recalculation.** When one cell changes, the order in which the cells that
depend on it are updated.

**Learning paths.** This curriculum's own prerequisite structure; the example above is
a real application.

#### Bringing the Course Together

This lesson is an example of the structures this course has built working together: the
graph is shown with a **mapping**, in-degrees are kept in a **counter**, ready vertices
wait in a **queue**, and the result accumulates in an **array**.

The principle repeated throughout the course also becomes visible here: every structure
makes one operation cheaper by making some other operation more expensive. An array
makes access cheap and insertion expensive; a linked list does the reverse. A hash table
reduces lookup to a constant and loses order. A tree preserves order and loses constant
time. A heap gives the extreme element but cannot search.

Choosing the right structure is therefore not "finding the best structure": it is
**knowing which operation is frequent and which is rare.** Algorithms, the subject of
the next course, asks the same question at the level of operations.

#### Summary

- Topological sort is an arrangement of vertices in which every edge goes left to right
  in the list.
- For the ordering to exist, the graph must be acyclic; the algorithm is also a cycle
  tester.
- The in-degree-based method starts from vertices with no dependencies left, and new
  ready vertices appear as edges are removed.
- For the same graph there are generally several valid orderings; the algorithm applies
  a criterion when choosing from the queue.
- Cost is $O(V + E)$.
- Build systems, package managers, task scheduling, and prerequisite structures use
  this ordering.

#### Next Step

This course built how data is organized and how that organization determines the cost
of operations. The next course — **Algorithms** — takes up the solutions that work on
these structures: how different solutions to a problem are compared, how cost is
expressed formally, and which methods solve sorting, searching, and graph problems.