Make delicious recipes!

Binary search tree with constant random element functionality

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.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal