treap vs AVL Trees, Treap vs Red-Black Trees

general
, , , ,
1

Can anyone explain??
When to use what??
And can we use AVL trees/Red-black trees in problems where Treaps are used??
http://codeforces.com/blog/entry/3767

2

can anyone explain??

3

Insertion:

  1. Treap

  2. Skip List /RB tree (depending on input size: RB-tree faster with smaller input, skip list faster with larger input)

Search:

  1. Treap
  2. RB-tree
  3. Skip List

Removal:

  1. Treap
  2. Skip List
  3. RB-tree

also see this
stackoverflow

4

So you mean that treap will give better performance than RB-tree and AVL tree inspite of its property to degenerate??
And any reason y can’t we use RB-tree or AVL tree in problems where treap is used apart from the reasons you mentioned above??