Хочу написать двоичное дерево для хранения строк. Как упрощенная задача - нужно отсортировать дерево на одном уровне. Т.е. просто отсортировать по одному символу буквы.
Допустим есть дерево
struct Node {
Node * left;
Node * right;
char c;
}
Какие существую варианты балансировки (упорядочивания дерева). Выходит что должен существовать медленный вариант и быстрый но не очень качественный?
Я вижу следующий алгоритм. 1. Создаем линейный массив, методом вставки упорядочиваем его, обходя все дерево. (тут т.к. извесно что елементов будет не более 256, то массив можно заранее создать в стеке) 2. Делим массив пополам, посередине корень, узел слева-посередине(1/4) - левый елемент, узел справа-посередине(3/4) - правый елемент, для деток повторяем деление (можно рекурсией).
Какие существую варианты балансировки деревьев желательно с оценкой затратности алгоритма, может есть ссылка где всё до кучи собрано?