Андрей Гейн: Дерево ван Эмде Боаса — структура данных, позволяющая хранить массив из N целых чисел и очень быстро делать с ним удивительные вещи. Например, сортировать за O(N log log N) или проверять, есть ли в нём определённый элемент, за O(log log N). Субъективная сложность лекции — три теты из пяти. Содержание: 2:31 Особенности дерева ван Эмде Боаса 4:56 Операции SuccessorQuery и PredecessorQuery, их вычислительная сложность 10:22 Дерево ван Эмде Боаса 23:37 Вставка элемента (наивная реализация) 29:00 Хранение минимальных и максимальных элементов 33:58 Вспомогательные функции IsEmpty, Contains, High, Low 44:54 Вставка элемента (оптимальная реализация) 53:06 Удаление элемента 1:09:30 Операция SuccessorQuery 1:22:09 Оценка потребляемой памяти и способы оптимизации 1:29:36 Лирическое отступление про цифровой бор 1:32:59 Вычислительная сложность сортировки массива 1:35:29 Вычислительная сложность выделения памяти под дерево
