Описание тега red-black-tree

Из Википедии, Красно-черное дерево:

Красно-черное дерево - это особый тип двоичного дерева, используемый в информатике для организации частей сопоставимых данных, таких как фрагменты текста или числа.

Листовые узлы красно-черных деревьев не содержат данных. Эти листья не обязательно должны быть явными в памяти компьютера - нулевой дочерний указатель может кодировать тот факт, что этот дочерний элемент является листом, - но он упрощает некоторые алгоритмы для работы с красно-черными деревьями, если листья действительно являются явными узлами. Для экономии памяти иногда один контрольный узел выполняет роль всех листовых узлов; тогда все ссылки от внутренних узлов на конечные узлы указывают на контрольный узел.

Красно-черные деревья, как и все бинарные деревья поиска, позволяют эффективно обходить их элементы в порядке, лево-корень-право. Время поиска является результатом обхода от корня к листу, и поэтому сбалансированное дерево, имеющее наименьшую возможную высоту дерева, дает время поиска O(log n).