Hello everybody ! This is my first entry. I want to share with you my knowledge about treaps and to ask if you know any problems that use this data structure.
The treap is a combination between a heap and a BST. So , you have two values asociated with every node — the key and the priority.
The main properties are: 1. if you traverse it in inorder , your keys will be sorted 2. priority of every node is greater than the ones of the sons
Search: like in an usual BST.
Rotations: the idea behind the rotations is to keep the heap property , so if you want to swap w and z this goes like that
z w / \ / \ w c <=> a z / \ / \ a b b c
Insertion: you go to the right place and insert the new node as a leaf and then when you return you balance the tree ( that means you make roations to keep the heap property )
Deletion: you search for the specified key and move it downwards ( in left or in right — you have to keep the heap property ) ; when the node becomes a leaf you delete it
Split: you can split the treap in two treaps ( one with the keys smaller than the wanted value and one with the key bigger than the wanted value ) ; you will insert a new node with priority = infinity and key = value ; your new treaps will be the left and the right sons
Join: you can join two treaps in one new treap ; you can do this by inserting a new node having the sons the two treaps and than you will delete the inserted node
You can keep dynamic arrays with a treap as you can search the k-th value in an array at any time in O(log n). All the operation stated before are made in O(log n) ( except rotations which are made in O(1) ).