August 7th, 2011, 04:22 AM
I'm confused on the properties of Tries. I'm looking at a definition from Data Structures & Algorithms in Java 5th ed. and it gives the following:
A standard trie T storing a collection S of s strings of total length n from an alphabet of size d has the following properties-
*Every internal node of T has at most d children.
*T has s external nodes.
*The height of T is equal to the length of the longest string in S.
*The number of nodes of T is O(n).
My confusion is over the fact that tries are supposed to be commonly used to store things like dictionaries. T having s external nodes is the source of my confusion. Suppose I wish to add the following two words to the trie: "bar" and "bard".
After adding "bar", 'r' would be an external node accounting for one string in s. If I then add "bard" then that 'r' would no longer be an external node. Would I then just have two 'r' nodes coming from the 'a' node with one being internal and one being external, or can the words "bar" and "bard" simply not exist in the same trie?
August 8th, 2011, 10:10 AM
I figured this out once the school's email maintenance was done and I got in touch with my teacher. My homework assignment doesn't strictly adhere to the book's definition of a standard trie.