Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Хадиев К.Р.
Дерево поиска с вероятностным сравнением ключей и квантовая сортировка строк
Аннотация:
В рамках данной работы рассматривается структура данных двоичное дерево поиска, в частности красно-черное дерево в качестве реализации само-балансирующегося дерева поиска. Мы рассматриваем случай когда процедура сравнения элементов в дереве 'шумная' или вероятностная. Мы представляем алгоритм, который реализует основные операции (добавление, удаление, поиск) с вероятностью ошибки O(1/n2) и временем работы t=O(log n) шагов. А также используем структуру данных для построения квантового алгоритма сортировки n строк длины k за O(n log n √k).
