CD
int l = getSize(L), r = getSize(R), rang = rand() % (l + r);
if (rang > r)
вот так корень определяется в мердже
вот так корень определяется в мердже
Size: a a a
2021 April 21
вот так корень определяется в мердже
NK
а почему она должна ?
CD
ну мне непонятна логика рассуждений - корень равновероятен, хорошо, но дерево не равновероятно ни в каком смысле, потому что split порождает не равновероятные деревья
NK
ну тоесть ведь у тебя распределение на деревьях тогда такое же как если бы строил случайное дерево на нужных вершинах
CD
в том-то и дело, что после split вроде бы это неверно
CD
а значит неверно и для самих аргументов merge
CD
смотри, построим дерево из 100к элементов, у него высота 20, высплитаем 20 элементов подряд, неужели они образовали равновероятное дерево?
NK
окей, я понимаю в чем проблема
CD
возможно, что я туплю и ответ просто "да"
NK
как я понимаю все доказательство строится не на том что каждое дерево равномерное
NK
если смотреть на одно конкретное дерево то у него распределение равномерное
CD
ну там равновероятное дерево в смысле выбора случайного корня
NK
ну да
NK
короче если у тебя есть алгоритм который приорететы ставит в начале
NK
то понятно что каждое дерево которое появляется в работе алгоритма равномерно распределено
NK
(тут надо предполагать что запросы не зависят от структуры дерева)
NK
а такой процесс построения дерева более менее эквивалентен растановке приоритетов
DP
в тему про вырождение структур данных - какие вы бы предложили структуры которые устойчивы к этому даже после многих обновлений?
NK
ну тоесть ответ не выродится в моем понимании надо только аккуратно делать coupling
CD
хм... то есть split на самом деле породит правильно распределенное дерево?