具有完整可重现示例 C 的 AVL 树旋转

Question

我已经在这个函数上卡了 2 天了，所以我想弄明白。下面的代码是我尝试（感谢 user3386109 ）在通用节点上进行 rightRotate 。我认为很接近，但问题是当我运行代码旋转时，但当我实际打印值时，它似乎什么也没发生。

#include <stdio.h>
#include <stdlib.h>

typedef struct tree mynode;  
    struct tree{                    // node struct
    int value;
    int key;
    char color;
    struct tree *left;
    struct tree *right;
};
//allocate memory, set color, key, value and NULL sons 
mynode* red_node_create(int Key, int Value) {
    mynode* parent=(mynode*) calloc(1, sizeof(mynode));
    parent->color= 1;
    parent->value=Value;
    parent->key=Key;
    parent->left=NULL;
    parent->right=NULL;
    return parent;
}

void rightRotate(mynode **parentPtr, mynode *child)
{
    // make sure the arguments are valid for a right rotation
    if (parentPtr == NULL || child == NULL || child->left == NULL)
    {
        printf("Error while rotating right\n");
        return;
    }
    printf("GOing to right rotate\n");
    // save the three node addresses involved in the rotation
    mynode *F = child;
    mynode *D = F->left;
    mynode *E = D->right;

    // perform the rotation
    *parentPtr = D;
    D->right = F;
    F->left = E;
    return;
}

int main(){

mynode* root=red_node_create(0,0);
mynode* F;
F=red_node_create(3,3);
mynode* D=red_node_create(2,2);;
mynode* E=red_node_create(1,1);;
F->left=D;
D->left=E;
root->right= F;
rightRotate(&root,F);
printf(" %d %d %d \n\n",root->right->value,root->right->right->value,
root->right->left->value);
free(F);
free(D);
free(E);
free(root);
return 0;
}

在这个例子中，程序以分段错误结束，显然是 rightRotate 运行s 但它没有完成它的工作。

Answer 1

您显然没有正确的右旋转算法...

而 SEG_FAULT 是由于您的测试树未正确初始化。

#include <stdio.h>
#include <stdlib.h>


struct tree
{               // node struct
  int value;
  int key;
  char color;
  struct tree *left;
  struct tree *right;
};

typedef struct tree mynode;   // move this below declaration for struct tree.
                              // keeping declarations in the right order does
                              // a great deal in making code easier to navigate. 

//allocate memory, set color, key, value and NULL sons 
mynode* red_node_create (int Key, int Value)
{
  mynode *p = (mynode *) calloc (1, sizeof (mynode));
  p->color = 1;
  p->value = Value;
  p->key = Key;
  p->left = NULL;
  p->right = NULL;
  return p;
}

// having a proper way to free memory is very important when dealing 
// with trees and lists.  It would be better if this was not recursive.
// I'll leave this exercise to you.  I'm sure you can find examples on 
// the Net.
void free_node(mynode* p)
{
    if (!p)
        return;
    
    free_node(p->left);
    free_node(p->right);

    free(p);   
}

// Rotation only needs 1 parameter: the root node around which
// rotation occurs.
void rightRotate (mynode ** root)
{
    if (!root || !*root || !(*root)->left)
    {
        printf ("bad arguments in myRightRotate()\n");
        return;
    }

    // take left node, make it parent,  make old parent the right node
    // of new parent, and make right node of old left node the left node
    // of old_parent
    
    // using letters as in graphics on this page: 
    // https://en.wikipedia.org/wiki/Tree_rotation
    
    // these non leaves nodes cannot be NULL
    mynode* Q = *root;
    mynode* P = Q->left;
    
    // the leaf nodes could be NULL.  Only B is needed.
    // but A and C are checked in unit test look-alike below.
    mynode* A = P->left;
    mynode* B = P->right;
    mynode* C = Q->right;
    
    // rotate
    *root = P;
    P->right = Q;
    Q->left = B;
    
#define CHECK_RIGHT_ROTATE   // undef as needed.
#ifdef CHECK_RIGHT_ROTATE

    // make sure the nodes are in place.    
    if (P != *root)
        printf("RR error. root is not P\n");

    if (Q != (*root)->right)
        printf("RR error. root->right is not Q\n");
    
    if (A != P->left)
        printf("RR error. A is not at P->left\n");
    if (B != Q->left)
        printf("RR error. B is not at Q->left\n");
    if (C != Q->right)
        printf("RR error. C is not at Q->right\n");
#endif
}

int main ()
{ 
    // make minimal tree for a proper rotate.  root has both left and right node.
    // - left node has both left and right leaf nodes, values and 1 and 2 
    // - right node is a leaf node. value 3
    mynode *root      = red_node_create (0, 0);
    root->left        = red_node_create (0, 0);
    root->left->left  = red_node_create(1, 1);
    root->left->right = red_node_create(2, 2);
    root->right       = red_node_create(3, 3);

    // before rotate, we should have
    // root->left->left:   leaf, value 1
    // root->left->right:  leaf, value 2
    // root->right: leaf, value 3

    printf ("before:  %d %d %d \n", root->left->left->value, root->left->right->value, root->right->value);

    rightRotate (&root);
    
    // after rotate, we should have
    // root->left:         leaf, value 1
    // root->right->left:  leaf, value 2
    // root->right->right: leaf, value 3
    
    printf ("after:   %d %d %d \n", root->left->value, root->right->left->value, root->right->right->value);
    
    free_node(root);
    
    return 0;
}

你可以运行这里的程序：https://onlinegdb.com/HyQAfPFtP

Answer 2

为了那些没有看到上一个问题的人，这是显示右旋转的图像。目标是用绿色连接替换红色连接来旋转树。

main 中需要更改三处才能使代码正常工作：

E应该接在D
rightRotate的第一个参数是指向F的指针地址。所以是&root->right。
在printf中，root->right是D，root->right->right是F，
root->right->right->left 是 E.

经过这三项更改后，main 变成了这样：

int main(void){

    mynode* root=red_node_create(0,0);
    mynode* F=red_node_create(3,3);
    mynode* D=red_node_create(2,2);
    mynode* E=red_node_create(1,1);

    root->right= F;
    F->left=D;
    D->right=E;
    rightRotate(&root->right,F);

    printf(" %d %d %d \n\n",
           root->right->value,                  // should be D which is 2
           root->right->right->value,           // should be F which is 3
           root->right->right->left->value);    // should be E which is 1

    free(F);
    free(D);
    free(E);
    free(root);
    return 0;
}

程序的输出是 2 3 1。

具有完整可重现示例 C 的 AVL 树旋转

Rotation on AVL tree with full reproducible example C

c

binary-search-tree

avl-tree