Не знаю, как вы, уважаемый читатель, а я всегда поражался контрасту между изяществом базовой идеи, заложенной в концепцию двоичных деревьев поиска, и сложностью реализации сбалансированных двоичных деревьев поиска (красно-черные деревья, АВЛ-деревья, декартовы деревья). Недавно, перелистывая в очередной раз Седжвика [1], нашел описание рандомизированных деревьев поиска (нашлась и ориганльная работа [2]) — настолько простое, что занимает оно всего треть страницы (вставка узлов, еще страница — удаление узлов). Кроме того, при ближайшем рассмотрении обнаружился дополнительный бонус в виде очень красивой реализации операции удаления узлов из дерева поиска. Далее вы найдете описание (с цветными картинками) рандомизированных деревьев поиска, реализация на С++, а также результаты небольшого авторского исследования сбалансированности описываемых деревьев.
Читать полностью »
Метка «рандомизация»
Рандомизированные деревья поиска
2012-06-07 в 19:43, admin, рубрики: Алгоритмы, рандомизация, метки: рандомизацияРандомизированые Алгоритмы
2012-04-18 в 9:53, admin, рубрики: Алгоритмы, обзор, рандомизация, теория вероятностей, метки: обзор, рандомизация, теория вероятностей Надеюсь что тема будет интересна людям которые знакомы с обычными алгоритмами и хотят узнать об упомянутых выше в общих чертах, что бы иметь представление о чем речь. Постараюсь избегать вычеслений и излагать на интуитивном уровне. И хотя интуиция в теории вероятностей часто подводит, давайте все же попробуем.
Читать полностью »