I can't quite figure this out. Say you have a binary tree where the left or right nodes correspond to 0 or 1 and a group of levels form a chain which is the index of the node. So you have 10010 which is 18 in decimal, so index 18 (say we count from 1 instead of 0).

    0   1
   0 1 0 1
        0 1

We build up some binary tree/trie. I'm trying to figure out if you can delete and add nodes to the trie without having to rewrite the whole subbranch to the right of where you insert or delete, or if there is a simple few-step operation to somehow sort of rotate the tree branch on insert/delete such that you don't have to rewrite a big chunk of the tree. The reason is, you want to maintain the position of the nodes, so if you have nodes at position 6, 7, and 8, if you remove node 4, then they become positions 5, 6, 7. Do you get this for free somehow, or do you have to rewrite all of there positions in the tree? I can't quite see how it would look, wondering if one could explain how it would work.

  • $\begingroup$ Maybe the problem is that you try to treat a trie as a binary search tree? $\endgroup$ – Bulat Jul 19 '19 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.