Блог пользователя Francesco4203

Trie deletion time complexity.
Автор Francesco4203, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить