What are main advantages of Tries over Binary Search Trees (BSTs)?

Technology CommunityCategory: Binary TreeWhat are main advantages of Tries over Binary Search Trees (BSTs)?
VietMX Staff asked 3 years ago

The following are the main advantages of tries over binary search trees (BSTs):

  • Looking up keys is faster. Looking up a key of length m takes worst case O(m) time. A BST performs O(log n) comparisons of keys, where n is the number of elements in the tree, because lookups depend on the depth of the tree, which is logarithmic in the number of keys if the tree is balanced. Hence in the worst case, a BST takes O(m log n) time. Moreover, in the worst case log(n) will approach m. Also, the simple operations tries use during lookup, such as array indexing using a character, are fast on real machines.
  • Tries are more space efficient when they contain a large number of short keys, because nodes are shared between keys with common initial subsequences.
  • Tries facilitate longest-prefix matching, helping to find the key sharing the longest possible prefix of characters all unique.
  • The number of internal nodes from root to leaf equals the length of the key. Balancing the tree is therefore no concern.