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. ///??? it's more complexity
Related: Set with constant random element functionality
Read full article from 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. ///??? it's more complexityRelated: Set with constant random element functionality
Read full article from Binary search tree with constant random element functionality - PrismoSkills
