Дерамида строится как обычное бинарное дерево поиска, но каждому элементу дополнительно приписывается поле приоритета, по которому элементы должны удовлетворять свойству пирамиды. При вставке в дерамиду элемент добавляется в дерево поиска, а потом мы поднимаемся вверх и выполняем повороты (не нарушающие свойства дерева), пока приоритет нарушает свойство пирамиды. В чем я ошибся при реализации этого алгоритма? При отладке попадаем в какой-то файл, связанный со временем, а потом выдается сообщение о нарушении прав доступа. Программа крашится.
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;
}
}
Программа работает верно, если закомментировать код, где выполняются повороты. Мне кажется, я принципиально не понял, что надо делать после добавления элемента, но ошибку не вижу. Все соответствует текстовому описанию.
А еще, есть ли какие-то замечания по коду? Как можно улучшить определение типов узлов, которые используются при построении дерева? Как исправить код вставки, который крашится, если в качестве root передается NULL? Думаю, функция должна верно вставлять элемент даже когда дерево пустое (передан NULL), и вставляемый элемент должен стать корнем. Там ниже по коду этот случай и учитывается, то почему-то не работает. Приходится для root создавать узел с нулевыми полями, и из-за этого при обходе выводится лишний элемент.