Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
16 kB
4
Indexable
Never
1) Write a dynamic data structure that maintains a collection of integers, subject to the
following operations:
a. void insert(int): inserts a new element in the collection, only if it is not
already present.
Complexity: O(log(n)). /1
b. int size(void): returns the size of the collection.
Complexity: O(1). /1
c. int min(void): returns the minimum element in the collection.
Complexity: O(1). /1
d. int max(void): returns the maximum element in the collection.
Complexity: O(1). /1
e. void delete(int): removes an element from the collection.
Complexity: O(log(n)). /1

///  ///////////////////////////1/
class myDataStructure
{
          set<int, greater<int>> s;

public: // are default constructor
          void insert(int);
          int min();
          int max();
          int size();
          void deleteX(int);
};

void myDataStructure::insert(int i)
{

          s.insert(i);
};
int myDataStructure::min()
{

          return *s.begin();
};
int myDataStructure::max()
{
          return *s.rbegin();
};
int myDataStructure::size()
{
          return s.size();
};
void myDataStructure::deleteX(int i)
{
          s.erase(s.find(i));
}

2) In what follows, we consider the following implementation for binary trees:
struct node {
int value;
node *left,*right;
};
typedef node *BinaryTree;
a. Write a function bool isSearchTree(BinaryTree& T) that checks
whether the input is a binary search tree.
Complexity: O(n) /1
b. Write a function bool isAVL(BinaryTree& T) that checks whether the input
is an AVL.
Complexity: O(n) /1
c. Write functions int floor(BinaryTree& T, int x) and int
ceil(BinaryTree& T, int x) such that given a binary search tree T and an
integer x, floor(T,x) outputs the largest value in T smaller than or equal to x, while
ceil(T,x) outputs the smallest value in T greater than or equal to x.
Complexity: O(log(n)) if T is an AVL (unspecified otherwise). /2
d. Write a function void range(BinaryTree& T, int x, int y), that
outputs on the terminal up to 5 values in T that are between x and y.
Complexity: O(log(n)) if T is an AVL (unspecified otherwise). /1

a.
bool isSearchTree(Node *T) {
          // Verificam daca nodul curent este nullptr (nu exista)
          // Daca este, inseamna ca arborele este un search tree, deci returnam true
          if (T == nullptr)
                    return true;

          // Daca nodul curent are atat un subarbore stang cat si un subarbore drept,
          // verificam daca acestea sunt search tree-uri si daca nodul curent respecta proprietatile unui search tree
          if (T->left != nullptr && T->right != nullptr) {
                    bool left = isSearchTree(T->left); // Verificam daca subarborele stang este un search tree
                    bool right = isSearchTree(T->right); // Verificam daca subarborele drept este un search tree
                    // Returnam true daca:
                    // 1. Valoarea nodului stang este mai mica decat valoarea nodului curent
                    // 2. Valoarea nodului drept este mai mare decat valoarea nodului curent
                    // 3. Subarborele stang este un search tree
                    // 4. Subarborele drept este un search tree
                    return T->left->value < T->value && T->right->value > T->value && left && right;
          }
          // Daca nodul curent are doar un subarbore stang, verificam daca acesta este un search tree
          // si daca nodul curent respecta proprietatile unui search tree
          else if (T->left != nullptr) {
                    bool left = isSearchTree(T->left);
                    // Returnam true daca:
                    // 1. Valoarea nodului stang este mai mica decat valoarea nodului curent
                    // 2. Subarborele stang este un search tree
                    return T->left->value < T->value && left;
          }
          // Daca nodul curent are doar un subarbore drept, verificam daca acesta este un search tree
          // si daca nodul curent respecta proprietatile unui search tree
          else if (T->right != nullptr) {
                    bool right = isSearchTree(T->right);
                    // Returnam true daca:
                    // 1. Valoarea nodului drept este mai mare decat valoarea nodului curent
                    // 2. Subarborele drept este un search tree
                    return T->right->value > T->value && right;
          }
          // Daca nodul curent nu are niciun subarbore, inseamna ca este o frunza,
          // deci returnam true, deoarece frunzele sunt intotdeauna respecta proprietatile unui search tree
          else
                    return true;
}

b.

map<Node *, int> heights; // map pentru a stoca inaltimile nodurilor

