Двоичные деревья поиска
Категория реферата: Рефераты по информатике, программированию
Теги реферата: отчет о прохождении практики, шпоры на экзамен
Добавил(а) на сайт: Dvoreckov.
Предыдущая страница реферата | 9 10 11 12 13 14 15 16 17 18 19 | Следующая страница реферата
Осталось рассмотреть случай 3: красная вершина node является левым потомком красной вершины node.nodeParent, которая, в свою очередь, является левым потомком node.nodeParent.nodeParent, правым потомком которой является nodeTemp. В этом случае достаточно произвести правое вращение и перекрасить две вершины. Цикл окончится, так как вершина node.nodeParent будет после этого чёрной.
Удаление вершины из КЧД
Удаление вершины немного сложнее добавления. Мы будем считать, что (NIL).color == BLACK, и будем считать операцию взятия цвета у указателя, равного NIL, допустимой операцией. Также мы будем считать допустимым присваивание (NIL).nodeParent, и будем считать данное присваивание имеющим результат. То есть при взятии значения (NIL).nodeParent мы получим ранее записанное значение. Функция RBTDelete подобна TreeDelete, но, удалив вершину, она вызывает процедуру RTBDeleteFixUp для восстановления свойств КЧД.
|
RBTDelete(Tree,node) Begin If (node.left == NIL) or (node.right == NIL) Then nodeParent = node; Else 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; Рекомендуем скачать другие рефераты по теме: шпаргалки по математике, шпаргалки по гражданскому. Предыдущая страница реферата | 9 10 11 12 13 14 15 16 17 18 19 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |