Балансировка высоты дерева AVL / ошибка коэффициента балансировки

Question

Хорошо, здесь много кода, но я подумал, что лучше всего, если что-то не сразу проявится в моей логике.

Моя проблема начинается с высоты и моего расчетного коэффициента балансировки. Я просмотрел бесчисленное количество алгоритмов дерева AVL и проделал большую черновую работу на бумаге, чтобы попытаться найти лучший способ решения проблемы балансировки этого зверя дерева. Вот что я получил:

typedef struct node {
    char* key;
    struct node *left;
    struct node *right;
    int height;
    int frequency;
}node;

int max(int a, int b)
{
    if(a > b)
    {
        return a;
    }
    else
        return b;
}

// A utility function to get height of the tree
int height(node* N)
{
    if(N==NULL)
        return -1;

    return N->height;
}

// A utility function to get maximum of two integers

int avlHeight(node* N) {
    if(N == NULL)
        return -1;
    else
        return max(height(N->left), height(N->right))+1;
}

node *rightRotate(node *y) //preform a right AVL rotation
{
    node *x = y->left;
    node *T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;

    // Return new root
    return x;
}

// A utility function to left rotate subtree rooted with x
// See the diagram given above.
node *leftRotate(node *x) //perform a left AVL rotation
{
    node *y = x->right;
    node *T2 = y->left;
    // Perform rotation

    y->left = x;
    x->right = T2;

    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;

    // Return new root
    return y;
}


// Get Balance factor of node N
int getBalance(node *N)//get the balance factor
{
    if (N == NULL)
        return -1;
    return height(N->left) - height(N->right);
}

node* insert(node* node, char* key)//function to insert new nodes to the tree
{
    if (node == NULL)
        return (newNode(key));
   // printf("%s",key);
    if(strcmp(node->key, key)==0)
    {
        node->frequency = node->frequency+1;
        return node;
    }

    if (strcmp(key, node->key) < 0)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    /* 2. Update height of this ancestor node */
    node->height = max(height(node->left), height(node->right)) + 1;

    /* 3. Get the balance factor of this ancestor node to check whether
     this node became unbalanced */
    int balance = getBalance(node);
    printf("%d\n",balance);
    // If this node becomes unbalanced, then there are 4 cases
    // Left Left Case

    if (balance > 1 && strcmp(key, node->left->key)<0) {
        return rightRotate(node);
    }

    // Right Right Case
    if (balance < -1 && strcmp(key, node->right->key)>0)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && strcmp(key, node->left->key)>0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && strcmp(key, node->right->key)<0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    /* return the (unchanged) node pointer */
    return node;
}

I̶ ̶d̶o̶ ̶n̶o̶t̶ ̶g̶e̶t̶ ̶a̶n̶y̶ ̶s̶e̶g̶-̶f̶a̶u̶l̶t̶s̶,̶ ̶̶̶̶̶̶̶̶̶̶̶̶̶,̶ ̶̶̶̶̶̶̶̶̶̶̶̶̶̶̶̶̶̶̶̶̶ tree̶ tree tree tree tree tree 44 tree 44 44 44 44 44 44 44 44̶ 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44̶̶̶̶ tree 44 44 44 44 44 44 44 44 44 44 44̶ 44 44 44 tree tree 44 44 44̶̶̶̶̶̶ ̶̶̶̶̶, Единственное, что не правильно с моим деревом, это то, что частота отключена на 1-3 элемента для любого данного узла, а высоты не такие, какими они должны быть для всех элементов.

Я был совершенно уверен, что когда я отлаживал, это было связано с моим алгоритмом балансировки, потому что для одного мои высоты были полностью выключены (я считаю, что они достигли 7), и около 70% моих узлов имели правильное количество импульсов (частоту),

Мой большой вопрос: что не так с моей логикой балансировки и / или логикой вращения? Весь мой код неверен, или я по крайней мере на правильном пути?

** после обновления кода по какой-то богом заброшенной причине, когда я вынимаю узел, на котором у меня есть segfault, вся программа работает, но все равно выдает мне неправильные частоты:/

Таким образом, буквально 1 элемент / узел делает это segfault, но все же это неправильно...

пример ввода->

wrn69 flr830 flr662 flr830 flr830
flr231 flr2166 flr1854 wrn69 wrn69

flr231 flr2166
wrn69
flr830