Подскажите с алгоритмом балансировки троичного дерева сравнений. 
Изложу исходные условия. Так как в дереве элементы - фамилии, то логично сделать ключами буквы алфавита. Причем принять, что A<B<C<...<Z.
Тогда, считывая исходные данные вида :


Получим что то вида (извиняйте что криво) :
                                                          

То есть если у добавляемого элемента первая буква фамилии совпадает с ключом, то он помещается в центр. если меньше, то в левое поддерево. если больше, то вправое. По-моему это самый очевидный  вариант. Если есть какой-то более удачный способ, то буду рад выслушать. Можно было бы попробовать использовать префиксное дерево, но задача именно изложена в троичном дереве.

Ну и очевидно, что тут будет мало общего с АВЛ деревьями. Еще непонятно нужно ли поле balance, одно или два и как осуществлять поиск этого значения (как высчитывать его через три потомка, а не через два как в АВЛ).

Тип опишу на паскале, но если будет код на другом языке - разберусь.

Заранее спасибо.

Это сообщение отредактировал(а) Anark1 - 7.12.2008, 15:19

Что-то ничего умного не приходит в голову (а ваша идея, что в центр класть вершину, у которой ключ равен - мне кажется, она неправильна для сбалансированного дерева, потому что никакой сбалансированности между тремя сыновьями каждой вершины в среднем не наблюдается).

В английском нете немного нашёл на эту тему (ключ "Ternary search tree"), и вот по ссылкам пришёл на статью Слетора и Тарьяна: Self-Adjusting Binary Search Trees (Sleator, Tarjan), там со страницы 23 идёт описание их link/cut tree, который, похоже, и есть сбалансированное троичное дерево.

maxdiver, добрался до этой статьи. Спасибо, уже что-то. Хотя он видится мне довольно тяжелой на подъем.
Я думаю, что должно быть что-нибудь попроще. Возможно, какой-то способ, основанной на условиях задачи. Я правильно понимаю, что сбалансированность означает по сути, что для каждого узла разница любых двух высот потомков равна -1,0,+1? Согласен, что в таком случае существуют небалансируемые деревья, но тогда как выбирать ключи, чтобы не терялся сам смысл использования деревьев?

http://www.cs.ucr.edu/cs14/cs14_06win/slid...ees_covered.pdf
Самое интересное из того, что нашел. Не могу придумать как подобрать ключи... Проблема, что фамилии могут повторяться.

Добавлено через 2 минуты и 46 секунд
Если мой английский меня не подводит, то там написано, что 2-3 деревья гарантированно балансированы при правильном добавлении и удалении...

Похоже нашел грамотную английскую статью. Если решу сабж, то выложу решение.