Мы рассматриваем сбалансированные деревья в определении, данном
китайским школьником Chen Quifeng.
Статья "Size Balanced Tree"
URL: http://yaoziyuan.googlepages.com/SizeBalancedTree.zip
(Zhongshan Memorial Middle School, Guangdong, China, 2006 год)
Новый адрес материалов: http://ihome.ust.hk/~cs_cqx/SBT.zip
Новый E-mail Chen'а: [email protected]

Аналогичную задачу выполняют binary search trees, определенные
японскими исследователями Youchi Hirai и Kazuhiko Yamamoto.
Статья "Balancing weight-balanced trees",
URL: http://hagi.is.s.u-tokyo.ac.jp/~yh/bst.pdf
(Cambridge University Press, 2011 год)

Работа японских исследователей выглядит внушительно, и их
weight-balanced tree выполняет в точности ту же задачу, что и
у китайца. Рассматривается большее число случаев взаимного
расположения вершин/размеров/весов, и большее число типов вращений
(вместо одного типа "rotation" - два типа: "rotation" и "double rotation").
Принцип работы "деревьев японцев" (weight-balanced, WBT) не такой
сложный, и при желании можно повторить его. Он реализован внутри
некоторых реализаций функциональных языков, таких как Haskell.


Что нужно (функции):
+ 1. Вставка + последующая автоматическая балансировка
+ 2. Удаление + балансировка
+ 3. Балансировка чтобы мало занимала процессорного времени.
+ 4. Поиск
+ 5. Узнать размер дерева
  6. Быстрый проход по "прошитому" дереву
  7. Оптимизировать программу по скорости вставки/удаления/поиска/обхода.

Ссылка на страницу постановщика задач: http://vk.com/Konard