3622
правки
Изменения
м
→Сравнение структур данных
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]]. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.
|-
| Отсортированный [[Список|список]]
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
| align="center" | Вариант [[Дерево поиска, наивная реализация|двоисного двоичного дерево поиска]] с добавлением инвариата "случайности", что уменьнашает ожидаемую высоту дерева.
|-
|[[АВЛ-дерево]]
