A Practical Guide to Data Structures and Algorithms using Java

Trie Data Structure 659

DigitizedOrderedCollection

throw new IllegalArgumentException(element + ‘‘ violates prefix-free requirement”);

TrieLeafNode<E> newNode = newLeafNode(element); //create the new leaf node

addNewNode(newNode, sd); //add it to the trie (sd is updated)

found = FindResult.MATCHED; //update found (to avoid a new search)

if (moveToPred(element, sd, found)) //maintain OrderedLeafChain Property

newNode.addAfter((TrieLeafNode<E>) sd.ptr);

else

newNode.addAfter(FORE);

size++; //preserve Size Property

return newNode; //return reference to the new leaf node

} finally {

pool.release(sd);

}

}

Correctness Highlights: By the correctness of find, if found ...