В общих интервью, когда мы говорим о HashMap, мы будем говорить о красно-черных деревьях, но если вы спросите дальше, знаете ли вы, каковы характеристики красно-черных деревьев? . .
Если у вас нет понятия бинарного дерева, сначала посмотрите:Первое знакомство с бинарным деревом
советы: листовые узлы, узлы без дочерних узлов. nil эквивалентен null в java.
По признаку 4 делается вывод, что не может быть последовательных красных узлов, а признак 5 также говорит о том, что левый и правый пути от любого узла к каждому листовому узлу содержат одинаковое количество черных узлов. Самый длинный путь, который можно вывести, — это сочетание черного и красного креста, а самый короткий путь — полностью черный. Следовательно, самый длинный путь не будет превышать вдвое самый короткий путь, поэтому красно-черное дерево приблизительно сбалансировано, а не строго сбалансировано. Дети, которым нужно понимать сбалансированные бинарные деревья, комиксы: первое знакомство с бинарными деревьями.
Найти красно-черное дерево, добавить, удалить, временное сложность O (log n), конкретно как это сделано, наша следующая есть.
Длина статьи короткая, я надеюсь, что каждый сможет научиться в простой и непринужденной обстановке. Редактор не сильно обновился, но я надеюсь, что каждая статья может быть полезной для всех, и продолжать усердно работать.
В этой статье используетсяmdniceнабор текста