Binary search tree with constant random element functionality - PrismoSkills

Binary search tree with constant random element functionality - PrismoSkills

Problem: Design an advanced data structure which has all the functionalities of a binary search tree and
additionally it is also able to return a random number from the BST in logN time.


Solution: This is very similar to the previous problem.
Create a class containing a TreeNode<Object, Integer> and an ArrayList<Object>

Tree will provide the default functionality of a BST but will additionally store the index of the object in the array.
The ArrayList will store references to the objects in the map.

Insert operations: If the value was not present before, add it to the end of the ArrayList.
Then insert the object in the BST with key=object and value=ArrayList.size-1 (this gives the index of the object in the array).

Delete operations: Lookup index of object in the ArrayList from the BST.
Delete from the BST and then nullify the index in the ArrayList where the object was present.
To prevent developing holes in the ArrayList, move the last element of the ArrayList to the deleted index and update the index in the BST.

Read full article from Binary search tree with constant random element functionality - PrismoSkills