O(logn) to insert and delete node from specific position of linked list?-CodePudding

I was thinking if it was possible to come up with a faster solution than O(N) to inserting or deleting from a specific index of a doubly or singly linked list. I came up with part of a O(logN) solution but got stuck. I was wondering if anyone could continue on the solution or show that it won't work.

Use Self Balanced BST: the index of the nodes are keys and the pointers to nodes in the linked list are the value. When inserting into BST at index = X, find key=X in O(logn), then insert a new node between this index=X and the parent. Since this is a different insertion process than normal, we'd need to update all children nodes' weight. Additionally, everything to the right subtree needs to be incremented by 1 to represent the index shift of nodes in the LL. This would take O(n) time, so we'd need to figure out a way to efficiently do this.

The idea would be to wait until a new search or a balancing process in order to update the children. Hold two additional booleans in each node: one to determine if all the left children need to be incremented and likewise for the right side.

Now we've pushed off the work to while we perform a search, we increment the key and also change the booleans as needed.

The problem is during balancing. It seems really complicated and cannot find a specific solution. Also, there are a few different styles of trees which I'm not familiar with. Any ideas?

Also, has this problem been thought of before?

CodePudding user response：

Use Self Balanced BST

Yes, that is the solution.

the index of the nodes are keys [...] Additionally, everything to the right subtree needs to be incremented by 1 to represent the index shift of nodes in the LL. [...] The idea would be to wait ...

This is not the right idea. Instead of storing the index, maintain a size attribute that stores the number of nodes that are in the subtree that the node is the root of. So if the node is a leaf, that size is 1 (the node itself). It it has two children which are leaves then it will be 3, etc.

The problem is during balancing.

That would indeed be difficult with your idea. With a size attribute it will be easier.

First: the algorithm for finding an index, will be like this:

If the index is less than the size of the left subtree, then go left, else go right in which case the index is reduced by the size of the left subtree.
Continue this process until the index is 0.
In case a new node needs to be inserted insert it there, and increase the size attribute of every node that you traversed with the above process (i.e. on the path from the root to the inserted leaf).

For balancing, you can use AVL rotations. This means nodes also need to be equiped with a balancing factor (standard feature of AVL). In addition to the standard AVL rotation algorithm, you'll need to update the size attribute of the rotated nodes, but that is just a matter of adding/subtracting sizes of the involved nodes.