bool isAVL(Node *root) // functia care verifica daca arborele e AVL
{
          if (root == nullptr) // daca radacina e null, arborele e gol, deci e echilibrat
                    return true;
          else if (root->left != nullptr && root->right != nullptr)
          {
                    bool left = isAVL(root->left); // verificam arborele din stanga
                    bool right = isAVL(root->right); // verificam arborele din dreapta
                    heights[root] = heights[root->left] < heights[root->right] ? heights[root->left] + 1 : heights[root->right] + 1;
                    // calculam inaltimea curenta
                    return left && right && abs(heights[root->left] - heights[root->right]) <= 1;
                    // returnam true daca arborele din stanga e AVL, arborele din dreapta e AVL si diferenta de inaltimi nu depaseste 1
          }
          else if (root->left != nullptr)
          {
                    bool left = isAVL(root->left); // verificam doar arborele din stanga
                    heights[root] = heights[root->left] + 1; // calculam inaltimea curenta
                    return left;
                    // returnam true daca arborele din stanga e AVL
          }
          else if (root->right != nullptr)
          {
                    bool right = isAVL(root->right); // verificam doar arborele din dreapta
                    heights[root] = heights[root->right] + 1; // calculam inaltimea curenta
                    return right;
                    // returnam true daca arborele din dreapta e AVL
          }
          else
          {
                    heights[root] = 1; // daca nu avem niciun fiu, inaltimea e 1
                    return true;
                    // returnam true, deoarece frunza e intotdeauna un arbore echilibrat
          }
}

c si d.

void findFloor(Node *root, int x, int &value)
{
          if (root == nullptr)
                    return;
          if (root->value == x)
                    value = root->value;
          if (root->left != nullptr && x < root->value)
          {
                    findFloor(root->left, x, value);
          }
          else if (root->right != nullptr && x > root->value)
          {
                    cout << "sebi" << root->value << endl;
                    value = root->right->value;
                    findFloor(root->left, x, value);
          }
          else
                    return;
}
int floor(Node *root, int x)
{
          int floorOfX;
          findFloor(root, x, floorOfX);
          return floorOfX;
}

int max = 0;
void range(Node *root, int x, int y)
{

          if (root == nullptr || ::max > 5)
                    return;

          if (root->value < y && root->value > x)
          {
                    cout << root->value << " ";
                    ::max++;
          }
          if (root->value > y)
                    range(root->left, x, y);
          else if (root->value < x)
                    range(root->right, x, y);
          else
          {
                    range(root->left, x, y);
                    range(root->right, x, y);
          }
} 


main:


int main()
{
          Node *root = createNode(2);
          root->left = createNode(1);
          root->right = createNode(3);

          // if (isSearchTree(root))
          //           cout << "Da";
          // else

          //           cout << "Nu";

          // root->left->left = createNode(10);
          // root->left->left->left = createNode(5);
          // root->left->left->left->left = createNode(9);
          // if (isAVL(root))
          //           cout << "Da";
          // else

          //           cout << "Nu";

          // cout << floor(root, 6);

          range(root, 0, 4);
}


Colocviul 2:

1) In what follows, we consider the following implementation for binary trees:
struct node {
int value;
node *left,*right;
};
typedef node *BinaryTree;
a. Write a function bool isSearchTree(BinaryTree& T) that checks
whether the input is a binary search tree.
Complexity: O(n) /1
b. Write a function bool isAVL(BinaryTree& T) that checks whether the input
is an AVL.
Complexity: O(n) /1
c. Write a function int biggestSearchTree(BinaryTree& T) that outputs
the size of a largest binary search subtree in T.
Complexity: O(n) /2
d. Write a function int biggestAVL(BinaryTree& T) that outputs the size of
a largest AVL subtree in T.
Complexity: O(n*log(n)) /2
e. A path is monotonic if all values on the path are strictly increasing. Write a function
int longestMonotonicPath(BinaryTree& T) that outputs the length of
a longest monotonic path in T.
Complexity: O(n) /2
f. Write a function bool isInOrder(const vector<int>& v) that being
given a vector v, determines whether it is the inorder of some AVL.
Complexity: O(n). /2

#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
struct node
{
          int value;
          node *st, *dr;
};
node *createNode(int i)
{
          node *p = new node;
          p->value = i;
          p->st = nullptr;
          p->dr = nullptr;
          return p;
}

void DFS(node *root, vector<node *> &DFSV)
{
          if (root == nullptr)
                    return;

          DFSV.push_back(root);
          if (root->st != nullptr && root->dr != nullptr)
          {
                    DFS(root->st, DFSV);
                    DFS(root->dr, DFSV);
          }
          else if (root->st != nullptr)
          {
                    DFS(root->st, DFSV);
          }
          else if (root->dr != nullptr)
          {
                    DFS(root->dr, DFSV);
          }
          else
                    return;
}

