Главная /
Алгоритмы и структуры данных поиска /
Отметьте верные утверждения для операции Split(T, x) в декартовом дереве.
Отметьте верные утверждения для операции Split(T, x)
в декартовом дереве.
вопрос
Правильный ответ:
в результате может получиться два дерева
T1, T2
, где x
не входит ни в одно из них
в результате операции получается три дерева:
T1 (< x)
, вершина с ключем x
,T2(> x)
если
x
= корень T
, α
- левое поддерево, β
- правое поддерево, то Split(T, x) = α, x, β
если ключ корня дерева
T < x
, то нужно вызвать рекурсивно Split(β, x) = γ, v, δ
. Получатся деревья T1
(α
- левое поддерево, γ
- правое, v
- корень), T2 = δ
сложность операции
O(N * log N)
Сложность вопроса
75
Сложность курса: Алгоритмы и структуры данных поиска
76
Оценить вопрос
Комментарии:
Аноним
Экзамен сдан и ладушки. Спасибо vtone
23 сен 2020
Аноним
Если бы не данные подсказки - я бы не осилил c этими тестами интуит.
02 апр 2017
Аноним
Экзамен прошёл и ладушки. Спасибо за халяуву
03 ноя 2015
Другие ответы на вопросы из темы программирование интуит.
- # Что нужно сделать, чтобы найти LCA любых двух вершин, имея Эйлеров обход дерева?
- # Что нужно посчитать для дерева помимо Эйлерова обхода вершин для нахождения lca при сведении задачи LCA к ±1-RMQ?
- # Если область поиска меняется с "колодца" на прямоугольную добавлением двух ограничивающих точек, то какая структура данных может использоваться для такой задачи?
- # Сколько дополнительной памяти требуется для работы алгоритма quick-sort?
- # Если структуру бинарное дерево размера 5(1012) слить со структурой размера 7(1112) получится структура размера: