Вращения AVL в C

Когда происходит вращение, в моем коде работает только первое вращение, я не мог понять, почему я думаю, что функции вращения возвращают неправильные узлы? может быть. Ниже мой узел и древовидная структура

#define ll unsigned long
typedef struct NODE_s *NODE; //Node structure
typedef struct NODE_s{
    NODE right,left;
    ll key;
    int height;
    void *data;
} NODE_t[1];

typedef struct AVL_s *AVL; //Tree structure
typedef struct AVL_s{
    NODE root;
} AVL_t[1];

Инициализировать функции

AVL AVL_init(){
    AVL t = (AVL)malloc(sizeof(AVL_t));
    t->root = NULL;
    return t;
}
NODE node_init(ll init_key){
    NODE node = (NODE)malloc(sizeof(NODE_t));
    node->left = NULL;
    node->right = NULL;
    node->key = init_key;
    node->height = 1;
    node->data = NULL;
    return node;
}

Функции вращения

NODE rightRotate(NODE node){

    NODE child  = node->left;
    NODE childR = child->right;

    child->right = node;
    node->left = childR;


        node->height = max(height(node->left), height(node->right))+1;
        child->height = max(height(child->left), height(child->right))+1;

    return child;
}
NODE leftRotate(NODE node)
{
    NODE child  = node->right;
    NODE childL = child->left;

    child->left = node;
    node->right = childL;


        node->height = max(height(node->left), height(node->right))+1;
        child->height = max(height(child->left), height(child->right))+1;

        return child;
}

Вставка рекурсивно Я думаю, что нужно использовать две функции, отправляющие дерево из основного, а затем корень дерева в функции вставки.

NODE insert_rec(NODE node,ll rec_key){
    if(rec_key < node->key){
        if(node->left == NULL)
            node->left = node_init(rec_key);
        else
            insert_rec(node->left, rec_key);
    }else if(rec_key > node->key){
        if(node->right == NULL)
            node->right = node_init(rec_key);
        else
            insert_rec(node->right, rec_key);
    }else
        printf("Duplicate %lu Data\n",rec_key);

    //If I delete from here to end of functions, it is clearly recursive BST insert and works successfully

    node->height = 1 + max(height(node->left),height(node->right));
    int balanceFactor = balance(node);

    if (balanceFactor > 1 && rec_key < node->left->key) //leftleft
       node = rightRotate(node);   //return rightRotate(node) also working

    if (balanceFactor < -1 && rec_key > node->right->key) //rightright
        node = leftRotate(node);   //return leftRotate(node) also working

    if (balanceFactor > 1 && rec_key > node->left->key) //leftright
    {
        node->left =  leftRotate(node->left);
        node = rightRotate(node); 
    }
    if (balanceFactor < -1 && rec_key < node->right->key) //rightright
    {
        node->right = rightRotate(node->right);
        node = leftRotate(node);
    }
   return node;
}
void insert(AVL tree,ll key){
    if(key == -1){
        printf("Invalid data %lu\n",key);
    }
    else if(tree->root == NULL){
        tree->root = node_init(key);
    }
    else{
       tree->root = insert_rec(tree->root,key);
    }
}

int main() {
    AVL tree = AVL_init();
    insert(tree,111);
    }

Это мой исходный код, я не могу понять, чего я не вижу. Если я заменю его обычным BST, он работает, но когда происходит вращение, узлы появляются где-то


c recursive-datastructures avl-tree
person murki    schedule 06.01.2021    source источник
comment
Существует [было] куча действительно хороших руководств (с исходным кодом) для различных вещей (включая деревья AVL) на сайте everlyconfuzzled.com. Но они больше не доступны. Но он заархивирован здесь: http://web.archive.org/web/20180225130248/http://www.eternallyconfuzzled.com/jsw_home.aspx Щелкните ссылку «Библиотеки».   -  person Craig Estey    schedule 07.01.2021

Ответы (1)


arrow_upward
1
arrow_downward

Я решил это. Функция insert() отправляется в мусор и помещается в insert_rec(). Это просто корневая проверка, если условия root = null.

Затем основная функция заменяется так,

int main() {
    AVL tree = AVL_init();
    NODE node = tree->root;
    insert_rec(node,111);
}

Наконец, в случаях с коэффициентом баланса мне просто нужно вернуть функции

return leftRotate(node); //instead of node = leftRotate(node); 

return rightRotate(node); //instead of node = rightRotate(node);

Эта перспектива упростила работу с возвращаемыми значениями из функций.

person murki    schedule 08.01.2021
comment
Хорошая работа, отвечая на свой вопрос. Я предлагаю вам принять свой собственный ответ (нажмите на галочку под стрелками «за» / «против» слева от вашего ответа), чтобы получить за него очки репутации. - person Bob Jarvis - Reinstate Monica; 08.01.2021
comment
О, забыл, спасибо, что напомнил. - person murki; 09.01.2021