0

好吧，这里有很多代码，但我认为最好以防万一某些东西在我的逻辑中没有立即显现出来。

我的问题从高度和我计算的平衡因子开始。我查阅了无数的 AVL-tree 算法，并在纸上做了很多粗略的工作，试图找出解决这棵树的野兽平衡方面的最佳方法。这是我必须要做的：

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̶e̶n̶o̶t̶ . 我的树唯一不正确的是任何给定节点的频率偏离了 1-3 个元素，并且高度不是所有元素的应有高度。

我很确定在调试时它与我的平衡算法有关，因为一方面我的高度完全偏离（我相信高达 7）并且我大约 70% 的节点具有正确的计数（频率） .

我的大问题：我的平衡逻辑和/或旋转逻辑有什么问题？我的整个代码是错误的，还是我至少在正确的轨道上？

**当我取出我段错误所在的节点时，由于某些上帝遗弃的原因更新了代码后，整个程序都可以工作，但仍然给我错误的频率：/

所以从字面上看，1个元素/节点会造成这个段错误，但它仍然是错误的......

示例输入->

wrn69 flr830 flr662 flr830 flr830
flr231 flr2166 flr1854 wrn69 wrn69

flr231 flr2166
wrn69
flr830
4

0 回答 0