Note de curs, probleme algoritmică, clasa IX/X, 23 ianuarie 2015

From Algopedia
Jump to navigationJump to search

În acest curs am implementat un arbore de intervale folosind paradigma programări funcționale.

Definirea și construcția

Inițial, am definit un nod din arborele de intervale. Fiind un arbore binar, fiecare nod are doi fii ordonați, fiul stâng (left) și fiul drept (right). Într-un nod am reținut numărul de frunze din subarborele asociat (size), suma frunzelor (sum) și valoarea adăugată tuturor fruzelor printr-o operație de update (add).

Apoi am implementat funcții care să construiască un arbore de intervale corespunzător unui vector prin de elemente nule respectiv unui vector oarecare de numere.

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>

using namespace std;

class ArbInt {
public:
  const int sum;
  const int add;
  const ArbInt* const left;
  const ArbInt* const right;
  const int size;

  ArbInt(int sum, int add, const ArbInt* const left, const ArbInt* const right, int size) :
      sum(sum), add(add), left(left), right(right), size(size) {
    ;
  }
};

const ArbInt* const emptyArbInt() {
  return NULL;
}

bool isEmpty(const ArbInt* const arbInt) {
  return arbInt == emptyArbInt();
}

const ArbInt* const createArbInt(int size) {
  assert(size > 0);
  if (size == 1)
    return new ArbInt(0, 0, emptyArbInt(), emptyArbInt(), size);
  else
    return new ArbInt(0, 0,
      createArbInt((size + 1) / 2),
      createArbInt(size / 2),
      size);
}

const ArbInt* const createArbInt(int* begin, int* end) {
  if (end - begin == 1)
    return new ArbInt(*begin, *begin, emptyArbInt(), emptyArbInt(), end - begin);
  else {
    const ArbInt* const arb1 = createArbInt(begin, begin + (end - begin) / 2);
    const ArbInt* const arb2 = createArbInt(begin + (end - begin) / 2, end);
    return new ArbInt(
      arb1->sum + arb2->sum,
      0,
      arb1,
      arb2,
      end - begin);
  }
}

Operațiile

Apoi am implementat cele două operații fundamentale pe arborii de intervale:

  • addInterval: adăungarea unei valori tuturor elementelor dintr-un interval (V[i] += val, begin <= i < end);
  • sumInterval: calcularea sumei elementelor dintr-un interval (s += V[i], begin <= i < end).
const ArbInt* const addInterval(const ArbInt* const arbInt, int begin, int end, int add) {
  if (begin == end)
    return arbInt;
  else if (end - begin == arbInt->size)
    return new ArbInt(
      arbInt->sum + arbInt->size * add,
      arbInt->add + add,
      arbInt->left,
      arbInt->right,
      arbInt->size);
  else
    return new ArbInt(
      arbInt->sum + (end - begin) * add,
      arbInt->add,
      addInterval(arbInt->left,
        min(begin, arbInt->left->size),
        min(end, arbInt->left->size), add),
      addInterval(arbInt->right,
        max(0, begin - arbInt->left->size),
        max(0, end - arbInt->left->size), add),
      arbInt->size
    );
}

int sumInterval(const ArbInt* const arbInt, int begin, int end) {
  if (end - begin == arbInt->size)
    return arbInt->sum;
  else if (end <= arbInt->left->size)
    return sumInterval(arbInt->left, begin, end)
      + arbInt->add * (end - begin);
  else if (arbInt->left->size <= begin)
    return sumInterval(arbInt->right,
      begin - arbInt->left->size,
      end - arbInt->left->size)
      + arbInt->add * (end - begin);
  else
    return sumInterval(arbInt->left, begin, arbInt->left->size) +
           sumInterval(arbInt->right, 0, end - arbInt->left->size)
      + arbInt->add * (end - begin);
}

Testarea

În final, am testat operațiile implementate anterior mai întâi scriind o funcție care afișează clar și detaliat structura internă a arborelui de intervale și apoi scriind un program care construiește și efectuează o serie de operații asupra unui arbore de intervale, pentru ca apoi să-l afișeze.

void dump(const ArbInt* const arbInt, int offset = 0) {
  if (!isEmpty(arbInt)) {
    dump(arbInt->right, offset + 1);
    for(int i = 1; i <= 5 * offset; i++)
      printf(" ");
    printf("%d,%d\n", arbInt->sum, arbInt->add);
    dump(arbInt->left, offset + 1);
  }
}

int main() {
  int v[] = {1, 3, 4, 9, 9, 4, 3, 5};
  const ArbInt* const arbInt1 = createArbInt(v, v + 8);
  printf("%d\n", sumInterval(arbInt1, 0, 5));
  printf("%d\n", sumInterval(arbInt1, 1, 8));
  const ArbInt* const arbInt2 = addInterval(arbInt1, 2, 4, 4);
  printf("%d\n", sumInterval(arbInt2, 3, 7));
  dump(arbInt2);
  const ArbInt* const arbInt3 = addInterval(arbInt2, 0, 1, 100);
  printf("%d\n", sumInterval(arbInt3, 0, 8));
  return 0;
}