1.

List the advantages of using Tries over Binary Search Trees (BSTs).

Answer»

The advantages of Tries over binary search trees (BSTs) are as follows:

  • It's quicker to lookup keys. In the WORST-case scenario, looking up a key of length m takes O(m) time. Because lockups are DEPENDENT on the depth of the tree, which is logarithmic in the NUMBER of keys if the tree is balanced, a BST does O(log N) key comparisons, where n is the number of items in the tree. As a result, a BST takes O(m log n) time in the worst scenario. Furthermore, log(n) will approach m in the worst-case scenario. Also, on real PROCESSORS, the simple actions Tries utilize during lookup, such as array indexing with a character, are quick.
  • Because nodes are shared between keys with common starting sub-sequences, tries with a large number of short keys are more space-efficient.
  • Tries facilitate longest-prefix matching, assisting in the discovery of the key with the longest possible prefix of characters, all of which are unique.
  • The length of the key is equal to the number of internal nodes from root to leaf. As a result, balancing the tree isn't an issue.


Discussion

No Comment Found