Балансировка авл дерева

Посмотри в любой книжке по деревьям и/или алгоритмам. Про красно-черные есть почти везде (например в кормене), про АВЛ-деревья точно есть есть в книжке М.Сибуя, Т.Ямамото "алгоритмы обработки данных" (с оценками сложности). На самом деле, если что-нибудь одно почитать, сможешь сам по аналогии как хочешь балансировать.

Ну и не забывайте, что в STL библиотеке это уже реализовано. STL - Си++, а если нужно на Си - поможет библиотека http://ip.osgf.ge/GNU/avl/