Перекрытый метод Delete (см. листинг 8.21) реализует обычную операцию удаления из дерева бинарного поиска и выполняет скос родительского узла удаленного узла к корневому узлу.
Листинг 8.21. Метод TtdSplayTree.Delete
procedure TtdSplayTree.Delete(aItem : pointer);
var
Node : PtdBinTreeNode;
Dad : PtdBinTreeNode;
begin
Node := bstFindNodeToDelete(aItem);
Dad := Node^.btParent;
FBinTree.Delete(Node);
dec(FCount);
if (Count <> 0) then
stSplay(Dad);
end;
Эти три перекрытых метода достаточно просты для понимания, поскольку реальная обработка передается методу stSplay. Код реализации этого метода приведен в листинге 8.22.
Листинг 8.22. Метод TtdSplayTree.stSplay
procedure TtdSplayTree.stSplay(aNode : PtdBinTreeNode);
var
Dad : PtdBinTreeNode;
Grandad : PtdBinTreeNode;
RootNode : PtdBinTreeNode;
begin
{поскольку мы должны выполнять скос до тех пор, пока не будет достигнут корневой узел, сделать корневой узел локальной переменной — это несколько ускорит процесс}
RootNode := FBinTree.Root;
{если мы находимся в позиции корневого узла, никакой скос больше выполнять не требуется}
if (aNode = RootNode) then
Exit;
{получить родительский и прародительский узлы}
Dad := aNode^.btParent;
if (Dad = RootNode) then
Grandad := nil else
Grandad := Dad^.btParent;
{выполнять операции спаренного двустороннего и одностороннего поворота до тех пор, пока это возможно}
while (Grandad <> nil) do
begin
{определить вид двойного повышения ранга, которое необходимо выполнить}
if ((Grandad^.btChild[ctLeft] = Dad) and (Dad^.btChild[ctLeft] = aNode)) or ( (Grandad^.btChild[ctRight] = Dad) and (Dad^.btChild[ctRight] ? aNode)) then begin
{выполнить повышение ранга посредством спаренного одностороннего поворота}
stPromote(Dad);
stPromote(aNode);
end
else begin
{выполнить повышение ранга посредством спаренного двустороннего поворота}
stPromote(stPromote(aNode));
end;
{после того, как ранг повышен, необходимо получить новый родительски и прародительский узел}
RootNode := FBinTree.Root;
if (aNode = RootNode) then begin
Dad := nil;