Секретные материалы

Claw.ru | Рефераты по информатике, программированию | Двоичные деревья поиска

Двоичные деревья поиска

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: отчет о прохождении практики, шпоры на экзамен
| Добавил(а) на сайт: 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;

Рекомендуем скачать другие рефераты по теме: шпаргалки по математике, шпаргалки по гражданскому.

Claw.ru | Рефераты по информатике, программированию | Двоичные деревья поиска

Двоичные деревья поиска

Категории:

Поделитесь этой записью или добавьте в закладки

Рефераты от А до Я