Реально ли сделать сбалансированное дерево поиска на массиве? [решено: свой менеджер кучи на массиве]

Revision ru3, by dmkz, 2018-06-17 18:32:44

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

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

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian dmkz 2018-06-17 18:32:44 40
ru2 Russian dmkz 2018-06-17 16:49:14 30
ru1 Russian dmkz 2018-06-17 16:48:16 605 Первая редакция (опубликовано)