int computeSize(node *root, vector<int> &sum)
{
          if (root == nullptr)
                    return 0;

          if (root->st != nullptr && root->dr != nullptr)
          {
                    int st = computeSize(root->st, sum);
                    int dr = computeSize(root->dr, sum);
                    sum.push_back(st + dr + 1);
          }
          else if (root->st != nullptr)
          {
                    int st = computeSize(root->st, sum);
                    sum.push_back(st + 1);
          }

          else if (root->dr != nullptr)
          {

                    int dr = computeSize(root->dr, sum);
                    sum.push_back(dr + 1);
          }
          else
          {
                    sum.push_back(1);
                    return 1;
          }
}

bool computeIsBST(node *root, vector<bool> &isBST)
{
          if (root == nullptr)
                    return true;
          if (root->st != nullptr && root->dr != nullptr)
          {
                    bool st = computeIsBST(root->st, isBST); // verificam daca arborele din dreapta si din stanga este search tree
                    bool dr = computeIsBST(root->dr, isBST);
                    isBST.push_back(root->st->value < root->value && root->dr->value > root->value && st && dr);
                    return root->st->value < root->value && root->dr->value > root->value && st && dr;
                    // toata conditia trb sa fie true
          }
          else if (root->st != nullptr)
          {

                    // avem arbore doar in stanga, in dreapta nu avem ce sa verificam si ne ar crapa daca comparam nullptr
                    bool st = computeIsBST(root->st, isBST);
                    isBST.push_back(root->st->value < root->value && st);
                    return root->st->value < root->value && st;
          }
          else if (root->dr != nullptr)
          {

                    // avem arbore doar in stanga, in dreapta nu avem ce sa verificam si ne ar crapa daca comparam nullptr
                    bool dr = computeIsBST(root->dr, isBST);
                    isBST.push_back(root->dr->value < root->value && dr);
                    return root->dr->value > root->value && dr;
          }
          else
          {
                    isBST.push_back(true);
                    return true;
          } // daca e frunza e sigur SearchTree
}
map<node *, int> heights;
bool computeIsAVL(node *root, vector<bool> &isAvl)
{

          if (root == nullptr)
                    return true;
          else if (root->st != nullptr && root->dr != nullptr)
          {
                    bool st = computeIsAVL(root->st, isAvl);
                    bool dr = computeIsAVL(root->dr, isAvl);
                    heights[root] = heights[root->st] < heights[root->dr] ? heights[root->st] + 1 : heights[root->dr] + 1;
                    isAvl.push_back(st && dr && abs(heights[root->st] - heights[root->dr]) <= 1);
                    return st && dr && abs(heights[root->st] - heights[root->dr]) <= 1;
          }
          else if (root->st != nullptr)
          {
                    bool st = computeIsAVL(root->st, isAvl);

                    heights[root] = heights[root->st] + 1;
                    isAvl.push_back(st);
                    return st;
          }
          else if (root->dr != nullptr)
          {

                    bool dr = computeIsAVL(root->dr, isAvl);
                    heights[root] = heights[root->dr] + 1;
                    isAvl.push_back(dr);
                    return dr;
          }
          else
          {
                    heights[root] = 1;
                    return true;
          }
}
int biggestSearchTree(node *root)
{

          vector<int>
              sizes;
          vector<bool> isBST;

          computeIsBST(root, isBST);
          computeSize(root, sizes);

          int maxSize = -1;
          for (int i = 0; i < sizes.size(); i++)
          {
                    if (sizes[i] > maxSize && isBST[i])
                              maxSize = sizes[i];
          }
          return maxSize;
}
bool hasExactElements(vector<int> &u, vector<int> &v)
{
          map<int, int> u1, v1;
          for (auto i : u)
          {
                    if (!u1[i])
                              u1[i] = 1;
                    else
                              u1[i]++;
          }
          for (auto i : v)
          {
                    if (!v1[i])
                              v1[i] = 1;
                    else
                              v1[i]++;
          }
          bool isExact = true;
          for (auto i : u)
                    if (u1[i] != v1[i])
                              isExact = false;
          for (auto i : v)
                    if (u1[i] != v1[i])
                              isExact = false;
          return isExact;
}
int main()
{
          // node *root = createNode(2);
          // root->st = createNode(1);
          // root->dr = createNode(1);

          // cout << biggestSearchTree(root);

          // vector<int> u = {1, 1, 2, 3}, v = {1, 1, 2, 3};
          // cout << hasExactElements(u, v);
}
// 1 2 3 4 5 v

// 1 3 6 10 15 sum
// 1 2 6 24 120 prod

// 24/6*3 = 12
// 10-6+3=7

// sum[j]-sum[i]+v[i]