Однако, вероятность такого события даже при десятке тысяч узлов является маленькой.
Большим достоинством рандомизированного дерева, является тот факт, что мы очень легко можем сделать множественное удаление. Иногда бывает так, что для быстроты работы из дерева надо удалить целый список чисел. И лучше всего передать этот список процедуре удаления, чтобы она сделала всего один проход по дереву, удалив все вершины сразу. Обычно в балансируемом дереве этого сделать либо нельзя, либо нужно сильно усложнять процедуру удаления. Приходится удалять числа по одному, медленно и не красиво.
В рандомизированном дереве это сделать просто. А даже если бы это было не так, не обязательно строго следить за структурой веток. Поэтому мы можем не только сделать удаление за один вызов, мы можем просто выдрать из дерево любой количество произвольных вершин. Дерево само приведёт себя к рабочему состоянию.
Кроме того для рандомизированных деревьев, есть все операции, которые можно делать со множествами. Есть замечательные и простые алгоритмы: слияния, объединения, вычитания, пересечения и симметричной разности. Правда до состояния рабочего кода их надо немного доработать (на это пока не хватло времени).
Целью данной курсовой работы является реализация построения рандомизированного дерева на языке Object Pascal.
Задачи:
1. Постановка задачи
2. Описание алгоритма решения задачи
3. Реализация алгоритма на языке Object Pascal
4. Оценка сложности алгоритма
…
