Kalkwst / MicroLib

MIT License
3 stars 0 forks source link

:sparkles: Add Treap Implementation #43

Open Kalkwst opened 1 year ago

Kalkwst commented 1 year ago

A treap is a type of binary search tree that is used to efficiently store and retrieve data. It is a combination of a binary search tree and a heap. Each node in the tree has a key and a priority, where the key is used to organize the data in a hierarchical structure similar to a binary search tree, and the priority is used to maintain the heap property, where the parent node has a higher priority than its children. This allows for efficient operations like search, insert and delete with a time complexity of O(log n) where n is the number of nodes in the tree.

From a more technical perspective, a treap is a binary tree data structure that is built by combining a binary search tree and a heap. It has a key and a priority associated with each node, where the key is used to organize the data in a hierarchical structure similar to a binary search tree, and the priority is used to maintain the heap property, where the parent node has a higher priority than its children. This combination of a binary search tree and a heap allows for efficient operations like search, insert and delete with a time complexity of O(log n) where n is the number of nodes in the tree. Additionally, the heap property ensures that the height of the tree remains logarithmic, which ensures that the time complexity of the operations remains logarithmic as well. It's a randomized data structure, the priority is assigned randomly to each node, this way it can be used in situations where the data is not guaranteed to be sorted.