Adding Treap Data Structure

[Aimaanhasan]

Description of the data structure

A Treap is a randomized binary search tree. It is different from random binary search tree, because Treap allows to have add(x) and delete(x) operations. A node in a Treap is similar to a node in BST, as it has a data value, but also has a unique random priority attached to it. With this priority, it follows the heap property, i.e, every node's priority should be greater than the priority of its parent.

Add operation

A node is added into a Treap in a similar way to a Binary Search Tree, with comparing it's data value with each node, and getting added as a leaf. However, this node has a unique priority attached to it, which is assigned randomly on its creation. To justify the heap property, the node is then bubbled up into the tree using rotations.

Delete operation

A node is deleted from the Treap, by first trickling down the node by using rotations, until the node becomes a leaf and then it is removed from the tree.

Time Complexity

Both add and delete operations use find operation similar to BST, which takes O(logn) operation, and then the expected/amortized time to do rotations is O(1). Thus it takes O(logn) time.

Advantages of Treap

It allows to have a balanced binary search tree, resulting in efficient operations.

[Aimaanhasan]

I want to work on it to add this to PyDataStructs

[czgdp1807]

A node in a Treap is similar to a node in BST, as it has a data value, but also has a unique random priority attached to it. With this priority, it follows the heap property, i.e, every node's priority should be greater than the priority of its parent.

So, where should Treap go? In heaps.py or binary_trees.py? What do you say?

The description for Treap data structure is quite good however, we need some concrete APIs to discuss upon. Please come up with an API design. See an example for the same here.

[Aimaanhasan]

Treaps should go in binary_trees.py, as we will be needing the properties of BinarySearchTree and SelfBalancingBinaryTree. Moreover, for the heap property in Treaps, it can be done by just adding a check of heap property, while doing the rotations.

[Aimaanhasan]

API for Treap

In my opinion, this would be the API for this data structure.

Treap
A Treap is a randomized binary search tree. It is different from random binary search tree, because Treap allows to have insert(x) and delete(x) operations. A node in a Treap is similar to a node in BST, as it has a data value, but also has a unique random priority attached to it. With this priority, it follows the heap property, i.e, every node's priority should be greater than the priority of its parent.

It is inherited from SelfBalancingBinaryTree

Attribute
There are no attributes as all attributes needed are already in parent's class.

Methods
1. `insert(key, data)` - It will insert a new node in the tree, by calling the method in parent's class, by adding data as a `tuple` of data and a random priority.
2. `delete(key, **kwargs)` - Use the delete method in parent's class to delete the node with the key.

[czgdp1807]

Well, I just realised that, Treap is formed from, "Tre"e + He"ap". Also considering the quote from wikipedia,

The treap was first described by Raimund Seidel and Cecilia R. Aragon in 1989;[1][2] its name is a portmanteau of tree and heap. It is a Cartesian tree in which each key is given a (randomly chosen) numeric priority.

So, Treap is a Cartesian tree. Can we first work on Cartesian tree and then inherit it in Treap as this follows ISA relationship? What do you think?

See, https://en.wikipedia.org/wiki/Cartesian_tree#Treaps

[Aimaanhasan]

I have read upon Cartesian Trees a lot after this question. I have come up with two ways to implement this.

First Approach

We develop Cartesian Tree by inheriting it from BinaryTree, and then implement Treap by inheriting it from Cartesian Tree, however, we will have to override the insertion and deletion method, as Cartesian Tree do not follow properties of BinarySearchTree, when inserting it.

Second Approach

We develop Cartesian Tree by inheriting from BinaryTree, and then implement Treap by inheriting from both Cartesian Tree and BinarySearchTree, in this way we will only call the super methods of insert and delete of BinarySearchTree, doing the rotations where necessary.

Conclusion

In both cases, we are completely overriding the methods of Cartesian Tree. Therefore, we will not be using methods of Cartesian Tree at all. Can you guide me further, what you think is the best approach from the both approaches in this case?

[czgdp1807]

@Aimaanhasan Is is possible to perform insertion and deletion on Cartesian Trees. I tried to find out, see [1] and [2], and was unable to reach any algorithms for performing insertion and deletion.
Treaps have their insertion and deletion algorithms defined.

.. [1] https://en.wikipedia.org/wiki/Cartesian_tree
.. [2] https://courses.helsinki.fi/sites/default/files/course-material/4594509/cartesianproof.pdf
.. [3] https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf
.. [4] https://en.wikipedia.org/wiki/Treap

[Aimaanhasan]

For Cartesian Tree

Take a look at this [1]. It's the paper, by Vuillemin , where he introduced Cartesian Trees among Data Structures. In this paper, there is an algorithm for insertion. Moreover, the paper describes Cartesian Tree as a tree with nodes having a 2-D coordinate s i.e (x, y), where x follows the rules of BinarySearchTree, i.e node.left.x < node.x < node.right.x and y follows the rules of Heap, i.e node.parent.y < node.y. According to this, it's a proof that we can implement Cartesian Tree such that it follows the properties of BinarySearchTree and Heap both.

Therefore, we can implement CartesianTree such that it inherits from BinarySearchTree.

For insertion

Use the insert method of the super class i.e BinarySearchTree and then do the rotations to ensure the property of heap.

For deletion

Use the delete method by using the find method of parent class, then rotating the node multiple times such that the node becomes a leaf node, and then delete it simply.

For Treap

We can then implement Treap by simply inheriting from CartesianTree, by only making a change that the y coordinate, would be random.

.. [1] https://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/geo-st.pdf

[czgdp1807]

Thanks @Aimaanhasan
So, it looks that for Treaps we just need to inherit Cartesian Trees and the rest will be done by inheritance. If that's the case then I'd suggest to make a PR to add both Cartesian Tree and Treaps at once.

[czgdp1807]

Note that we may need to make a new kind of node to store the key and priority in a single node. Currently, only key attribute is there in TreeNode classes. For consistency, please use arrays internally for storing trees. After going through the current implementation you should be able to get the point.
P.S. Are you participating through RGSoC, 2020?

[Aimaanhasan]

Yes, I am participating through RGSoC 2020. Moreover, I'll make a PR for both Cartesian Trees and Treaps. I'll take a look on how to use arrays internally for storing trees, and ask you if there is any confusion

[czgdp1807]

Then please make sure to submit your application on RGSoC website before, 30th March, 23:00 UTC with a minimum of two coaches. If you face any problem while arranging coaches then please send an invite to me, @pristineVedansh and if needed to @anukritijha246 If your team is already having 2 coaches then not a problem.