Я использую реализацию Red-Black tree, написанную Джулианом Бакналом в его знаменитой книге The Tomes Of Delphi. Исходный код может быть загружен здесь, и я использую код как есть в Delphi 2010 с изменениями в TdBasics.pas
, чтобы он компилировался в современной версии Delphi (в основном, комментируя большую часть этого текста - только двоеточие требует только нескольких определений).
Это известная реализация известного автора в часто рекомендуемой книге. Я чувствую, что я должен быть на твердой земле, используя его. Но я сталкиваюсь с авариями с использованием Delete()
и Promote()
. Возвращаясь к написанию модульных тестов с DUnit, эти проблемы легко воспроизводятся. Некоторый пример кода (фрагменты из моих тестов DUnit):
// Tests that require an initialised tree start with one with seven items
const
NumInitialItems : Integer = 7;
...
// Data is an int, not a pointer
function Compare(aData1, aData2: Pointer): Integer;
begin
if NativeInt(aData1) < NativeInt(aData2) then Exit(-1);
if NativeInt(aData1) > NativeInt(aData2) then Exit(1);
Exit(0);
end;
// Add seven items (0..6) to the tree. Node.Data is a pointer field, just cast.
procedure TestTRedBlackTree.SetUp;
var
Loop : Integer;
begin
FRedBlackTree := TtdRedBlackTree.Create(Compare, nil);
for Loop := 0 to NumInitialItems - 1 do begin
FRedBlackTree.Insert(Pointer(Loop));
end;
end;
...
// Delete() crashes for the first item, no matter if it is 0 or 1 or...
procedure TestTRedBlackTree.TestDelete;
var
aItem: Pointer;
Loop : Integer;
begin
for Loop := 1 to NumInitialItems - 1 do begin // In case 0 (nil) causes problems, but 1 fails too
aItem := Pointer(Loop);
Check(FRedBlackTree.Find(aItem) = aItem, 'Item not found before deleting');
FRedBlackTree.Delete(aItem);
Check(FRedBlackTree.Find(aItem) = nil, 'Item found after deleting');
Check(FRedBlackTree.Count = NumInitialItems - Loop, 'Item still in the tree');
end;
end;
Я не достаточно прочен в алгоритмах, чтобы знать, как исправить это, не внося дополнительных проблем (неуравновешенное или неправильное дерево.) Я знаю, потому что я пробовал:)
Сбой кода
Вышеуказанный тест не удается выполнить в Promote()
при удалении элемента в строке, помеченной !!!
:
function TtdRedBlackTree.rbtPromote(aNode : PtdBinTreeNode)
: PtdBinTreeNode;
var
Parent : PtdBinTreeNode;
begin
{make a note of the parent of the node we're promoting}
Parent := aNode^.btParent;
{in both cases there are 6 links to be broken and remade: the node's
link to its child and vice versa, the node link with its parent
and vice versa and the parent link with its parent and vice
versa; note that the node child could be nil}
{promote a left child = right rotation of parent}
if (Parent^.btChild[ctLeft] = aNode) then begin
Parent^.btChild[ctLeft] := aNode^.btChild[ctRight];
if (Parent^.btChild[ctLeft] <> nil) then
Parent^.btChild[ctLeft]^.btParent := Parent;
aNode^.btParent := Parent^.btParent;
if (aNode^.btParent^.btChild[ctLeft] = Parent) then //!!!
aNode^.btParent^.btChild[ctLeft] := aNode
else
aNode^.btParent^.btChild[ctRight] := aNode;
aNode^.btChild[ctRight] := Parent;
Parent^.btParent := aNode;
end
...
Parent.btParent
(становление aNode.btParent
) составляет nil
, таким образом, сбой. Изучая древовидную структуру, родитель node является корнем node, который, очевидно, имеет родительский nil
.
Некоторые нерабочие попытки его фиксации
Я попробовал просто протестировать это и только запустить этот оператор if/then/else, когда существовал бабушка и дедушка. Хотя это кажется логичным, это своего рода наивное исправление; Я не понимаю вращения достаточно хорошо, чтобы узнать, действительно ли это, или что-то еще должно произойти вместо этого - и это вызывает другую проблему, упомянутую после фрагмента. (Обратите внимание, что здесь есть дубликат этого кода ниже фрагмента, скопированного выше для левого вращения, и там тоже происходит ошибка.)
if aNode.btParent <> nil then begin //!!! Grandparent doesn't exist, because parent is root node
if (aNode^.btParent^.btChild[ctLeft] = Parent) then
aNode^.btParent^.btChild[ctLeft] := aNode
else
aNode^.btParent^.btChild[ctRight] := aNode;
aNode^.btChild[ctRight] := Parent;
end;
Parent^.btParent := aNode;
...
С помощью этого кода тест для удаления все еще не выполняется, но с чем-то более странным: после вызова метода Delete() вызов метода Find() корректно возвращает nil, указывая, что элемент удален. Однако последняя итерация цикла, удаляющая элемент 6, вызывает сбой в TtdBinarySearchTree.bstFindItem
:
Walker := FBinTree.Root;
CmpResult := FCompare(aItem, Walker^.btData);
FBinTree.Root
nil
, сбой при вызове FCompare
.
Итак - в этот момент я могу сказать, что мои модификации явно просто вызывают больше проблем, а что-то еще более фундаментальное не так с кодом, реализующим алгоритм. К сожалению, даже с книгой в качестве справочной информации я не могу понять, что не так, точнее, какая правильная реализация будет выглядеть и что здесь происходит.
Я изначально думал, что это был мой код неправильно, используя дерево, вызывая проблемы. Это все еще очень возможно! Автор, книга и, следовательно, неявный код хорошо известны в мире Delphi. Но аварии легко воспроизводятся, написав некоторые очень простые модульные тесты для класса, используя исходный код книги, загруженный с сайта автора. Кто-то еще должен был использовать этот код за последнее десятилетие, и столкнулся с той же проблемой (если только ошибка не является моей, и оба моих кода и модульные тесты неправильно используют дерево). Я ищу ответы, помогая с помощью:
- Идентификация и исправление ошибок в
Promote
и в других местах класса. Обратите внимание, что я также написал модульные тесты для базового классаTtdBinarySearchTree
, и все они проходят. (Это не значит, что это идеально - я, возможно, не обнаружил неудачные случаи, но это поможет.) - Поиск обновленной версии кода. Джулиан не опубликовал никаких ошибок для реализации красно-черного дерева.
- Если все остальное не удается найти другую известную хорошую реализацию красно-черного дерева для Delphi. Я использую дерево для решения проблемы, а не для написания дерева. Если мне нужно, я с радостью заменит базовую реализацию другим (учитывая правильные условия лицензирования и т.д.). Тем не менее, учитывая родословную книги и кода, проблемы удивляют, и их решение поможет большему количеству людей, чем мне. широко рекомендованная книга в сообществе Delphi.
Изменить: дополнительные примечания
Комментарий MBo указывает Джулианскую библиотеку EZDSL, которая содержит еще одну реализацию красно-черного дерева. Модульные тесты на этой версии проходят. В настоящее время я сравниваю два источника, чтобы попытаться увидеть, где алгоритмы отклоняются, чтобы найти ошибку.
Одна из возможностей - просто использовать красно-черное дерево EZDSL, а не красно-черное дерево Tomes of Delphi, но есть несколько проблем с библиотекой, которые заставляют меня не использовать ее: она написана для 32-битного x86 только; некоторые методы предоставляются только в сборке, а не в Pascal (хотя большинство из них имеют две версии); деревья структурированы совершенно по-другому, например, используя курсоры для узлов вместо указателей - совершенно правильный подход, но пример того, как отличается код "пример" в книге ToD, где навигация семантически отличается; код, на мой взгляд, гораздо сложнее понять и использовать: он довольно сильно оптимизирован, переменные и методы не так четко обозначены, есть множество магических функций, структура node на самом деле представляет собой запись объединения/случая, скрежеща в деталях для стеков, очередей, делений и списков, двойных списков, списков пропусков, деревьев, двоичных деревьев и кучи в одной структуре, которая почти непонятна в отладчике и т.д. Это не код, который я очень хочу использовать в производстве, где мне нужно будет его поддерживать, и нелегко учиться. Исходный код Tomes of Delphi гораздо читабельнее и гораздо удобнее обслуживать... но также и неверно. Вы видите дилемму:)
Я пытаюсь сравнить код, чтобы попытаться найти различия между юлианским кодексом практики (EZDSL) и его учебным кодом (Tomes of Delphi.) Но этот вопрос все еще открыт, и я все равно буду благодарен за ответы. Я не могу быть единственным человеком, использующим красно-черные деревья из Томеса Дельфи за двенадцать лет с момента его публикации:)
Изменить: дальнейшие примечания
Я сам это ответил (несмотря на то, что предлагал щедрость. Ой.) У меня возникли проблемы с поиском ошибок, просто просмотрев код и сравнив с описанием алгоритма ToD, поэтому вместо этого я переопределял ошибочные методы, основанные на хорошая страница, описывающая структуру, которая поставляется с лицензией C, лицензированной MIT; подробности ниже. Один из бонусов заключается в том, что я думаю, что новая реализация на самом деле намного понятнее.