Data structure with AVL and Hash table

Question

Suggest a Data Structure for N elements that support on the following operations: Describe the Data Structure on a sketch and literally, describe how each method work.

\begin{array}{|c|c|c|c|} \hline Operation & Average Running Time & Deterministic Running Time \\ \hline Init(N)& &O(1)\\ \hline Insert(x)& O(log(n)) & O(log(n))\\ \hline Delete(x)& O(log(n))& O(log(n))\\ \hline getContinuous(KEY,k) & O(k) & O(max(k,log(n))\\ \hline \end{array}

---

getContinuous(KEY,k) - returns a list of the k successors to the element with key KEY

What I thought to do: Working with hash table that holds AVL trees instead of linked lists (this will ensue $O(logn)$ . I don't know though how to provide $getContinuous(KEY,k)$. Perhaps with another hash table? but how?

Thanks

Answer 1

Use an AVL and a hash table implemented by link-list. All leaves in the AVL are connected via a doubly link-list, and every leaf will contain a pointer to the corresponding entry in the hash table.

The hash table will translate a key to a pointer. The pointer will point to the corresponding element in the AVL.

When inserting a element, we first enter it to the AVL, deriving the order of the key in the AVL, and connecting the element to its next and previous leaves. Then, we insert the a pointer to the corresponding leaf in the AVL to the hash table. This takes $O(1)$ in worst case, as the hash table is implemented by a link list. Finally, we connect the AVL leaf entry with the hash table entry. It takes $O(\log n)$ in worst case.

When deleting an element, we first find it in the AVL. Then, since the AVL points to the hash table, we can delete the corresponding entry in the hash in $O(1)$. Finally, we delete the element in the AVL, and "fix" the link-list of leaves. It takes $O(\log n)$ in worst case.

getContinuous(KEY,k) is implemented as follows: We search the key in the hash table for at most $\log n$ steps. If it found- then using the pointer to the AVL leaf, and using the link-list of the leaves we found the $k$ successors. If the key was not found within $\log n$ steps, then we search the AVL using the regular search procedure, find the corresponding key, and imply the $k$ successors.

Of course, getContinuous(KEY,k) takes $O(k+\log n)= O(max(k,\log n))$ time in the worst case. However, it takes in average $O(1)$ steps to find the key in the hash table, and thus getContinuous(KEY,k) takes $O(k)$ time in average.