Все мы знаем, что в основе TreeMap, а следовательно и TreeSet, лежит красно-черное дерево. Чуть меньше людей знает о том, что оно самобалансирующееся, еще меньше знают, как именно оно балансируется. Я тут нашел отличное видео о том, как этот вид деревьев балансируется при вставке.
Есть набор свойств, которые дерево должно сохранять для того чтобы держать баланс (эти свойства слева сверху на видео). Для их достижения можно перекрашивать вершины или выполнять повороты. Очень круто показан весь процесс.
Теперь вас еще труднее поставить в тупик на собеседовании :)
https://www.youtube.com/watch?v=g9SaX0yeneU
Есть набор свойств, которые дерево должно сохранять для того чтобы держать баланс (эти свойства слева сверху на видео). Для их достижения можно перекрашивать вершины или выполнять повороты. Очень круто показан весь процесс.
Теперь вас еще труднее поставить в тупик на собеседовании :)
https://www.youtube.com/watch?v=g9SaX0yeneU