Изменения

Перейти к: навигация, поиск

Splay-дерево

1 байт добавлено, 18:31, 17 мая 2011
→‎Merge(T_1, T_2)
==Merge(<tex>T_1</tex>, <tex>T_2</tex>)==
У нас есть два дерева <tex>T_1</tex> и <tex>T_2</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второго.
запускаем Запускаем Move to Root от самого большого элемента (пусть это элемент в дереве <tex>iT_1</tex>) в дереве (пусть это элемент <tex>T_1i</tex>). после После этого корень <tex>T_1</tex> содержит элемент <tex>i</tex>, причём у него нет правого ребёнка. делаем Делаем <tex>T_2</tex> правым поддеревом <tex>i</tex> и возвращаем полученное дерево. 
==Split(<tex>i</tex>, <tex>T</tex>)==
запускаем Splay от элемента <tex>i</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>i</tex>.
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/8844»

Навигация