Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include "Profiler.h"
- Profiler profiler("DynamicOrderStatistics");
- #define max_size 10000
- int op_select = 0;
- int op_delete = 0;
- int op_build = 0;
- typedef struct NodeT
- {
- int data;
- int size;
- struct NodeT *left, *right, *parent;
- } NodeT;
- NodeT* initialize_node(int data)
- {
- NodeT* new_node = (NodeT*)malloc(sizeof(NodeT));
- op_build++;
- new_node->data = data;
- op_build++;
- new_node->size = 1;
- new_node->left = new_node->right = NULL;
- new_node->parent = NULL;
- return new_node;
- }
- NodeT* buildPBT(int a[], int first, int last) //build a PBT from an ordered array
- {
- NodeT* root = (NodeT*)malloc(sizeof(NodeT));
- op_build++;
- if (first <= last)
- {
- int mid = (first + last + 1) / 2;
- root = initialize_node(a[mid]);
- op_build = op_build + 2;
- root->left = buildPBT(a, first, mid - 1);
- root->right = buildPBT(a, mid + 1, last);
- op_build++;
- if (root->left != NULL)
- {
- op_build++;
- root->size = root->size + root->left->size;
- }
- op_build++;
- if (root->right != NULL)
- {
- op_build++;
- root->size = root->size + root->right->size;
- }
- op_build++;
- if (root->left != NULL)
- {
- op_build++;
- root->left->parent = root;
- }
- op_build++;
- if (root->right != NULL)
- {
- op_build++;
- root->right->parent = root;
- }
- return root;
- }
- else
- return NULL;
- }
- void show_tree(NodeT* p, int level)
- {
- if (p != NULL)
- {
- show_tree(p->right, level + 1);
- for (int i = 0; i <= level; i++)
- printf(" ");
- if(p->parent == NULL)
- printf("%d,%d - NULL\n\n", p->data, p->size);
- else
- printf("%d,%d - %d\n\n", p->data, p->size, p->parent->data);
- show_tree(p->left, level + 1);
- }
- }
- NodeT* OS_Select(NodeT* root, int i)
- {
- int r;
- op_select++;
- if (root != NULL)
- {
- op_select++;
- if (root->left != NULL)
- r = root->left->size + 1;
- else
- r = 1;
- if (i == r)
- return root;
- else
- {
- if (i < r)
- return OS_Select(root->left, i);
- else
- return OS_Select(root->right, i - r);
- }
- }
- else
- return NULL;
- }
- NodeT* findMin(NodeT* pNode)
- {
- op_delete++;
- if (pNode == NULL)
- return NULL;
- op_delete++;
- if (pNode->left != NULL)
- return findMin(pNode->left);
- else
- return pNode;
- }
- void transplant(NodeT* root, NodeT* u, NodeT* v)
- {
- op_delete++;
- if (u->parent == NULL)
- {
- root = v;
- op_delete++;
- }
- else
- {
- op_delete++;
- if (u == u->parent->left)
- {
- u->parent->left = v;
- op_delete++;
- }
- else
- {
- op_delete++;
- u->parent->right = v;
- }
- if (v != NULL)
- {
- v->parent = u->parent;
- op_delete++;
- }
- }
- }
- void delete_node(NodeT* root, NodeT* z)
- {
- op_delete++;
- if (z->left == NULL)
- {
- // op_delete++;
- NodeT* aux = z;
- op_delete++;
- while (aux->parent != NULL)
- {
- op_delete++;
- aux->parent->size--;
- op_delete++;
- aux = aux->parent;
- op_delete++;
- }
- op_delete++;
- transplant(root, z, z->right);
- }
- else
- {
- NodeT* aux = z;
- op_delete++;
- while (aux->parent != NULL)
- {
- op_delete++;
- aux->parent->size--;
- op_delete++;
- aux = aux->parent;
- op_delete++;
- }
- op_delete++;
- op_delete++;
- if (z->right == NULL)
- {
- NodeT* aux = z;
- op_delete++;
- while (aux->parent != NULL)
- {
- op_delete++;
- aux->parent->size--;
- op_delete++;
- aux = aux->parent;
- op_delete++;
- }
- op_delete++;
- transplant(root, z, z->left);
- }
- else
- {
- op_delete++;
- NodeT* y = findMin(z->right);
- op_delete++;
- NodeT* aux = y;
- while (aux->parent != NULL)
- {
- op_delete++;
- aux->parent->size--;
- op_delete++;
- aux = aux->parent;
- op_delete++;
- }
- op_delete++;
- op_delete++;
- if (y->parent != z)
- {
- transplant(root, y, y->right);
- op_delete++;
- y->right = z->right;
- op_delete++;
- y->right->parent = y;
- }
- transplant(root, z, y);
- op_delete++;
- y->left = z->left;
- op_delete++;
- y->left->parent = y;
- op_delete++;
- y->size = z->size;
- }
- }
- }
- int main()
- {
- /////////demo
- //NodeT* root = (NodeT*)malloc(sizeof(NodeT));
- //int n = 11;
- //int a[] = { 5, 10, 20, 27, 30, 31, 32, 35, 40, 45, 70 };
- //int i;
- //NodeT* y;
- ////int a[] = { 1, 2, 3, 4};
- ////int n = 4;
- //root = NULL;
- //root = buildPBT(a, 0, n - 1);
- //show_tree(root, 0);
- //
- //i = 7;//leaf 32
- //y = OS_Select(root, i);
- //if (y != NULL)
- // printf("I found the element %d of rank %d\n", y->data, i);
- //else
- // printf("We don't have rank %d in this tree.", i);
- //delete_node(root, y);
- //show_tree(root, 0);
- //i = 5;//one child 30
- //y = OS_Select(root, i);
- //if (y != NULL)
- // printf("I found the element %d of rank %d\n", y->data, i);
- //else
- // printf("We don't have rank %d in this tree.", i);
- //delete_node(root, y);
- //show_tree(root, 0);
- //i = 3;//two children 20
- //y = OS_Select(root, i);
- //if (y != NULL)
- // printf("I found the element %d of rank %d\n", y->data, i);
- //else
- // printf("We don't have rank %d in this tree.", i);
- //delete_node(root, y);
- //show_tree(root, 0);
- //i = 3;//two children 31, root
- //y = OS_Select(root, i);
- //if (y != NULL)
- // printf("I found the element %d of rank %d\n", y->data, i);
- //else
- // printf("We don't have rank %d in this tree.", i);
- //delete_node(root, y);
- //show_tree(root, 0);
- int n, a[max_size];
- for (n = 100; n <= 10000; n += 100)
- {
- op_select = 0;
- op_delete = 0;
- op_build = 0;
- NodeT* root = NULL;
- FillRandomArray(a, n, 0, 10000, 1);
- root = buildPBT(a, 0, n - 1);
- srand(time(NULL));
- int n_ramase = n;
- for (int i = 0; i < n; i++)
- {
- int ith_smallest = rand() % (n_ramase);
- NodeT* val = OS_Select(root, ith_smallest);
- if (val != NULL)
- delete_node(root, val);
- n_ramase--;
- }
- profiler.countOperation("op_select", n, op_select);
- profiler.countOperation("op_delete", n, op_delete);
- profiler.countOperation("op_build", n, op_build);
- profiler.countOperation("Operations", n, op_select + op_delete + op_build);
- profiler.createGroup("Operations", "op_select", "op_delete", "op_build");
- }
- profiler.showReport();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement