Алгоритмы trainee
Что такое AVL и красно-чёрное дерево?
Ответ
Самобалансирующиеся BST. После каждой вставки/удаления выполняется ребалансировка через повороты — гарантия O(log n). AVL — строже балансируется (быстрее поиск, медленнее вставка), красно-чёрное балансируется слабее (дешевле вставки, чуть медленнее поиск).
Разбор: И AVL, и красно-чёрное — самобалансирующиеся бинарные деревья поиска, которые после вставок/удалений восстанавливают баланс поворотами, давая гарантированную высоту O(log n); AVL держится строже (быстрее поиск, дороже модификации), красно-чёрное балансируется слабее (дешевле вставки). Дистракторы путают их с хеш-таблицами и B-деревьями и ложно утверждают, что балансировки нет вовсе.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.