[FEATURE REQUEST] Add Treap class in java

[ShreeHarish]

What would you like to Propose?

What would I like to propose?

A treap (short for "tree heap") is a type of balanced binary search tree that combines properties of both a binary search tree and a heap. It ensures that the tree remains balanced during operations like insertion and deletion, achieving good average-case time complexities for these operations.

Issue details

Issue details

The repository currently lacks implementation of Treap`

Additional Information

No response

[SaxenaPrashast]

Title:

"Add Treap Data Structure to the Repository"

Description:

I would like to propose the addition of the Treap (Tree Heap) data structure to the repository. A Treap is a randomized binary search tree that maintains the binary search tree property on the keys and a heap property on random priorities assigned to each node. This ensures that the tree remains balanced with an average-case time complexity of O(log n) for insertion, deletion, and search operations.

Why It’s Needed:

Currently, the repository does not include an implementation of a self-balancing binary search tree like a Treap. This data structure can be useful in situations where efficient insertion, deletion, and search operations are needed while keeping the structure simple and randomized, avoiding the complexity of manually balancing trees (e.g., AVL or Red-Black Trees).

Proposed Features:

1. Insert: Add a node by maintaining both the binary search tree and heap properties.
2. Delete: Remove a node while maintaining both properties.
3. Search: Perform standard binary search tree operations for key lookups.

Documentation:

I will provide clear inline comments and documentation explaining the purpose and use of the Treap. This will include examples of how to use the data structure.

[siriak]

Looks good, let's add it

[ShreeHarish]

@siriak I have added a pull request for this #5563. This is also my first time, so kindly ping me for any mods

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!