Реферат: Двоичные деревья поиска
Каждый лист (NIL) имеет чёрный цвет.
Если вершина красная, то оба её потомка – чёрные.
Все пути от корня к листьям содержат одинаковое число чёрных вершин.
Пример КЧД с учётом наших положений приведен на рисунке 4. Учтите, что вершина 9 могла быть и красной, но в дальнейшем мы будем рассматривать только те деревья, у которых корень чёрный. Мы это сделаем для того, чтобы потомки корня могли иметь любой цвет.
Рисунок 4.
Вращения
Операции вставки и удаления вершин в КЧД могут нарушать свойства КЧД. Чтобы восстановить эти свойства, надо будет перекрашивать некоторые вершины и менять структуру дерева. Для изменения структуры используются операции, называемые вращением. Возвращая КЧД его свойства, вращения так же восстанавливают сбалансированность дерева. Вращения бывают левые и правые, их суть показана на рисунке 5.
Рисунок 5.
Как видно, вращения, перемещая вершины, не нарушают свойства упорядоченности.
В процедуре RBTLeftRotate предполагается, что node.right != NIL. В процедуре RBTRightRotate предполагается, что node.left != NIL.
|
RBTLeftRotate(Tree,node) Begin nodeTemp = node.right; node.right = nodeTemp.left; If (nodeTemp.left != NIL) Then nodeTemp.left.nodeParent = node; nodeTemp.nodeParent = node.nodeParent; If (node.nodeParent == NIL) Then Tree.root = nodeTemp; Else Begin If (node == node.nodeParent.left) Then node.nodeParent.left = nodeTemp; Else node.nodeParent.right = nodeTemp; End nodeTemp.left = node; К-во Просмотров: 884
Бесплатно скачать Реферат: Двоичные деревья поиска
|