Treaps

Another variation of a binary search tree is a treap, which is a tree in which the nodes maintain two values:

1. data/key field
2. priority field

The data fields will be ordered using binary search tree properties and the priority fields will be ordered using heap order properties.

If the heap order is to maintain a max heap, then:

1. The nodes in the left subtree of the root will have data fields that are less than the data field of the root.
2. The nodes in the right subtree of the root will have data fields that are greater than the data field of the root.
3. The left and right subtrees are binary search trees.
4. The priority value of the root is greater than the priority value of its children.
5. The left and right subtrees are max heaps

If the heap order is to maintain a min heap, then:

1. The nodes in the left subtree of the root will have data fields that are less than the data field of the root.
2. The nodes in the right subtree of the root will have data fields that are greater than the data field of the root.
3. The left and right subtrees are binary search trees.
4. The priority value of the root is less than the priority value of its children.
5. The left and right subtrees are min heaps

Processing a treap

Searching

Searching a treap is implemented in the same manner as the searching of a binary search tree.

Insertion

Insertion of a node into a treap must ensure that both binary search tree and heap order properties are maintained. To do this, insert the node as a leaf node following binary search tree properties. If the heap order property is violated, then it will be restored by applying a rotation.

If the new node was inserted as a left child, then a right rotation will be performed with the inserted node and its parent.

If the new node was inserted as a right child, then a left rotation will be performed with the inserted node and its parent.

Deletion

Deletion of a node from a treap must ensure that both binary search tree and heap order properties are maintained throughout the treap. This is done by only deleting leaf nodes from the treap.

If the node to be deleted is already a leaf node, then simply delete it from the treap, making sure to set its parent's appropriate child pointer to null.

If the node to be deleted is not a leaf node, it will be rotated down the treap until it becomes a leaf node. If the left child of the node to be deleted has a higher priority than the right child of the node to be deleted, then a right rotation will be performed with the node to be deleted and its left child.

If the right child of the node to be deleted has a higher priority than the left child of the node to be deleted, then a left rotation will be performed with the node to be deleted and it's right child.

This process will be repeated until the node to be deleted becomes a leaf node.

Delete the node with key 4 from the following treap: