dmkz's blog

By dmkz, history, 6 years ago, In Russian

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

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

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

  • Vote: I like it
  • 0
  • Vote: I do not like it