자료구조 avl트리 구현중인데 책에 있는 알고리즘대로 구현했더니 안되네,,

회전하고 나서 temp의 부모가 부모노드의 왼쪽인지 오른쪽인지 구현부분 어캐해야돼?


그거 안넣어서 회전은 하는데 계속 출력할때 회전된 내용이 안나오고 이런모양만 나오는데,,

(41의 부모도 35, 11의 부모도 35, 70의 부모도 35이지만 35의 왼쪽은 11, 오른쪽은 41이 출력됨)

 나는

이런모양얻고싶거든 (31,11,41,94,70순으로 avl트리 삽입)

회전하기전에 부모노드의 왼쪽인지 오른쪽인지를 저장하고, 회전하고 회전하고나서의 서브트리 루트의 부모노드를 거기에 가르키게 하면 되나? 근데 그러면 왼쪽인지 오른쪽인지 어캐 알아?.. 


 //LL삽입시 오른쪽으로 회전

struct Node* right_rotate(struct Node* node)

{

    struct Node* temp = node->left;


    node->left = temp->right;

    if (temp->right != NULL)

        temp->right->parent = node;

    temp->right = node;

    temp->parent = node->parent;

    node->parent = temp;

    return temp;

}

//RL삽입시 RL회전

struct Node* right_left_rotate(struct Node* node)

{

    struct Node* temp = node->right;

    node->right = right_rotate(temp);

    return left_rotate(node);

}