Francesco4203's blog

Trie deletion time complexity.
By Francesco4203, history, 3 years ago, In English

Hi guys, I've just learned a Trie's delete algorithm, which I believe to have a time complexity of O(n.m), where n is the length of the deleted key and m is the size of the set of characters used, as for every time we process a node, we need to check if it still has some other connections to other nodes or not, which takes O(m) time. However, almost every source says that it works in O(n) time. Can anyone please explain to me? Thank you for reading, have a nice day!

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can check if node has some other connections with a variable $$$cnt$$$ that is stored in every node. Such variable counts number of connections leading to some other nodes, so checking can be done in $$$O(1)$$$ with simple check $$$cnt==0$$$, when adding/deleting update its value.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Really thank you for that. But still, such implementation in the link check for the whole set of characters instead, and they still say that it works in O(n) time, which makes me really confused.

    → Reply