Рефераты | Рефераты по информатике, программированию | Двоичные деревья поиска
Двоичные деревья поискаКатегория реферата: Рефераты по информатике, программированию Теги реферата: отчет о прохождении практики, шпоры на экзамен Добавил(а) на сайт: Dvoreckov. Предыдущая страница реферата | 10 11 12 13 14 15 16 17 18 19 20 | Следующая страница реферата 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 4 Begin 5 If (node == node.nodeParent.left) 6 Begin 7 nodeTemp = node.nodeParent.right; 8 If (nodeTemp.color == RED) Then 9 Begin 10 nodeTemp.color = BLACK; 11 nodeTemp.nodeParent.color = RED; 12 RBTLeftRotate(Tree,node.nodeParent); 13 nodeTemp = node.nodeParent.right; 14 End 15 If (nodeTemp.left.color == BLACK) and (nodeTemp.right.color == BLACK) Then 16 Begin 17 nodeTemp.color = RED; Рекомендуем скачать другие рефераты по теме: шпаргалки по математике, шпаргалки по гражданскому. Предыдущая страница реферата | 10 11 12 13 14 15 16 17 18 19 20 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |