Как я могу разбить дерево AVL на данном узле в момент времени O (log (n))?

Question

Я ломал себе голову, пытаясь разными способами, но лучшее, что у меня получилось, это O (log ^ 2 (n)). точный вопрос: создайте функцию Split(AVLtree T, int k), которая возвращает 2 дерева AVL (например, кортеж) так, чтобы все значения в T1 были меньше или равны k, а остальные были в T2. k не обязательно находится в дереве. время должно быть O (log (n)). Предположим, что эффективная реализация дерева AVL, и мне удалось создать функцию слияния за время O (log (| h1-h2 |)).

Любая помощь будет очень полезна.

Answer 1

Вы почти у цели, учитывая, что у вас есть функция слияния!

Выполните обычный поиск преемника в дереве для k. Это позволит проследить путь через дерево от root до этого узла-преемника. Представьте себе, что вы отрезаете каждое ребро на пути таким образом, что даст вам набор «вымпелов», отдельных узлов с допустимыми деревьями AVL, свисающими по сторонам. Затем покажите, что если вы снова объедините их вместе в правильном порядке, затраты на слияние образуют телескопическую сумму, которая в сумме составляет O (log n).