Основные операции с двоичным деревом поиска высоты h (вставка, удаление, поиск, следующий, предыдущий) могут быть выполнены за O(h) действий. Деревья эффективны, если их высота мала. Но малая высота не гарантируется, и в худшем случае деревья не более эффективны, чем списки. Проблему баланса будем решать ниже описанным способом.
Свойства
Красно-черные деревья [2], так же как и AVL-деревья [1, 3], принадлежат к классу «сбалансированных» с высотой порядка O(logn), но в отличие от последних, имеют максимальную высоту 2log(n+1)[1]. Это обеспечивается следующими свойствами:
все вершины, помимо «ключа», имеют «цвет» Î {красный, черный}[2]; дети – nil всегда черные[3]: если вершина красная, то ее дети черные; все пути от вершины до любого nil содержат равное количество черных вершин – их черные высоты равны.
Вершина содержит три указателя типа t_rb (родитель p, правый r и левый l дети) – каркас дерева, ключ el – предмет упорядочивания, тип которого зависит от t_el, и цвет c – «балансировка» (см. таблицу 1
в приложении к статье).
Loading ...