drzewo poszukiwań binarnych - może być listą - O(n)

drzewo AVL - niezmienniki gwarantuja zrównoważenie - O(\log n)

kopiec - w ogóle nie ma posortowania - O(n)

kopiec dwumianowy - j.w. - O(n)

drzewa czerwono-czarne - jak AVL - O(\log n)