#algorithm #tree #avl-tree #b-tree
#алгоритм #дерево #avl-дерево #b-дерево
Вопрос:
В самобалансирующихся деревьях, таких как деревья AVL, вставка узла принимает значение O (log n), где n — текущее количество узлов в дереве.
Предположим, я хочу построить новое дерево AVL с нуля со следующими значениями: 1,2,3,4 … n Есть ли способ, которым я могу сделать это в O (n) вместо традиционного способа, который займет O (n log (n))?
Ответ №1:
Да, это возможно. Идея заключается в том, что у вас есть функция, которая принимает диапазон [x, y] и разрезает его на два диапазона [x, n), (n, y], создает узел со значением n, а затем добавляет двух своих дочерних элементов, вызывая себя с этими двумя диапазонами как и его параметры.
Комментарии:
1. Оказывается, это невозможно по ссылке, только для кучи
2. Ссылка относится к ситуациям, когда вы начинаете с несортированных данных. Если вы знаете, что диапазон равен [1, n], то создание каждого узла — это операция с постоянным временем, а связывание каждого узла с его родительским элементом — операция с постоянным временем, поэтому все это можно выполнить за линейное время.