Worked examples — Deletion in open addressing — tombstone markers

This page runs the tombstone machine through every situation it can face. We build one small map of "case classes," then work examples until each cell is covered — including the weird corners: deleting the last live key, deleting into an all-tombstone table, a wrap-around chain, and a rehash that clears the graveyard.

---

The scenario matrix

Before working anything, here is the full grid of cases this topic can throw at you. Every worked example below is tagged with the cell it covers, so you can see nothing is skipped.

Cell	Case class	What makes it special
A	Delete a middle key of a collision chain	The classic bug the tombstone fixes
B	Delete the first key ($h(k)$ slot itself)	The chain's head becomes †
C	Delete the last key of a chain	Could we use EMPTY here? (edge reasoning)
D	Search a key that is genuinely absent	Must still stop at EMPTY, walk past †
E	Insert reuses a tombstone — no duplicate ahead	Place at remembered †
F	Insert scans past a tombstone — duplicate exists ahead	Must NOT create a duplicate
G	Wrap-around chain crossing the array end	Probe indices go $\mathrm{mod}m$
H	Degenerate: all slots tombstoned, table "empty" of live keys	${\alpha }_{\text{eff}}$ high, $n_{\text{occupied}}=0$
I	Limiting behaviour: tombstones pile up → rehash	Cost forecast + rebuild
J	Word problem (lockers) + exam twist	Apply to a story / count probes

We now cover each cell.

---

Example 1 — Cell A: deleting a middle key

Steps.

1. Insert 10 → slot 3 (empty). Why this step? $h(10)=3$, slot free, place it.
2. Insert 17 → $h(17)=3$ occupied by 10, probe 4, empty → place. Why? Collision, linear probe to next slot.
3. Insert 24 → 3 (=10), 4 (=17), 5 empty → place. Table: [_ _ _ 10 17 24 _].
4. Delete 17 → set slot 4 to †, not EMPTY. Why? Slot 4 is in the middle of the chain 3→4→5; EMPTY would cut it. Table: [_ _ _ 10 † 24 _].
5. Search 24: slot 3 (=10, no), slot 4 (=†, keep going), slot 5 (=24 ✓). Why? Search treats † like occupied.

Answer: 3 probes, found at slot 5.

Recall Verify

Without the tombstone (blank slot 4), search 24 hits EMPTY at slot 4 after 2 probes and wrongly returns "not found." The tombstone converts a false miss into a correct hit at 3 probes. ✓

---

Example 2 — Cell B: deleting the head of the chain

Steps.

1. Delete 10 → slot 3 becomes †. Table: [_ _ _ † 17 24 _]. Why not EMPTY? Search for 17 and 24 starts at slot 3; EMPTY there would immediately report them missing.
2. Search 24: slot 3 (=†, keep going), slot 4 (=17, no), slot 5 (=24 ✓). Why? The head tombstone is walked through like any occupied slot.

Answer: 3 probes, found. Deleting the head is no different from a middle — the head slot is inside the probe sequences of everything that collided there.

Recall Verify

Slot 3 = †, slot 4 = 17, slot 5 = 24. Search 24 touches slots 3,4,5 → 3 probes, success. ✓

---

Example 3 — Cell C: deleting the last key of a chain

Steps.

1. Note slot 6 (right after 24) is already EMPTY. Why relevant? No live key sits past slot 5, so blanking slot 5 would not cut off any current key.
2. If we set slot 5 EMPTY → [_ _ _ 10 17 _ _]. Search 17: slot 3 (10), slot 4 (17 ✓) — still works. Search 24: slot 3,4,5(EMPTY) → correctly "not found." So EMPTY is technically safe right now.
3. But the standard rule still says use †: [_ _ _ 10 17 † _]. Why insist? Simplicity + safety: deciding "am I the last of my chain?" requires scanning forward, and a future insert could extend the chain past slot 5, re-creating a mid-chain hole. Uniform † avoids case analysis.

