Ответ
Красно-черное дерево (Red-Black Tree) — самобалансирующееся бинарное дерево поиска.
Основные свойства, обеспечивающие балансировку (O(log n) для put/get/remove):
- Каждый узел имеет цвет: красный или черный.
- Корень всегда черный.
- Все листья (NIL) считаются черными.
- Красный узел не может иметь красного потомка (нет двух красных узлов подряд).
- Все простые пути от узла до его листьев содержат одинаковое количество черных узлов (одинаковая черная высота).
Пример использования:
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Three");
map.put(1, "One");
map.put(2, "Two");
// Элементы автоматически сортируются по ключу (естественный порядок)
System.out.println(map); // {1=One, 2=Two, 3=Three}
// Навигационные методы
Integer lowerKey = map.lowerKey(2); // 1
Integer higherKey = map.higherKey(2); // 3Ключи должны быть сравнимы (реализовывать Comparable) или в конструктор необходимо передать Comparator.
Ответ 18+ 🔞
А, слушай, вот эта штука — красно-чёрное дерево. Выглядит как какая-то ёбаная магия, но на самом деле просто хитрая жопа, чтобы дерево поиска само себя не разваливало в труху.
Представь обычное бинарное дерево, куда ты запихиваешь ключи. Если их кидать как попало, оно вытянется в одну длиннющую ветку, как хуй с горы, и поиск станет медленным, как у меня в субботу утром. Вот чтобы этого не было, придумали правила, прям как в строгой семье, ёпта.
Вот их пять заповедей, нарушать которые низя:
- Узел может быть либо красным, либо черным. Как светофор, блядь.
- Корень — всегда чёрный папа. С него всё начинается, авторитет, блядь.
- Все листья (пустые места, NIL) — тоже считаются чёрными. Просто договорились так.
- Главное правило, ёбта! Красный узел не может породить красного ребёнка. Два красных подряд — это пиздец, нарушение баланса. Красные должны быть разделены чёрными, как ссорящиеся родственники на свадьбе.
- От любого узла до каждого его листа должно быть одинаковое число чёрных узлов на пути. Это называется «чёрная высота» и она везде одинаковая, вот в чём весь фокус!
Когда ты добавляешь или удаляешь узел, эти правила могут ебнуться. Тогда дерево начинает крутить себя само: повороты и перекрашивания. Оно тыкает узлы, меняет цвета, чтобы снова всё стало по правилам. Выглядит сложно, но оно просто не хочет, чтобы его поиск превратился в долгую пиздёжку.
Где это, блядь, применяется? Да прямо в Java, в TreeMap! Смотри, как просто:
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Три");
map.put(1, "Один");
map.put(2, "Два");
// Внутри эта бандура автоматом всё в красно-чёрное дерево упаковывает и сортирует по ключам!
System.out.println(map); // {1=Один, 2=Два, 3=Три}
// А ещё там навигация готовая, чтоб не ебаться
Integer ключПоменьше = map.lowerKey(2); // 1
Integer ключПобольше = map.higherKey(2); // 3Только смотри, чувак: ключи должны уметь сравниваться. Либо они сами по себе сравнимы (как Integer), либо ты суёшь в конструктор свой Comparator, а то дерево нихуя не поймёт, что больше, а что меньше. В общем, штука мощная, вся соль — в этих пяти правилах, которые не дают дереву превратиться в кривую палку.