Здравствуйте!
Дали задание написать сбалансированное дерево поиска с операциями: пробежаться по всем элементам за O(n) в порядке неубывания, вставить новый элемент за O(log(n)), найти определенный элемент за O(log(n)). Известно, что на любой момент работы программы в дереве ≤ n элементов. Дерево должно работать поверх массива размера O(n).
Перед тем, как начать думать о написании своей реализации, полез в интернет, а там ничего нет о реализации сбалансированных деревьях на массивах, в связи с этим встал вопрос: может это и не возможно сделать вовсе?
Массив мало чем от обычной памяти отличается: заменяем указатели на индексы в массиве, для выделения элемента берём первый неиспользованный элемент массива. Так можно любую структуру написать "на массиве", если она состоит из одинаковых элементов (вроде вершин).
Спасибо, значит нужно писать свой аналог менеджера кучи, а я изначально подумал, что в задаче требуются индексы для дочерних элементов вроде 2 * i + 1 и 2 * i + 2, как в дереве отрезков.
Это очень вряд ли, потому что такие индексы задают фиксированную структуру дерева, а самобалансирующиеся как раз свою структуру активно меняют, причём основная операция — "переподвесить поддерево", её через "перенумеровать вершины" не выразить (потому что надо перенумеровывать всё поддерево).