Рефераты | Рефераты по информатике, программированию | Двоичные деревья поиска
Двоичные деревья поиска
Категория реферата: Рефераты по информатике, программированию
Теги реферата: отчет о прохождении практики, шпоры на экзамен
Добавил(а) на сайт: Dvoreckov.
Функция RBTInsert не так сложна, как кажется на первый
взгляд. Рассмотрим её подробнее. После строк 3-4 выполняются все свойства КЧД, кроме, возможно, одного: у новой красной вершины может быть красный родитель.
Такая ситуация (красная вершина имеет красного родителя) может сохраниться
после любого числа итераций цикла. Внутри цикла рассматриваются 6 различных
случаев, но три из них (строки 8-28) симметричны трём другим (строки 30-50), различие лишь в том, является ли родитель вершины node правым или левым
потомком своего родителя (случаи разделяются в строке 7). Поэтому мы рассмотрим
подробно только первые три случая (строки 8-28). Предположим, что во всех
рассматриваемых КЧД корень чёрный, и будем поддерживать это свойство (строка
52). Поэтому в строке 5 node.nodeParent (красного цвета) не может быть корнем, и node.nodeParent.nodeParent != NIL. Операции внутри цикла начинаются с
нахождения nodeTemp, “дяди” node, то есть вершины, имеющей того же родителя, что и node.nodeParent. Если nodeTemp – красная вершина, то имеет место случай
1, если черная, то 2 или 3. Во всех случаях вершина node.nodeParent.nodeParent
– чёрная, так как пара node, node.nodeParent была единственным нарушением
свойств КЧД.
Случай 1 (строки 12-15 и 34-37) показан на рисунке 6.
Является ли вершина node правым или левым потомком своего родителя, значения не
имеет.
Рисунок 6.
Обе вершины (node и nodeTemp) – красные, а вершина
node.nodeParent.nodeParent – чёрная. Перекрасим node.nodeParent и nodeTemp в
чёрный цвет, а node.nodeParent.nodeParent – в красный. При этом число чёрных
вершин на любом пути от корня к листьям остаётся прежним. Нарушение свойств КЧД
возможно лишь в одном месте: вершина node.nodeParent.nodeParent может иметь
красного родителя, поэтому надо продолжить выполнение цикла, присвоив node
значение node.nodeParent.nodeParent.
В случаях 2 и 3 вершина nodeTemp – чёрная. Различаются
случаи, когда вершина node является правым или левым потомком своего родителя.
Если правым, то это случай 2 (строки 20-23 и 41-45). В этом случае производится
левое вращение, которое сводит случай 2 к случаю 3, когда node является левым
потомком своего родителя. Так как node и node.nodeParent – красные, после
вращения количество чёрных вершин на путях от корня к листьям остается прежним.
Рисунок 7.
Рекомендуем скачать другие рефераты по теме: шпаргалки по математике, шпаргалки по гражданскому.