Полное двоичное дерево как эффективная структура данных - PullRequest
Новая
       9

Полное двоичное дерево как эффективная структура данных

3 голосов
/ 06 августа 2011

Вам дан массив размером n (n - степень двойки). Все записи массива инициализируются нулями. Вы должны выполнить последовательность следующих онлайн операций:

  1. Add(i,x), который добавляет x к записи A[i].
  2. Отчет sum(i,j) = сумма записей в массиве от индексов i до j для любого 0 < i < j <= n.

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

Я думаю, что решение - это дерево сегментов, но я знал, ошибаюсь я или нет?

Ответы [ 2 ]

1 голос
/ 07 августа 2011

Ну, вы можете сделать это с деревом или с более эффективной структурой данных. В любом случае вам не нужно дерево сегментов - оно более ориентировано на поиск и меньше ориентировано на данные.

Из соображений эффективности я бы пошел с массивом массивов, где первый массив имеет размер n, следующий массив имеет размер n / 2, n / 4, n / 8, ... 1. Всякий раз, когда вы добавляете от x до A [i] (первый массив), вы также добавляете его к индексу (i >> 1) (он же i / 2) во втором массиве, к индексу (i >> 2) (он же i / 4) в третий массив и т.д ...

Хитрость в расчете суммы (i, j). Теперь мы собираемся вычислить и сумму (0, j) и сумму (0, i - 1), потому что сумма (i, j) = сумма (0, j) - сумма (0, i - 1).

Чтобы вычислить сумму (0, v) (для некоторых v), все, что вам нужно сделать, это добавить не более одной записи с каждого уровня. Псевдокод для суммирования от 0 до индекса * без учета самого индекса выглядит следующим образом: 

sum from 0 to index:
begin
    i = 0
    sum = 0
    while i < maxlevel
        if ((index >> i) & 1) != 0
            sum = sum + array[i][index]
    return sum
end

Чтобы понять, почему это работает, подумайте о массиве самого низкого уровня и суммировании от 0 до четного индекса против нечетного индекса. Если вы используете четный индекс, вы можете просто сделать это более эффективно, используя массив чуть выше него, так как он уже имеет каждые две суммы, суммированные уже! Фактически, для индекса нечетных чисел вы можете просто сделать то же самое, что и для четного индекса, но вручную добавить одну запись, которая является «нечетным человеком». Но так как вы собираетесь суммировать индексы на втором уровне, вы можете просто сделать все, но, возможно, последний (если новый индекс для суммирования) будет странным. И т. Д., И т. Д. здесь делаешь.

Это должны быть все кусочки, которые вам нужны. Если вы хотите сделать это с бинарным деревом, вы все равно можете сделать то же самое. Вы можете хранить сумму в каждом узле двоичного дерева. Когда вы пересекаете, чтобы добавить сумму к определенному узлу, также добавьте ее ко всем узлам, которые вы пересекаете. Точно так же вы можете использовать тот же трюк, чтобы найти трюк от нуля до индекса. Поиск суммы от нуля до индекса теперь становится обходом двоичного дерева, где для каждого пройденного вами узла вы добавляете сумму узла и вычитаете любого потомка «правой руки» (или более высокого значения), которого вы не обходите.

Надеюсь, я не испортил проблему с домашним заданием, и, прочитав это, вы почувствуете достаточно аромата, чтобы справиться с этим, но не настолько, чтобы проблема теперь стала простой реализацией.

Удачи!

0 голосов
/ 07 августа 2011

решение дерева:

создайте полное дерево, листья которого являются вашими входами: 1,2, ..., n
node.value = inserted value [if node is a leaf]
node.value = node.left.value + node.right.value [if node is not a leaf]

так, на самом деле - для каждого поддерева значение его корня является суммой значений всех его узлов.

обновление записи - это O (logn), так как вам нужно обновлять суммы вплоть до корня.

для суммы (i, j) мы найдем сумму всех элементов слева от i и всех элементов справа от j и вычтем ее из root.value, и мы получим то, что нам нужно.так: 

 sum(root,i,j) = root.value - sumLeft(i,root) - sumRight(j,root)

расчет sumLeft() и sumRight() прост, [для sumLeft:] просто начните с корня вниз до нижней границы, и каждый раз, когда вы идете влево, вычитайте правуюТаким образом, вы вырезаете из суммы не нужные узлы.[убедите себя, почему это так].в конце сумма имеет только релевантные узлы.тот же принцип для sumRight, но вместо этого мы вычитаем левых сыновей.
псевдокод: 

sumLeft(x,root):
  curr <- root
  sum <- root.value
  while (curr is not a leaf):
      if (x is in curr.right):
         curr <- curr.right
      else:
         sum <- sum - curr.right.value
         curr <- curr.left
  return sum
sumRight(x,root):
  curr <- root
  sum <- root.value
  while (curr is not a leaf):
      if (x is in curr.left):
         curr <- curr.left
      else:
         sum <- sum - curr.left.value
         curr <- curr.right
  return sum

Итак, sum (root, i, j) требует от вас дважды спуститься по дереву, которое по-прежнему равно O (logn).

РЕДАКТИРОВАТЬ1:

это то, как вы добавляете x к элементу i на корне: [вопрос указывает на то, что опора добавляет элемент, а не заменяет его, так что эторешение предполагает.его также можно легко модифицировать для вставки]. 

add(root,i,x):
  root.value <- root.value + x
  if root is leaf:
      return
  else if i is in root.left:
     add(root.left,i,x)
  else:
     add(root.right,i,x)

обратите внимание, что вы можете точно знать, какому поддереву (левому или правому) корня принадлежит запись, которой принадлежит [если i < n/2 слеваостальное справа.объясните себе, как это делается для любого поддерева, а не только для корня.

РЕДАКТИРОВАТЬ 2:
пример для дерева с 8 элементами: 

                21
      10                 11
  4        6        7        4
1  3     2  4     6   1    2   2

обобщить пример:

сумма (4,6) должна предоставить 4 + 6 + 1 = 11.
sumLeft (4) должен предоставить 1 + 3 + 2 = 6, и он обеспечивает: sumLeft(4) = 21 - 11 - 4 = 6, как и ожидалось.
sumRight (6) должен предоставить 2 + 2 = 4, а он обеспечивает sumLeft(6) = 21 - 11 - 7 =4.[как ожидается]
так, в целом: sum(4,6) = 21 - 6 - 4 = 11, как и ожидалось.

добавить пример:
добавить (2,4) [добавление 4 ко 2-му элементу]приведет к изменению дерева на: 

                25
      14                 11
  8        6        7        4
1  7     2  4     6   1    2   2
...