Здравствуйте!

Дали задание написать сбалансированное дерево поиска с операциями: пробежаться по всем элементам O(n), вставить новый элемент O(log(n)), найти определенный элемент O(log(n)). Известно, что на любой момент работы программы в дереве  ≤ n элементов. Дерево должно работать поверх массива размера O(n).

Перед тем, как начать думать о написании своей реализации, полез в интернет, а там ничего нет о реализации сбалансированных деревьях на массивах, в связи с этим встал вопрос: может это и не возможно сделать вовсе?