Изменения

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Вариант [[Дерево поиска, наивная реализация|двоисного дерево поиска]] с добавлением инвариата "случайности", что уменьнашает ожидаемую высоту дерева.

|[[АВЛ-дерево]]

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>