MultiwayTrieSet Flashcards
Multiway Trie is a motivated by:
ReTRIEVAL of words. Thus TREE is associated with TRIE
As a result of Binary Search Tree being (1) ___ complexity , and HashTable providing a (2) ____ complexity, MULTI-WAY TRIE was developed (by Edward Fredkin)
(1) BST can search a library of of words with O(log n) worst case and
(2) HashTable can search a library wiht O(k) worst case time complexity
Trie is considered a “prefix tree”
Element being stored are not represented by the value of a singe node, but the concatenation of labels on the path from root to the corresponding element.
Trie rely on
Edge Labels. These edge labels spell out the words to be stored
“word nodes” that are the “terminal” nodes or nodes with a boolean indicating that the current node produces a word in the lexicon, but additional nodes may still continue.
Multiway Trie has more than ___child edges
“two”
MWT always require starting from the root, traversing down its edges and ending on a node that has been labelled as a word node.
A word only exist if the final node that you have arrived on is labelled as a “word node”
MWT relies on the FIND() algorithm.
The find() function will follow the algorthm. If it fails that means the word does not exist and if it does the label of the “word node” is removed from the label and return true.
Inserting new words into a MWT involves:
If at any point the edge needed to continue building the word does not exist, we simply create the required edge and continue.
The letter labels EDGES of the trie, not the node.
An empty MWT is a single node tree with NO edges.
Inserting a single letter into the MWT (populating it with a single character) would entail creating a new node to join the originating root node, and connecting the root node to the new node. This is done to insert a new character/”word” into the MWT that is the size of one character.
Assume that, if you are given a node u and a character c, you can access the outgoing edge of u labeled by c (or determine that no such edge exists) in O(1) time. Given this assumption, what is the worst-case time complexity of the find, insert, and remove algorithms
O(k)
To output all the “elements” in the trie in a sorted order a _____ is performed
PRE-Order Traversal
ascendingPreOrder(node): // Recursively iterate over the words in ascending order
if node is a word-node:
output the word labeled by path from root to node
for each child of node (in asc
To output all the “elements” in the trie in a descending sorted order a _____ is performed
POST-Order Traversal
descendingPostOrder(node): // Recursively iterate over the words in descending order
for each child of node (in descending order):
descendingPreOrder(child)
if node is a word-node:
output the word labeled by path from root to node
How can “auto-complete” be implemented?
Use recursive pre-order traversal technique to provide useful function to our Multiway Trie
How can “auto-complete” be implemented?
Use recursive pre-order traversal technique to provide useful function to our Multiway Trie. Just start at the node with the current set of characters and then perform pre-order traversal
