Блог пользователя dmkz

Автор dmkz, история, 6 лет назад, По-русски

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

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

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Массив мало чем от обычной памяти отличается: заменяем указатели на индексы в массиве, для выделения элемента берём первый неиспользованный элемент массива. Так можно любую структуру написать "на массиве", если она состоит из одинаковых элементов (вроде вершин).

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо, значит нужно писать свой аналог менеджера кучи, а я изначально подумал, что в задаче требуются индексы для дочерних элементов вроде 2 * i + 1 и 2 * i + 2, как в дереве отрезков.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Это очень вряд ли, потому что такие индексы задают фиксированную структуру дерева, а самобалансирующиеся как раз свою структуру активно меняют, причём основная операция — "переподвесить поддерево", её через "перенумеровать вершины" не выразить (потому что надо перенумеровывать всё поддерево).