Какой самый эффективный алгоритм добавления элемента в дерево?
По идее в таком случае просто нет смысла использовать дерево, эффективнее будет динамически растущий массив с бинарным поиском по нему. 

Еще если сначала сохранить последовательность в массив, то можно потом из нее построить сбалансированное бинарное дерево за O(N), просто обойдя массив рекурсивно в правильном порядке.
В любом случае ты получишь O(N log N) так что AVL.