Answer: EMPTY happens to work for the tail, but tombstones are still used — a uniform rule beats a fragile special case.

Recall Verify

Tail-tombstone table [_ _ _ 10 17 † _]: search 17 touches 3,4 → 2 probes, success. Search 24 touches 3,4,5(†),6(EMPTY) → 4 probes, correct miss. ✓

---

Example 4 — Cell D: searching a genuinely absent key

Steps.

1. slot 3 (=10, no). Why continue? Occupied but not our key.
2. slot 4 (=†, keep going). Why? Tombstone ≠ chain end.
3. slot 5 (=24, no). Continue.
4. slot 6 (=EMPTY → STOP). Why stop? EMPTY is the only honest "chain ended" signal.

Answer: 4 probes, correctly "not found." The tombstone did not fool us — only EMPTY halts the search.

Recall Verify

Absent-key search touches slots 3,4,5,6 → 4 probes, terminates at EMPTY, returns absent. ✓

---

Example 5 — Cell E: insert reuses a tombstone (no duplicate ahead)

Steps.

1. slot 3 (=10, not 38). Remember: no tombstone seen yet.
2. slot 4 (=†). Record this as the first tombstone (firstTomb = 4) but keep scanning. Why keep going? 38 might already exist later in the chain — stopping now risks a duplicate.
3. slot 5 (=24, not 38). Continue.
4. slot 6 (=EMPTY → stop scanning). No duplicate 38 found. Why stop here? EMPTY guarantees 38 is not further along.
5. Place 38 at firstTomb = 4. Table: [_ _ _ 10 38 24 _]. Why slot 4, not 6? Reusing the tombstone keeps chains short and reclaims graveyard space.

Answer: 38 lands at slot 4, reclaiming the tombstone.

Recall Verify

Final: slot 3=10, slot 4=38, slot 5=24. Later search 38 touches 3,4 → 2 probes, success. ✓

---

Example 6 — Cell F: insert must NOT create a duplicate

Steps.

1. slot 3 (=10). Key already present! STOP — do not insert. Why? Duplicate keys break the "one slot per key" model and future deletes.
2. (If we had naively used slot 4's tombstone first, we'd hold two copies of 10 at slots 3 and 4 — a duplicate.)

Answer: no insertion; 10 already exists at slot 3. This is exactly why insert scans for the key even after spotting a tombstone.

Recall Verify

Table unchanged [_ _ _ 10 † 24 _]; count of key 10 = 1. Duplicate avoided. ✓

---

Example 7 — Cell G: wrap-around chain

Steps.

1. Insert 4 → slot 4. Why? $h(4)=4$, free.
2. Insert 9 → slot 4 occupied, probe $(4+1)\mathrm{mod}5=0$ → place at slot 0. Why mod 5? Index 5 doesn't exist; wrap to the front.
3. Insert 14 → 4 (=4), 0 (=9), $(4+2)\mathrm{mod}5=1$ → slot 1. Table: [9 14 _ _ 4].
4. Delete 9 → tombstone at slot 0: [† 14 _ _ 4]. Why? Slot 0 is mid-chain (4→0→1); EMPTY would break it.
5. Search 14: slot 4 (=4, no), slot 0 (=†, keep going), slot 1 (=14 ✓). Why start at 4? $h(14)=4$; the probe wraps 4→0→1.

Answer: 3 probes, found — wrap-around works because indices are always taken $\mathrm{mod}m$.

Recall Verify

Probe order for 14 is $[4,0,1]$; slot 1 holds 14 → 3 probes, success. ✓

---

Example 8 — Cell H: the all-tombstone degenerate table

Steps.

1. After the three deletes: [† † † _ _], $n_{\text{occupied}}=0$, $n_{\text{tombstones}}=3$.
2. Search 20: slot 0 (†), slot 1 (†), slot 2 (†), slot 3 (EMPTY → stop). Why 4 probes for an empty table? Search must walk every tombstone before the first EMPTY.
3. Compute ${\alpha }_{\text{eff}}=\frac{n_{\text{occupied}}+n_{\text{tombstones}}}{m}=\frac{0+3}{5}=0.6$, while the live load factor is $0/5=0$.

