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.

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.

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.

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

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