The Del operation removes a key-value pair from the MerklePatriciaTree. While the delete operation's core idea is straightforward, it needs to maintain the trie's integrity and ensure that the remaining nodes are correctly restructured.
🪜 Steps to Execute a Delete:
Locate the Node: Start by traversing the trie to find the node corresponding to the key you intend to delete.
Leaf Node Deletion: If the located node is a leaf node:
Simply remove it from the trie.
Branch Node Handling: After deleting a key:
Check if the branch node has only one remaining child.
If so, remove the branch node and link its only child to the branch node's parent.
Extension Node Handling: If the path to the node being deleted passes through an extension node:
Check if the deletion results in the extension node having no unique path segments.
If so, merge the extension node with its only child.
HashNode Encountered: Upon encountering a HashNode during the delete traversal:
Fetch the actual node it references.
Continue the delete operation for this node.
Update Parent Nodes: Ensure that all parent nodes above the deleted node are updated to reflect the changes. This might involve recalculating hash values and adjusting child references.
Last updated