Treap

What is a Treap?

A tree is a random binary search tree. A treap is a combination of heap and BST given the name (tree + heap = treap). A tree isn’t necessarily always perfectly balanced, but it guarantees a decent tree. It also boasts two extra operations, which would be impossible for other trees. The ability to merge and split with other trees

Building a Treap and Inserting

A tree uses the idea of priority in order to build the tree. It assigns a random priority value to each item before inserting it. The treap is a combination of a max heap (big numbers on top) and a binary search tree. This means it must satisfy two different conditions.

1. The BST Rule, where every left child’s value is less than its parent and every right child’s value is greater than its parent

2. The Max Heap Rule: each child’s priority is smaller than its parent’s priority.

The BST rule is satisfied as normal. If the current value is greater than the node, go right; otherwise, go left. Repeat until there is an open spot. Once a spot is found, rotations will be used to correct the positioning if the priority is wrong.

The situations for rotations in a tree go as follows:

• If the current node is a left child and it does not abide by the heap rule, rotate right on the current node.

• If the current node is a right child and it does not abide by the heap rule, rotate left on the current node.

Rotations will continue to occur until the priority constraint is met.

Search

Same as a BST.

Split and merge:

Both split and merge make use of the heap feature. They both create artificial nodes used to manipulate the tree.

Splitting:

For splitting the tree at the root:

1. Insert a node with a super-high value.

2. Rotate the node all the way until it is at the root.

   1. If the child is right, then rotate the node left.

   2. If left child, then rotate the node right.

3. Now the newly created node has the smaller valued tree on the left and the higher valued tree on the right.

For splitting the tree at a certain position:

1. Search for the location of the node (BST style).

2. Save the original value, then set it to a super high number.

3. Rotate that node all the way until it is at the root.

   1. If the child is right, then rotate the node left.

   2. If left child, then rotate the node right.

4. Once the node is at the root, The left child is the root of the smaller tree. The new root is the root of the bigger tree.

5. After separating the tree, remember to set the manipulated node back to its original value.

Conditions before doing a merge:

Pre requiestes:

In both operations, there will be treasuring involved. Each value in one treap needs to be greater than all of the other values in the other treap.

Treap 1 = smaller valued tree

Treap 2 = bigger value tree

For merging to treaps

1. Create a node with a super-small priority.

2. Make Treap 1 its left child and Treap 2 its right child (because of the pre-reqs, this means it obeys the BST rule).

3. Now rotate the tree because it has low priority and should end up as a left node.

4. Once a leaf node is removed from the tree

Deletion:

Deletion also used the advantages of a heap. I called it node X.

1. Find where node X is located (BST style).

2. Set the priority of node X to a super low value.

3. Rotate the nodes under node X. After enough operations, it should become a leaf node.

   1. If it has a left child rotate, it’s a left child right.

   2. If it only has the right child rotate, it’s the right child left.

4. Once a leaf node is discarded,