Deramid is built as a regular binary search tree, but each element is additionally assigned a priority field, according to which elements must satisfy the pyramid property. When inserted into a deramid, an element is added to the search tree, and then we go up and execute turns (not violating the properties of the tree), while priority violates the pyramid property. What was my mistake when implementing this algorithm? When debugging, we get into some file related to time, and then an access violation message is issued. The program crashes.
struct deramid_node{ int key; int priority; deramid_node *left; deramid_node *right; deramid_node *parent; }; typedef deramid_node deramid; struct deramid_node * create_tree(void){ deramid *root; root = (deramid *)malloc(sizeof(deramid)); root->key = NULL; root->parent = NULL; root->left = NULL; root->right = NULL; return root; } void left_rotate(deramid *root, deramid *x){ deramid *y = x->right; x->right = y->left; if(y->left != NULL) y->left->parent = x; y->parent = x->parent; if(x->parent == NULL) root = y; else{ if(x == x->parent->left) x->parent->left = y; else x->parent->right = y; } y->left = x; x->parent = y; } void right_rotate(deramid *root, deramid *x){ deramid *y = x->left; x->left = y->right; if(y->right != NULL) y->right->parent = x; y->parent = x->parent; if(x->parent == NULL) root = y; else{ if(x == x->parent->right) x->parent->right = y; else x->parent->left = y; } y->right = x; x->parent = y; } void deramid_insert(deramid *root, deramid *z){ deramid *x = root; //Отмечает проходимый путь deramid *y = NULL; //Ссылается на родительский по отношению к x узел //Добавляем элемент по ключу srand(time(NULL)); z->priority = rand() % 701; while(x != NULL){ y = x; if(z->key < x->key) x = x->left; else x = x->right; } z->parent = y; //все поля z кроме key должны быть NULL if(y == NULL) root = z; else{ if(z->key < y->key) y->left = z; else y->right = z; } z->parent = y; //Поднимаемся вверх и выполняем повороты while(y != root){ if(y->priority > y->left->priority) right_rotate(root, y); if(y->priority > y->right->priority) left_rotate(root, y); y = y->parent; } } The program works correctly if you comment out the code where the turns are made. I think I basically did not understand what to do after adding an element, but I don’t see an error. Everything corresponds to the textual description.
And also, are there any comments on the code? How can you improve the definition of node types that are used when building a tree? How to fix the insertion code that crashes if NULL is passed as root? I think the function should correctly insert the element even when the tree is empty (passed NULL), and the inserted element should become the root. There this case is taken into account below, and for some reason it does not work. It is necessary for root to create a node with zero fields, and because of this, an extra element is displayed when traversing.
