Tries:Height of a Trie
Height of a Trie
In the worst case, a root-node to element-node path has a branch node for every digit in a key. Therefore, the height∗ of a trie is at most numberof digits + 1.
A trie for social security numbers has a height that is at most 10. If we assume that it takes the same time to move down one level of a trie as it does to move down one level of a binary search tree, then with at most 10 moves we can search a social-security trie. With this
many moves, we can search a binary search tree that has at most 210 − 1 = 1023 elements.
This means that, we expect searches in the social security trie to be faster than searches in a binary search tree (for student records) whenever the number of student records is more than 1023. The breakeven point will actually be less than 1023 because we will normally not be able to construct full or complete binary search trees for our element collection. Since a SS# is nine digits, a social security trie can have up to 109 elements in it.
An AVL tree with 109 elements can have a height that is as much as (approximately) 1.44 log2(109 + 2) = 44. Therefore, it could take us four times as much time to search for elements when we organize our student-record dictionary as an AVL tree than when this dictionary is organized as a trie!
Comments
Post a Comment