Clasele 11-12 lecția 5 - 30 oct 2015: Difference between revisions
From Algopedia
Jump to navigationJump to search
(→Temă) |
(No difference)
|
Latest revision as of 15:13, 31 October 2015
Arbore binar de căutare
#include <cstdio>
#include <algorithm>
using std::pair;
class BST { // Binary Search Tree
public:
int value;
BST* left;
BST* right;
};
BST* find(BST* node, int value) {
if (node == NULL || node->value == value) {
return node;
} else if (node->value < value) {
return find(node->right, value);
} else { // if (value < node->value)
return find(node->left, value);
}
}
pair<BST*, BST*> split(BST* node, int value) {
pair<BST*, BST*> answer;
if (node == NULL) {
answer.first = NULL;
answer.second = NULL;
} else if (node->value <= value) {
answer.first = new BST;
answer.first->value = node->value;
answer.first->left = node->left;
pair<BST*, BST*> splitAnswer = split(node->right, value);
answer.first->right = splitAnswer.first;
answer.second = splitAnswer.second;
delete node;
} else { // value < node->value
answer.second = new BST;
answer.second->value = node->value;
answer.second->right = node->right;
pair<BST*, BST*> splitAnswer = split(node->left, value);
answer.first = splitAnswer.first;
answer.second->left = splitAnswer.second;
delete node;
}
return answer;
}
BST* join(BST* first, BST* second) {
if (first == NULL) {
return second;
} else {
first->right = join(first->right, second);
return first;
}
}
BST* insert(BST* node, int value) {
pair<BST*, BST*> splitAnswer = split(node, value);
BST* answer = new BST;
answer->value = value;
answer->left = splitAnswer.first;
answer->right = splitAnswer.second;
return answer;
}
BST* erase(BST* node, int value) {
if (node == NULL) {
return NULL;
} else if (node->value == value) {
BST* answer = join(node->left, node->right);
delete node;
return answer;
} else if (node->value < value) {
node->right = erase(node->right, value);
return node;
} else { // if (value < node->value)
node->left = erase(node->left, value);
return node;
}
}
void dump(BST* node, int depth = 0) {
if (node != NULL) {
dump(node->left, depth + 1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", node->value);
dump(node->right, depth + 1);
}
}
int main(void) {
BST* arb = NULL;
arb = insert(arb, 5);
arb = insert(arb, 3);
arb = insert(arb, 6);
arb = insert(arb, 4);
arb = insert(arb, 9);
arb = insert(arb, 1);
arb = insert(arb, 7);
//dump(arb);
//printf("\n");
arb = erase(arb, 7);
//dump(arb);
return 0;
}
Heap
class Heap {
public:
int value;
Heap* left;
Heap* right;
};
Heap* insert(Heap* node, int value) {
if (node == NULL) {
node = new Heap;
node->value = value;
node->left = NULL;
node->right = NULL;
} else if (node->value < value) {
int oldValue = node->value;
node->value = value;
if (rand() % 2 == 1) {
node->left = insert(node->left, oldValue);
} else {
node->right = insert(node->right, oldValue);
}
} else { // if (value <= node->value)
if (rand() % 2 == 1) {
node->left = insert(node->left, value);
} else {
node->right = insert(node->right, value);
}
}
return node;
}
int top(Heap* node) {
return node->value;
}
Heap* pop(Heap* node) {
if (node == NULL) {
return NULL;
} else { // if (node != NULL)
if (node->left == NULL) {
Heap* answer = node->right;
delete node;
return answer;
} else if (node->right == NULL) {
Heap* answer = node->left;
delete node;
return answer;
} else if (node->right->value < node->left->value) {
node->value = node->left->value;
node->left = pop(node->left);
return node;
} else { // if (node->left->value <= node->right->value)
node->value = node->right->value;
node->right = pop(node->right);
return node;
}
}
}
void dump(Heap* node, int depth = 0) {
if (node != NULL) {
dump(node->left, depth + 1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", node->value);
dump(node->right, depth + 1);
}
}
int main() {
Heap* h = NULL;
h = insert(h, 5);
h = insert(h, 3);
h = insert(h, 6);
h = insert(h, 4);
h = insert(h, 9);
h = insert(h, 1);
h = insert(h, 7);
dump(h);
for (int i = 0; i < 7; i++) {
printf("%d ", top(h));
h = pop(h);
}
return 0;
}
Temă
Pentru data viitoare veți avea de rezolvat următoarele 2 probleme: