Каждая словарная операция в расширяемом дереве использует операцию расширения для перемещения узла в корень дерева. Амортизированная эффективность этой операции расширения обычно анализируется с помощью потенциального метода и описывается во многих источниках в Интернете (включая википедию). Амортизированное время этой операции расширения отображается как O (m lg n).
Однако я нигде не нахожу фактического анализа полных словарных операций, таких как вставка, удаление, ... Каждая из этих операций использует, помимо операции расширения, также поиск вниз по дереву, чтобы найти правильную позицию узла для вставки. или удалить. Только после того, как вы найдете этот узел, вы можете начать операцию развертывания.
Люди склонны делать такие заявления, как:
- сложность операции с развернутым деревом такая же, как и связанного экрана
- [Для нашего анализа отметим, что время для выполнения поиска, вставки или удаления пропорционально времени для соответствующего отображения], стр. 456 книги Гудрича под названием Структуры данных и алгоритмы в C ++
У меня два вопроса:
- Как можно сделать такой вывод, что время выполнения поиска пропорционально времени развертки? Этот вид подразумевает, что время нисходящего перехода к узлу также пропорционально привязке расширения?
- Какова амортизированная временная эффективность обхода вниз? Является ли это константой просто потому, что вы не меняете структуру дерева, просто выполняя обход вниз (чтобы ваш потенциал остался прежним)? И разве эта константа не больше = N, поскольку это наихудший случай?
Как можно сделать такой вывод?