Answer: 4 probes to confirm 20 is absent — in a table with zero live keys. This is the tombstone tax made visible: cost tracks ${\alpha }_{\text{eff}}$, not live occupancy. See Load Factor and Rehashing.

Recall Verify

Absent-search touches slots 0,1,2,3 → 4 probes; ${\alpha }_{\text{eff}}=3/5=0.6$; live load = 0. ✓

---

Example 9 — Cell I: limiting behaviour → rehash

Steps.

1. Plug ${\alpha }_{\text{eff}}=0.6$ into $\frac{1}{2}\left(1+\frac{1}{(1-{\alpha }_{\text{eff}}{)}^2}\right)$. Why this tool? It is the standard estimate for unsuccessful linear-probing search cost, and it depends on ${\alpha }_{\text{eff}}$ — precisely what tombstones inflate.
2. $(1-0.6{)}^2=0.16$, so $\frac{1}{0.16}=6.25$, then $\frac{1}{2}(1+6.25)=3.625$ expected probes. Why care? A live-empty table "should" cost ~1 probe; tombstones push it to ~3.6.
3. Rehash: reinsert only OCCUPIED entries into a fresh array. Here there are none → new table [_ _ _ _ _]. Why? Rebuild drops all †.
4. New ${\alpha }_{\text{eff}}=\frac{0+0}{5}=0$. Why it matters: search cost collapses back to ~1 probe.

Answers: (a) ≈ 3.625 expected probes; (b) ${\alpha }_{\text{eff}}=0$ after rehash.

Recall Verify

$\frac{1}{2}(1+1/(1-0.6{)}^2)=3.625$; post-rehash ${\alpha }_{\text{eff}}=0/5=0$. ✓

---

Example 10 — Cell J: word problem + exam twist

Steps.

1. Start: [_ _ _ 3 10 17 _]. Tombstone locker 4 (10 graduated): [_ _ _ 3 † 17 _].
2. Insert 24: locker 3 (=3, no), locker 4 (=†, record firstTomb=4, keep scanning), locker 5 (=17, no), locker 6 (EMPTY → stop, no duplicate). Place 24 at firstTomb=4. Why 4? Reuse the tombstone (Cell E logic). Table: [_ _ _ 3 24 17 _].
3. (a) Answer: locker 4.
4. Search 31: locker 3 (=3), 4 (=24), 5 (=17), 6 (EMPTY → stop). Why 4 inspections? Three occupied + one EMPTY to confirm absence.
5. (b) Answer: 4 lockers inspected.

Recall Verify

24 lands at locker 4; absent-search 31 touches lockers 3,4,5,6 → 4 inspections, correct miss. ✓

---

Recap — matrix coverage

Recall

Which example covered "insert must not duplicate a key already ahead in the chain"? ::: Example 6 (Cell F). Which cell showed a table with zero live keys still costing 4 probes? ::: Cell H (Example 8) — all tombstones, ${\alpha }_{\text{eff}}=0.6$. After rehashing an all-tombstone table with no live entries, what is ${\alpha }_{\text{eff}}$? ::: $0$ (Example 9). Why is a tombstone still used when deleting the tail of a chain? ::: Uniform rule; a future insert could extend the chain and re-create a mid-chain hole (Example 3, Cell C).

---

Connections

• Parent topic — tombstone markers
• Open Addressing — the setting for every example here.
• Linear Probing — the probe sequence $h(k)+i\mathrm{mod}m$ used throughout.
• Load Factor and Rehashing — the ${\alpha }_{\text{eff}}$ cost and rehash cure (Examples 8–9).
• Hash Functions — the $h(k)=k\mathrm{mod}m$ that starts every probe.
• Separate Chaining — the alternative where delete is trivially O(1).