Алгоритм Splay-сортировки: Параллельно я реализовал и более "классический" подход к балансировке BST с использованием рекурсии, или, скорее, построение BST с последующей операцией "splay" для каждого элемента. Можно ли это назвать полноценным алгоритмом Splay-сортировки — не знаю.
&НаКлиенте
Процедура КомандаСортироватьSplayДеревом(Команда)
// массив чисел на форме.
МассивЧисел = ЭтаФорма.Список3.ВыгрузитьЗначения();
// 1. Сортируем массив и получаем корень финального дерева
КореньДерева = Неопределено;
ОтсортированныйМассив = Новый Массив;
// Построение Splay-дерева
Для Каждого Элемент Из МассивЧисел Цикл
КореньДерева = ВставитьИПротянутьВКорень(КореньДерева, Элемент);
КонецЦикла;
// 2. Обход для получения отсортированного массива
ВыполнитьОбходInOrder(КореньДерева, ОтсортированныйМассив);
// 2. Визуализируем то, что получилось
ТабличныйДокументРезультат = ВизуализироватьSplayДерево(КореньДерева);
ЭтаФорма.Список3.ЗагрузитьЗначения(ОтсортированныйМассив);
КонецПроцедуры
// Рекурсивная функция: вставляет значение как в BST и протягивает его в корень
//
// Параметры:
// ТекущийУзел - Структура - корень текущего поддерева
// Значение - Число - значение для вставки
//
// Возвращаемое значение:
// Структура - новый корень поддерева (это будет вставленный элемент)
//
Функция ВставитьИПротянутьВКорень(ТекущийУзел, Значение)
// 1. Сначала вставляем узел по правилам BST в переданное поддерево
ТекущийУзел = ВставитьВBST(ТекущийУзел, Значение);
// 2. "протягиваем" узел с этим значением в корень
Возврат ПротянутьУзелВКорень(ТекущийУзел, Значение);
КонецФункции
Функция ВставитьВBST(ТекущийУзел, Значение)
Если ТекущийУзел = Неопределено Тогда
НовыйУзел = Новый Структура;
НовыйУзел.Вставить("Значение", Значение);
НовыйУзел.Вставить("Левый", Неопределено);
НовыйУзел.Вставить("Правый", Неопределено);
Возврат НовыйУзел;
КонецЕсли;
Если Значение < ТекущийУзел.Значение Тогда
ТекущийУзел.Левый = ВставитьВBST(ТекущийУзел.Левый, Значение);
Иначе
ТекущийУзел.Правый = ВставитьВBST(ТекущийУзел.Правый, Значение);
КонецЕсли;
Возврат ТекущийУзел;
КонецФункции
// Основная функция, которая выполняет серию поворотов, чтобы переместить узел с заданным значением в корень дерева.
Функция ПротянутьУзелВКорень(Корень, Значение)
// Базовый случай: пустое дерево или узел найден
Если Корень = Неопределено Или Корень.Значение = Значение Тогда
Возврат Корень;
КонецЕсли;
Если Значение < Корень.Значение Тогда // Искомый узел в левом поддереве
Если Корень.Левый = Неопределено Тогда
Возврат Корень; // Узел не найден, но можно протянуть последний посещенный узел
КонецЕсли;
// Идем глубже по Константылевому поддереву
Если Значение < Корень.Левый.Значение Тогда // Zig-Zig
Корень.Левый.Левый = ПротянутьУзелВКорень(Корень.Левый.Левый, Значение);
Корень = ПоворотZigZig(Корень, Истина);
ИначеЕсли Значение > Корень.Левый.Значение Тогда // Zig-Zag
Корень.Левый.Правый = ПротянутьУзелВКорень(Корень.Левый.Правый, Значение);
Корень.Левый = ПоворотZig(Корень.Левый, Ложь); // Важный порядок: сначала маленький поворот
Корень = ПоворотZig(Корень, Истина); // потом большой
Иначе // Если (случай дубликата) Тогда
// Протягиваем найденный узел наверх одним поворотом
Корень = ПоворотZig(Корень, Истина);
КонецЕсли;
Иначе // Искомый узел в правом поддереве
Если Корень.Правый = Неопределено Тогда
Возврат Корень;
КонецЕсли;
// Идем глубже по правому поддереву
Если Значение > Корень.Правый.Значение Тогда // Zig-Zig
Корень.Правый.Правый = ПротянутьУзелВКорень(Корень.Правый.Правый, Значение);
Корень = ПоворотZigZig(Корень, Ложь);
ИначеЕсли Значение < Корень.Правый.Значение Тогда // Zig-Zag
Корень.Правый.Левый = ПротянутьУзелВКорень(Корень.Правый.Левый, Значение);
Корень.Правый = ПоворотZig(Корень.Правый, Истина);
Корень = ПоворотZig(Корень, Ложь);
Иначе // Если (случай дубликата) Тогда
Корень = ПоворотZig(Корень, Ложь);
КонецЕсли;
КонецЕсли;
Возврат Корень;
КонецФункции
// Поворот Zig. X - потомок, P - родитель.
// Параметр XЛевый указывает, является ли X левым потомком P.
// Возвращает новый корень поддерева (узел X).
Функция ПоворотZig(P, XЛевый)
X = Неопределено;
Если XЛевый Тогда
X = P.Левый;
Если X = Неопределено Тогда
Возврат P; // Нечего поворачивать
КонецЕсли;
P.Левый = X.Правый;
X.Правый = P;
Иначе
X = P.Правый;
Если X = Неопределено Тогда
Возврат P; // Нечего поворачивать
КонецЕсли;
P.Правый = X.Левый;
X.Левый = P;
КонецЕсли;
Возврат X;
КонецФункции
// Поворот ZigZig. G - дедушка, P - родитель, X - потомок.
// Параметр XЛевый указывает, что P и X являются левыми потомками (Истина) или правыми (Ложь).
// Возвращает новый корень поддерева (узел X).
Функция ПоворотZigZig(G, XЛевый)
Если XЛевый Тогда
// G -> P -> X (все левые)
P = G.Левый;
X = P.Левый;
P.Левый = X.Правый; // B к P
G.Левый = P.Правый; // C к G
P.Правый = G; // G к P
X.Правый = P; // P к X
Иначе
// G -> P -> X (все правые)
P = G.Правый;
X = P.Правый;
P.Правый = X.Левый; // B к P
G.Правый = P.Левый; // C к G
P.Левый = G; // G к P
X.Левый = P; // P к X
КонецЕсли;
Возврат X; // X - новый корень
КонецФункции
// Поворот ZigZag. G - дедушка, P - родитель, X - потомок.
// Параметр XЛевый указывает, является ли X левым потомком P.(G->P и P->X разнонаправленные)
// Возвращает новый корень поддерева (узел X).
Функция ПоворотZigZag(G, XЛевый)
Если XЛевый Тогда
// G -> P (правый), P -> X (левый)
P = G.Правый;
X = P.Левый;
P.Левый = X.Правый; // C к P
G.Правый = X.Левый; // B к G
X.Левый = G; // G к X
X.Правый = P; // P к X
Иначе
// G -> P (левый), P -> X (правый)
P = G.Левый;
X = P.Правый;
P.Правый = X.Левый; // B к P
G.Левый = X.Правый; // C к G
X.Левый = P; // P к X
X.Правый = G; // G к X
КонецЕсли;
Возврат X; // X - новый корень
КонецФункции
// Рекурсивная процедура для обхода дерева в порядке "in-order" (левый-корень-правый).
// Именно этот обход для двоичного дерева поиска дает отсортированную последовательность.
//
// Параметры:
// Узел - Структура - текущий узел дерева
// КоллекцияРезультата- Массив - массив, в который записываются отсортированные значения
//
Процедура ВыполнитьОбходInOrder(Узел, КоллекцияРезультата)
Если Узел = Неопределено Тогда
Возврат;
КонецЕсли;
// 1. Сначала обходим левое поддерево (там все значения меньше)
ВыполнитьОбходInOrder(Узел.Левый, КоллекцияРезультата);
// 2. Затем добавляем значение самого узла
КоллекцияРезультата.Добавить(Узел.Значение);
// 3. В конце обходим правое поддерево (там все значения больше)
ВыполнитьОбходInOrder(Узел.Правый, КоллекцияРезультата);
КонецПроцедуры
"Почему структура"? - код, основанный на структурах, выглядит лаконично и ясно, а также работает быстро.
Алгоритм Day-Stout-Warren (DSW): Этот алгоритм известен тем, что преобразует BST в "виноградную лозу", а затем балансирует ее, чтобы получить максимально сбалансированное дерево. Я постарался максимально точно воспроизвести его логику, включая этапы преобразования и итоговую балансировку.
&НаКлиенте
Процедура СортировкаDSW(Команда)
//-- массив чисел на форме.
МассивЧисел = ЭтаФорма.Список3.ВыгрузитьЗначения();
СлучайныйКореньДерева = Неопределено;
ОтсортированныйМассив = Новый Массив;
//-- 1 Создаем случайное, несбалансированное дерево
Для Каждого Значение Из МассивЧисел Цикл
СлучайныйКореньДерева = ВставитьВBST(СлучайныйКореньДерева, Значение);
КонецЦикла;
//-- 3 вызов DSW-балансировки
СбалансированныйКорень = СбалансироватьДеревоПоDSW(СлучайныйКореньДерева);
ВыполнитьОбходInOrder(СбалансированныйКорень, ОтсортированныйМассив);
ТабДок = ВизуализироватьSplayДерево(СбалансированныйКорень);
ЭтаФорма.Список3.ЗагрузитьЗначения(ОтсортированныйМассив);
КонецПроцедуры
Функция СбалансироватьДеревоПоDSW(ИсходныйКорень)
//-- 1 Создание "виноградной лозы"
РазмерЛозы = 0;
КореньЛозы = СоздатьВинограднуюЛозу(ИсходныйКорень, РазмерЛозы);
//КореньЛозы = СоздатьДвусвязнуюЛозу(ИсходныйКорень, РазмерЛозы); -
//-- 2 Превращение лозы в сбалансированное дерево
КоренСбалансированногоДерева = СбалансироватьЛозу(КореньЛозы, РазмерЛозы);
//КоренСбалансированногоДерева = СбалансироватьЛозуПоКлассике(КореньЛозы, РазмерЛозы); // - бесконечный цикл
Возврат КоренСбалансированногоДерева;
КонецФункции
// Процедура преобразования в "виноградную лозу".
// Процедура возвращает новый корень лозы, а размер записывает в переменную.
//
// Параметры:
// Корень - Структура - корень исходного дерева
// РазмерЛозы - Число - количество узлов (передается по ссылке для изменения)
//
// Возвращаемое значение:
// Структура - корень полученной лозы
Функция СоздатьВинограднуюЛозу(Корень, РазмерЛозы)
ТекущийКорень = Корень;
РазмерЛозы = 0;
ПредыдущийУзел = Неопределено;
Пока ТекущийКорень <> Неопределено Цикл
// Внутренний цикл: пока у корня есть левый потомок,
// делаем поворот, чтобы левый стал новым корнем.
Пока ТекущийКорень.Левый <> Неопределено Цикл
ТекущийКорень = ПоворотZig(ТекущийКорень, Истина);
КонецЦикла;
// Теперь у ТекущийКорень нет левых потомков.
// Присоединяем его к "хвосту" нашей лозы.
Если ПредыдущийУзел = Неопределено Тогда
// Это первый узел, он станет новым главным корнем лозы.
НовыйГлавныйКорень = ТекущийКорень;
Иначе
// Это не первый узел, делаем его правым потомком предыдущего.
ПредыдущийУзел.Правый = ТекущийКорень;
КонецЕсли;
// Запоминаем текущий узел как "хвост" и переходим дальше.
ПредыдущийУзел = ТекущийКорень;
ТекущийКорень = ТекущийКорень.Правый;
РазмерЛозы = РазмерЛозы + 1;
КонецЦикла;
Возврат НовыйГлавныйКорень;
КонецФункции
// Превращает "виноградную лозу" в сбалансированное дерево с помощью встроенных логарифмов.
//
// Параметры:
// КореньЛозы - Структура - корень "лозы"
// N - Число - количество узлов в лозе
//
// Возвращаемое значение:
// Структура - корень сбалансированного дерева
//
Функция СбалансироватьЛозу(КореньЛозы, N)
Результат = СбалансироватьДеревоРекурсивно(КореньЛозы, N);
Возврат Результат.Корень;
КонецФункции
// Подход 2: Альтернативный, с более чистой реализациии второго этапа DSW - "Рекурсивная сборка"
// 1. Корень - построенное поддерево.
// 2. КонецЛозы - узел, с которого нужно продолжить сборку.
Функция СбалансироватьДеревоРекурсивно(НачалоЛозы, КоличествоУзлов)
// База рекурсии: если узлов для поддерева нет
Если КоличествоУзлов <= 0 Тогда
Возврат Новый Структура("Корень, КонецЛозы", Неопределено, НачалоЛозы);
КонецЕсли;
// 1. Определяем, сколько узлов пойдет на левое и правое поддеревья
ЛевыеУзлы = Цел(КоличествоУзлов / 2);
ПравыеУзлы = КоличествоУзлов - ЛевыеУзлы - 1;
// 2. Рекурсивно строим левое поддерево из первых `ЛевыеУзлов` узлов лозы
ЛеваяРезультат = СбалансироватьДеревоРекурсивно(НачалоЛозы, ЛевыеУзлы);
// 3. Следующий узел после левой части становится корнем текущего поддерева
Корень = ЛеваяРезультат.КонецЛозы;
// 4. Рекурсивно строим правое поддерево из оставшихся `ПравыеУзлов` узлов
// Началом для правой части будет узел, следующий за корнем
ПраваяРезультат = СбалансироватьДеревоРекурсивно(Корень.Правый, ПравыеУзлы);
// 5. Собираем все вместе: устанавливаем полученные поддеревья для корня
Корень.Левый = ЛеваяРезультат.Корень;
Корень.Правый = ПраваяРезультат.Корень;
// 6. Возвращаем результат: построенное поддерево и конец всей лозы
КонецЛозы = ПраваяРезультат.КонецЛозы;
Возврат Новый Структура("Корень, КонецЛозы", Корень, КонецЛозы);
КонецФункции
// Подход 1: -- классический вариант DSW с математикой и поворотами --
// Эта функция использует многократные проходы по лозе и повороты Zig
// для преобразования ее в сбалансированное дерево.
Функция СбалансироватьЛозуПоКлассике(КореньЛозы, N)
// --- Этап 1: Создание "почти полного" дерева ---
// Вычисляем количество узлов для идеальной части дерева
M = ДваВСтепени(Цел(Log(N + 1) / Log(2))) - 1;
ПоворотовСделать = N - M;
Текущий = КореньЛозы;
// Делаем N-M поворотов через каждые два узла
Для i = 1 По ПоворотовСделать Цикл
// Проверяем наличие узлов для поворота
Если Текущий.Правый = Неопределено ИЛИ Текущий.Правый.Правый = Неопределено Тогда
Прервать;
КонецЕсли;
// Узел, который будем поднимать
УзелДляПоворота = Текущий.Правый;
// Выполняем левый поворот Zig с помощью нашей функции
НовыйКореньПоддерева = ПоворотZig(Текущий, Ложь); // Поворот направо
// Перепривязываем новую структуру в общую лозу
Родитель = Текущий.Предыдущий;
Если Родитель <> Неопределено Тогда
Родитель.Правый = НовыйКореньПоддерева;
Иначе
КореньЛозы = НовыйКореньПоддерева; // Это новый корень всей лозы
КонецЕсли;
// Перемещаемся на два узла вперед по НОВОЙ структуре
Текущий = НовыйКореньПоддерева.Правый.Правый;
КонецЦикла;
// --- Этап 2: Полная балансировка ---
// Устанавливаем N = M и повторяем проходы
N = M;
Пока N > 1 Цикл
N = Цел(N / 2);
Текущий = КореньЛозы;
Для i = 1 По N Цикл
// Проверяем наличие узлов для поворота
Если Текущий.Правый = Неопределено ИЛИ Текущий.Правый.Правый = Неопределено Тогда
Прервать;
КонецЕсли;
УзелДляПоворота = Текущий.Правый;
НовыйКореньПоддерева = ПоворотZig(Текущий, Ложь);
Родитель = Текущий.Предыдущий;
Если Родитель <> Неопределено Тогда
Родитель.Правый = НовыйКореньПоддерева;
Иначе
КореньЛозы = НовыйКореньПоддерева;
КонецЕсли;
Текущий = НовыйКореньПоддерева.Правый.Правый;
КонецЦикла;
КонецЦикла;
Возврат КореньЛозы;
КонецФункции
// Функция, которая создает лозу с ссылками на предыдущие узлы
Функция СоздатьДвусвязнуюЛозу(Корень, РазмерЛозы)
ТекущийКорень = Корень;
РазмерЛозы = 0;
ПредыдущийУзел = Неопределено;
Пока ТекущийКорень <> Неопределено Цикл
Пока ТекущийКорень.Левый <> Неопределено Цикл
ТекущийКорень = ПоворотZig(ТекущийКорень, Истина);
КонецЦикла;
// Добавляем ссылку на предыдущий узел!
ТекущийКорень.Предыдущий = ПредыдущийУзел;
Если ПредыдущийУзел = Неопределено Тогда
НовыйГлавныйКорень = ТекущийКорень;
Иначе
ПредыдущийУзел.Правый = ТекущийКорень;
КонецЕсли;
ПредыдущийУзел = ТекущийКорень;
ТекущийКорень = ТекущийКорень.Правый;
РазмерЛозы = РазмерЛозы + 1;
КонецЦикла;
Возврат НовыйГлавныйКорень;
КонецФункции
Функция ДваВСтепени(Степень)
Результат = Pow(2, Степень);
Возврат Результат;
КонецФункции
Так у меня и не получилось заставить работать функцию "СбалансироватьЛозуПоКлассике", так же как и "СбалансироватьДеревоРекурсивно" — уходит в бесконечный цикл.
Смотреть дерево в стандартной форме 1С это просто ужас, поэтому вот что-то такое, хоть и не точное в плане визуализации.
//--------------------------------------------------------------------- Визуализация дерева ------------------------------------------------------------------------------------------------------
// Функция формирует табличный документ с визуализацией дерева значений.
//
// Параметры:
// Дерево - ДеревоЗначений - дерево, которое нужно визуализировать
//
// Возвращаемое значение:
// ТабличныйДокумент - готовый документ с изображением дерева
//
Функция ВизуализироватьSplayДерево(КореньДерева)
ТабДок = Новый ТабличныйДокумент;
// Получаем макет. Этот способ работает и на форме, и в серверном контексте
Обработка = РеквизитФормыВЗначение("Объект");
Макет = Обработка.ПолучитьМакет("МакетДерева");
// Выводим заголовок
ОбластьЗаголовка = Макет.ПолучитьОбласть("Заголовок");
ТабДок.Вывести(ОбластьЗаголовка);
// Запускаем рекурсивный вывод, начиная с самого корня
ВывестиУзлыДерева(ТабДок, Макет, КореньДерева, "", Истина);
Возврат ТабДок;
КонецФункции
// Рекурсивная процедура для вывода узлов дерева, построенного на Структурах.
//
// Параметры:
// ТабДок - ТабличныйДокумент - документ, куда производится вывод
// Макет - ТабличныйДокумент - макет для получения областей
// Узел - Структура - текущий узел дерева
// Префикс - Строка - префикс (ствол) для текущего уровня
// ЭтоLastБрат - Булево - Истина, если родительский элемент был последним
//
Процедура ВывестиУзлыДерева(ТабДок, Макет, Узел, Префикс, ЭтоLastБрат)
Если Узел = Неопределено Тогда
Возврат;
КонецЕсли;
ОбластьСтроки = Макет.ПолучитьОбласть("Строка");
// --- Формируем строку целиком ---
// Определяем символ ветки для текущего элемента
СимволВетки = "";
// Для корневого узла не рисуем символ ветки
Если Префикс <> "" Тогда
СимволВетки = "^92;^72;^72; ";
КонецЕсли;
// Собираем итоговую строку
ПолнаяСтрока = Префикс + СимволВетки + Строка(Узел.Значение);
ОбластьСтроки.Параметры.Строка = ПолнаяСтрока;
// Выводим строку в документ
ТабДок.Вывести(ОбластьСтроки);
// --- Готовим префикс для дочерних элементов ---
НовыйПрефикс = Префикс;
// Если узел не корневой, добавляем к префиксу ствол от родителя
Если Префикс <> "" Тогда
// Если родитель был не последним, его ствол продолжается
Если Не ЭтоLastБрат Тогда
НовыйПрефикс = Префикс + "^74; ";
Иначе
// Если родитель был последним, на его месте пусто
НовыйПрефикс = Префикс + " ";
КонецЕсли;
Иначе
// Это корень дерева, у него нет "ствола" выше, но у детей будут отступы
НовыйПрефикс = " ";
КонецЕсли;
// Рекурсивный вызов для дочерних элементов
// Сначала выводим "левое" поддерево (меньшие значения)
ВывестиУзлыДерева(ТабДок, Макет, Узел.Левый, НовыйПрефикс, Ложь); // Левый не может быть последним, если есть правый
// Затем выводим "правое" поддерево (большие или равные значения)
ВывестиУзлыДерева(ТабДок, Макет, Узел.Правый, НовыйПрефикс, Истина); // Правый - последний
КонецПроцедуры
//--------------------------------------------------------------------- Визуализация дерева ------------------------------------------------------------------------------------------------------
Я понимаю, что BST и его балансировка — это не те структуры, которые часто встречаются в повседневной разработке на 1С. Однако я считаю, что такие задачи помогают глубже понять принципы работы алгоритмов, развить навыки работы с рекурсией, указателями (ссылками) и оптимизации кода.
Это мой первый опыт реализации подобных алгоритмов на 1С, поэтому любая конструктивная критика будет очень полезна для моего дальнейшего развития.
Заранее благодарю всех, кто уделит время моему проекту!
Источники
Проверено на следующих конфигурациях и релизах:
- Бухгалтерия предприятия, редакция 3.0, релизы 3.0.194.23
Вступайте в нашу телеграмм-группу Инфостарт