Реально ли сделать сбалансированное дерево поиска на массиве?

Правка ru1, от dmkz, 2018-06-17 16:48:16

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

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

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru3 Русский dmkz 2018-06-17 18:32:44 40
ru2 Русский dmkz 2018-06-17 16:49:14 30
ru1 Русский dmkz 2018-06-17 16:48:16 605 Первая редакция (опубликовано)