Fair enough, but I personally believe the AVL structure is sufficiently simple. Let me compare treaps and AVL trees: Both insert at the same point, then procee

Fair enough, but I personally believe the AVL structure is sufficiently simple. Let me compare treaps and AVL trees: Both insert at the same point, then proceed to rebalance. The treap will rotate upwards until p_new>p_parent. The AVL will update balance information upwards until bal_parent%2==1, then update and possibly rotate once. That's a couple of conditional operations extra, and field operations instead of tree operations. The final step in particular is less elegant, but straggling cleanup operations are everyday things and well worth the better performance, to me.