Я реализую пакет LLRB, который должен работать в любом из двух режимов: Bottom-Up 2-3 или Top-Down 2-3-4 описанный Sedgewick (код - улучшенный код, хотя он имеет дело только с 2-3 деревья здесь, благодаря RS для указателя).
Sedgewick дает очень четкое описание операций дерева для режима 2-3, хотя он много времени проводит о режиме 2-3-4. Он также показывает, как простое изменение порядка переворачивания цвета во время вставки может изменить поведение дерева (либо разбить по пути вниз на 2-3-4, либо разбить по пути вверх на 2-3):
private Node insert(Node h, Key key, Value value)
{
if (h == null)
return new Node(key, value);
// Include this for 2-3-4 trees
if (isRed(h.left) && isRed(h.right)) colorFlip(h);
int cmp = key.compareTo(h.key);
if (cmp == 0) h.val = value;
else if (cmp < 0) h.left = insert(h.left, key, value);
else h.right = insert(h.right, key, value);
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
// Include this for 2-3 trees
if (isRed(h.left) && isRed(h.right)) colorFlip(h);
return h;
}
Однако он замалчивает удаление в 2-3-4 LLRB со следующим:
Код на следующей странице - это полная реализация delete() для LLRB 2-3 деревьев. Он основан на обратном подходе, используемом для вставки сверху вниз 2-3-4 деревьев: мы выполняем повороты и цветные переходы по пути вниз по пути поиска, чтобы гарантировать, что поиск не заканчивается на 2- node, так что мы можем просто удалить node внизу. Мы используем метод fixUp() для совместного использования кода для переворота и поворота цвета после рекурсивных вызовов в коде insert(). С помощью fixUp() мы можем оставить правые красные ссылки и несбалансированные 4-узлы вдоль пути поиска, чтобы эти условия были исправлены по пути вверх по дереву. (Подход также эффективен с 2-3-4 деревьями, но требует дополнительного вращения, когда правый node от пути поиска - это 4- node.)
Его функция delete():
private Node delete(Node h, Key key)
{
if (key.compareTo(h.key) < 0)
{
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = delete(h.left, key);
}
else
{
if (isRed(h.left))
h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null))
return null;
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);
if (key.compareTo(h.key) == 0)
{
h.val = get(h.right, min(h.right).key);
h.key = min(h.right).key;
h.right = deleteMin(h.right);
}
else h.right = delete(h.right, key);
}
return fixUp(h);
}
Моя реализация корректно поддерживает инварианты LLRB 2-3 для всех операций дерева на 2-3 деревьях, но не подходит для подкласса правосторонних делеций на 2-3-4 деревьях (эти неудачные удаления приводят к правым красным вершинам, но снежный ком для дисбаланса деревьев и, наконец, разыменования нулевых указателей). Из обзора примера кода, который обсуждает деревья LLRB и включает опции для построения деревьев в любом из режимов, кажется, что ни один из них не правильно реализует удаление из 2-3-4 LLRB (т.е. Ни один из них не имеет дополнительного вращения, например, Sedgewick java выше и здесь).
У меня возникли проблемы с выяснением того, что он подразумевает под "дополнительным вращением, когда правый node с пути поиска является 4- node"; по-видимому, это вращение влево, но где и когда?
Если я поворачиваю левую часть, проходящую мимо эквивалента 4- node (т.е. RR node) или правого наклоняющегося 3- node эквивалента (BR node) либо до вызова fixUp(), либо в конце функции fixUp, я все равно получаю такое же инвариантное противоречие.
Вот состояния дерева наименьших неудачных примеров, которые я нашел (сгенерированные последовательной вставкой элементов от 0 до соответствующего максимального значения).
Первая пара деревьев показывает переход от состояния, совместимого с инвариантом, до удаления элемента 15 до явно разбитого состояния после.
Вторая по существу такая же, как и выше, но с удалением 16 из 0..16 (удаление 15 результатов в той же топологии). Заметим, что инвариантное противоречие позволяет пересечь корень node.
Ключом будет понимание того, как отменить нарушения, сгенерированные во время ходьбы по дереву, до целевого node. Следующие два дерева показывают, как первое дерево выглядит сверху после ходьбы вниз и слева и справа (без удаления и перед тем, как идти назад с помощью fixUp()).
После попытки удалить '-1' без fixUp:
После попытки удалить '16' без fixUp:
Попытка повернуть влево на прогулку назад, когда node имеет только красный правый дочерний элемент, кажется, является частью решения, но он не работает правильно с двумя красными правыми детьми подряд, перед этим с помощью flipColor когда оба ребенка красны, похоже, улучшают ситуацию дальше, но все же оставляют некоторые инварианты нарушенными.
Если я дополнительно проверю, является ли правильный дочерний элемент правильного ребенка красным, когда его брат является черным и вращается влево, если это правда, я только терпит неудачу один раз, но в этот момент я чувствую, что мне нужна новая теория, а не новый эпицикл.
Любые идеи?
Для справки моя реализация доступна здесь (Нет, это не Java).
Последующий:
Часть причин, по которым меня это интересовало, заключалась в том, чтобы подтвердить многие утверждения, что 2-3 дерева LLRB более эффективны, чем 2-3-4 дерева LLRB. Мой бенчмаркинг подтвердил это для вставки и удаления (2-3 примерно на 9% быстрее), но я считаю, что поиск очень немного быстрее для 2-3-4 деревьев.
Следующие моменты являются репрезентативными и согласованными во всех прогонах:
BU23:
BenchmarkInsert 1000000 1546 ns/op
BenchmarkDelete 1000000 1974 ns/op
BenchmarkGet 5000000 770 ns/op
TD234:
BenchmarkInsert 1000000 1689 ns/op
BenchmarkDelete 1000000 2133 ns/op
BenchmarkGet 5000000 753 ns/op
Первый столбец - имя скамьи, второе - количество операций, третье - результат. Тест на i5M 2.27.
Я просмотрел длины ветвей для 2-3 деревьев и 2-3-4 деревьев, и мало что можно объяснить разницей поиска (среднее расстояние от корня до node и SD 1000 деревьев каждый с 10000 случайных вставок):
Means:
TD234 leafs BU23 leafs
12.88940 12.84681
TD234 all BU23 all
11.79274 11.79163
StdDev:
TD234 leafs BU23 leafs
1.222458 1.257344
TD234 all BU23 all
1.874335 1.885204
