Define the concept of a treap.

A treap is a form of binary search tree data structure that maintains a dynamic set of ordered keys and allows binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.

Describe the procedure of removing an item from a binary search tree.
When removing an item from a search tree, it is imperative that the tree which remains satisfies the data ordering criterion.
  1. to remove a non-leaf node, it must be moved down in the tree until it becomes a leaf node since a leaf node is easily deleted.
  2. to move a non-leaf node down in the tree, we either swap it with the smallest key in the right subtree or with the largest one in the left subtree.
Describe the algorithm of inserting data into a binary search tree.

In order to insert data into a binary search tree you have to perform the following steps: a) pretend that the item is already in the tree and follow the path taken by the find routine to determine where the item would be. b) assuming that the item is not already in the tree, the search will be unsuccessful and will terminate with an external, empty node which is precisely where the item to be inserted is placed.

What is a binary search tree?
A binary search tree is a finite set of keys which satisfies the following properties:
  1. a) all the keys contained in left subtree are less than the value of the subtree root
  2. all the keys contained in the right subtree are greater than the value of the subtree root
Give example of some types of search trees.

AVL Search Trees, M-Way Search Trees, B-Trees.