Black and red trees: Instertion and deletion

Insert a node in AVL: complicated rotation

AVL Insert with Double rotation

Delete a node in a treap

Treaps: Find in C++

bool CTree::find (CTree t, key x)
{
if (t== nullnode)
  return false;
else
  if (t->key == x)
    return true;
  else
     if (t->key < x)
       return find (t->right,x)
     else;
        return find (t->left,x)
}

Treaps

Trees + Heaps = TREAPS!!!

•  Data keys are organized as in a binary search tree 
•  Priorities organized as in a heap 
•  The priority of a node is always greater than the priorities of the children

Example: