Реферат: Двоичные деревья поиска
nodeParent = TreeNext(node);
If (nodeParent.left != NIL) Then
nodeTemp = nodeParent.left;
Else
nodeTemp = nodeParent.right;
nodeTemp.nodeParent = nodeParent.nodeParent;
If (nodeTemp.nodeParent == NIL) Then
Tree.root = nodeTemp;
Else
Begin
If (nodeParent.nodeParent.left == nodeParent) Then
nodeParent.nodeParent.left = nodeTemp;
Else
nodeParent.nodeParent.right = nodeTemp;
End
If (nodeParent != node) Then
Begin
node.key = nodeParent.key;
node.color = nodeParent.color;
{ копирование дополнительных данных }
End
If (nodeParent.color == BLACK) Then
RBTDeleteFixUp(Tree,nodeTemp);
Return nodeParent;
End
Рассмотрим, как процедура RBTDeleteFixUp восстанавливает свойства КЧД. Очевидно, что если удалили красную вершину, то, поскольку оба ее потомка чёрные, красная вершина не станет родителем красного потомка. Если же удалили чёрную вершину, то как минимум на одном из путей от корня к листьям количество чёрных вершин уменьшилось. К тому же красная вершина могла стать потомком красного родителя.
|
1 RTBDeleteFixUp(Tree,node) 2 Begin 3 While (node != Tree.root) and (node.color == BLACK) Do К-во Просмотров: 890
Бесплатно скачать Реферат: Двоичные деревья поиска
|