Question

What happens if you call VEB-TREE-INSERT with an element that is already in the vEB tree? What happens if you call VEB-TREE-DELETE with an element that is not in the vEB tree? Explain why the procedures exhibit the behavior that they do. Show how to modify vEB trees and their operations so that we can check in constant time whether an element is present.

Answer 1

Let us consider that x is an element which is already in the vEB tree. If the insert operation is called on the vEB tree then it will cause an overflow. In order to resolve the issue we need to modify the code adding an else case.

Now let us assume that we want to delete an element not present in the vEB tree. If there is only one element in the tree then it will be deleted. But the else-if condition will not be executed as the tree size is not equal to 2. So, the max element will be deleted. In order to resolve this issue we need to use an auxiliary array A[] and update it with the condition:

A[x] = 0 if x is not in the tree.

Now for insertion we will check if A[x] = 0.

If it is true then we will set A[x] = 1 and perform the insert operation. If A[x] <> 0 then return.

Now for deletion we will check if A[x] = 1.

If it is true then we will set A[x] = 0 and perform the delete operation. If A[x] <> 1 then return.

Hope this helps.