Untitled
unknown
plain_text
2 years 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]