Структуры данных и модели вычислений
Реализация операций с использованием рангов вершин
Для такой реализации разделенных множеств необходимо хранить с каждым узлом дополнительно еще одну величину — высоту поддерева, корнем которого является узел . Будем называть ее высотой, или рангом, узла . Остальные операции нужно настроить на корректную работу с этим полем. Будем хранить высоту каждого узла в ячейке массива .
Операция СОЗДАТЬ () назначает в качестве родителя узлатот же самый, а высотой узласчитает 0. Таким образом, время выполнения данной операции есть. В результате выполнения операции СОЗДАТЬ () образуется новое дерево, изображенное на рис. 3.6. Число, расположенное рядом с узлом, обозначает его высоту. Описанные действия реализуются с помощью операторов
Рис. 3.6.
Операция ОБЪЕДИНИТЬ
() назначает корень большего по высоте дерева родителем корня другого дерева. Если деревья имеют одинаковую высоту, то узел назначается родителем узла , после чего значение высоты узла увеличивается на единицу. Заметим, что и должны быть до выполнения операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет имя того из объединяемых подмножеств, у которого корень имел большую высоту, а имя другого из объединяемых подмножеств перестанет быть именем какого-либо из подмножеств. Очевидно, время выполнения этой операции есть константа. Выполнить описанные действия можно с помощью следующей процедуры:
На рис. 3.7 и рис. 3.8 показано применение операции ОБЪЕДИНИТЬк коллекции, изображенной на рис. 3.3, с учетом высот объединяемых поддеревьев. Рядом с кружочками, изображающими узлы, показаны их высоты. Так как, то родителем узла 6 становится узел 3.
Операция НАЙТИ () осуществляется, как и в предыдущей реализации, продвижением по указателям на родителей от узла до корня дерева. В качестве берется найденный корень.
Рис. 3.7.
Рис. 3.8.
Очевидно, что время выполнения данной операции, как и ранее, пропорционально длине пути из узлав корень соответствующего дерева. Однако длина такого пути в данном случае может быть оценена иначе. Для оценки длины этого пути докажем следующие леммы:
