Untitled

What is Soft Deletion in a Trie?
Soft deletion means that instead of physically removing nodes from the Trie when a word is deleted, we simply update the metadata (like cntEndWith and cntPrefix) to reflect the deletion. The structure of the Trie remains intact, and the nodes are not removed unless they are no longer needed.

Why Use Soft Deletion?
Efficiency :
Physically removing nodes from the Trie can be computationally expensive because it requires traversing the Trie to clean up unused nodes.
With soft deletion, we only decrement counters (cntEndWith and cntPrefix), which is much faster.

Shared Prefixes :
In a Trie, multiple words may share common prefixes. For example, "adith" and "adithp" share the prefix "adith". If we physically delete "adith", we might accidentally remove nodes that are still needed for other words like "adithp".

Soft deletion ensures that shared prefixes remain intact while correctly reflecting the removal of a specific word.

Dynamic Updates :
Soft deletion allows the Trie to remain flexible for future insertions. For example, if you delete "adith" but later reinsert it, the Trie doesn't need to reconstruct the nodes—it just updates the counters again.