1
$\begingroup$

Problem: we have a sequence of numeric values, e.g. [102, 25, 77, 17, 2, 13]. We need to implement 3 operations, each can be at most logarithmic time complexity.

  1. insert(i, v) - inserts value v at index i.
  2. remove(i) - removes value at index i.
  3. peek(i) - returns value at index i.

What I've tried: AVL tree, where node keys are elements' indices. It theoretically guarantees log time for all three operations. The problem is when we use e.g. insert(0, v), we need to update all of the other indices (we want to keep the proper order), resulting in O(n) complexity. Sample sequence would look like this in my way of thinking:

sample avl tree

$\endgroup$

2 Answers 2

5
$\begingroup$

I think you have already a good idea with AVL trees.

To improve the data structure, you should keep track of the size of each subtree (and discard indices, they are not really useful here).

In details, a node $x$ of the tree should have the following information:

  • value;
  • size;
  • height;
  • pointer to the left child;
  • pointer to the right child.

There is no key in there, since those trees are not binary search trees, but the values are ordered by increasing indices when considering the in-order (like the keys in a BST). However, since the indices may change during the process, as you have stated, there is no use in storing those.

Peeking is the easiest algorithm:

define a.peek(i):
   s ← a.left.size
   if s = i then return a.value
   if s > i then return a.left.peek(i)
   return a.right.peek(i - s - 1)

To insert an element at position $i$, we search the position the same way as the peeking is done and continue in the left or right child (eventually with the node it replaces). All size and heigths or ancestors must be modified and some rotations may be necessary to keep the balance of each node.

define a.insert(i, v):
   if a is empty then
      a.value ← v
      a.size ← 1
      a.height ← 0
      a.left ← empty
      a.right ← empty
      return
   s ← a.left.size
   if s = i then
      if a.left.height < a.right.height then
         a.left.insert(i, v)
      else
         a.right.insert(0, a.value)
         a.value ← v
      a.size ← a.size + 1
      a.height ← 1 + max(a.left.height, a.right.height)
   else if s > i then
      a.left.insert(i, v)
      a.size ← a.size + 1
      a.height ← 1 + max(a.left.height, a.right.height)
      if a.left.height > a.right.height + 1 then
         do a right rotation
   else
      //similar insertion in the right child

When deleting a node, it need to be replaced. The easiest way to do it is to use a node in the child of greatest height, either the rightmost node in the left child or the leftmost node in the right child. Implementation left to you.

All those operations have time complexity linear in the height of the tree, which is logarithmic in the size, given that the balance is keeped.

$\endgroup$
6
  • 1
    $\begingroup$ Q1: why are all the operations invoked in context of a node? a.peek(i) or a.insert(i, v) are not valid imo. We perform these on a sequence rather than node. Q2: what is now AVL key of a node? The sequence element value? If so, this can break avl "no duplicates" rule $\endgroup$
    – YogoWafel
    Dec 28, 2022 at 0:20
  • $\begingroup$ A1: there is a clear bijection between a node and the subsequence of values contained in the corresponding subtree. That's why I use peek and insert on nodes. A2: there is no key, since this is not really a BST. I only use the structure of an AVL tree to keep the balance. As is, the structure allows duplicates (but "no duplicate" was not a constraint in your post). $\endgroup$
    – Nathaniel
    Dec 28, 2022 at 1:32
  • $\begingroup$ thanks for the inspiration, this approach seems great! However I encountered a problem with peeking after a left rotation. Possibly I corrupted the tree somehow? Peeking and insertion was done the way you suggested, but I'm not sure how the tree should look after my operations. Explained my problem here $\endgroup$
    – YogoWafel
    Dec 29, 2022 at 14:45
  • $\begingroup$ The insertion of $8$ at index $2$ should not need a rotation. The tree you should obtain is Node(Leaf(-1), 7, Node(Leaf(8), -2, Leaf(-3))) $\endgroup$
    – Nathaniel
    Dec 29, 2022 at 14:51
  • $\begingroup$ you're right, I messed up with the balance condition. However I still can't wrap my head around the insertion algorithm. Once again, similar example that returns $2$ instead of $7$ on peek(1)... $\endgroup$
    – YogoWafel
    Dec 29, 2022 at 21:58
2
$\begingroup$

You need to augment the AVL tree with weight information on every node (i.e. the number of nodes in the subtree rooted there).

Insertion and deletion will require to increment/decrement the weights of all nodes from the root to the insertion/deletion point.

Lookup will use the weight information to choose the descent directions.

Note that the index information remains implicit.

enter image description here

Searching for index $3$:

enter image description here

After deletion:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.