Красно-черное дерево с левым наклоном ( LLRB ) — это тип самобалансирующегося бинарного дерева поиска , введенный Робертом Седжвиком . Это вариант красно-черного дерева , гарантирующий ту же асимптотическую сложность операций, но разработанный для более простой реализации. [1]
Красно-черное дерево с левым наклоном удовлетворяет всем свойствам красно-черного дерева:
Кроме того, свойство левого наклона гласит, что:
Свойство левого наклона уменьшает количество случаев, которые необходимо учитывать при реализации операций дерева поиска.
Деревья LLRB являются изоморфными 2–3–4 деревьями . В отличие от обычных красно-черных деревьев, 3-узлы всегда наклонены влево, что делает это отношение соответствием 1 к 1. Это означает, что для каждого дерева LLRB существует уникальное соответствующее 2–3–4 дерево, и наоборот.
Если мы наложим дополнительное требование, что узел не может иметь двух красных потомков, деревья LLRB станут изоморфными деревьям 2–3 , поскольку 4-узлы теперь запрещены. Седжвик замечает, что реализации деревьев LLRB 2–3 и деревьев LLRB 2–3–4 отличаются только положением одной строки кода. [1]
Все предложенные алгоритмы красно-черного дерева характеризуются временем поиска в худшем случае, ограниченным небольшим постоянным кратным log N в дереве из N ключей, а поведение, наблюдаемое на практике, обычно в то же самое время быстрее, чем граница в худшем случае, близко к оптимальному log N рассмотренных узлов, который наблюдался бы в идеально сбалансированном дереве.
В частности, в левостороннем красно-черном дереве 2–3, построенном из N случайных ключей, эксперименты Седжвика показывают, что: