이번에 데이터 스트럭쳐 과목 때문에, 레드 블랙 트리를 만들어 내야 하는데
씨언어도 제대로 배운적도 없는데 어떻게 어떻게 해서 여기까지 진행했는데, 로테이션을 어떻게 해야할지 막막해..
정확히는.. 로테이션을 하면 PRINT가 안되는 상황이 발생하고 있어..
포인터 때문에 그런거 같은데.. 형들 제발 도와주세요 ㅠ
void insertElement(Node ** root, int newElement)
{
Node *nparent;
Node *uncle;
Node *gparent;
Node *temp;
Node *temp2;
Node *temp3;
Node *temp4;
if (root == NULL)
{
printf("Error no root pointer\\n");
return;
}
nparent = NULL;
uncle = NULL;
gparent = NULL;
temp = NULL;
temp2 = NULL;
temp3 = NULL;
temp4 = NULL;
while (*root != NULL)
{
// Insert to the left of this node
if (newElement < (*root)->element)
{
nparent = (*root);
root = &((*root)->left);
}
// Insert to the right of this node
else if (newElement > (*root)->element)
{
nparent = (*root);
root = &((*root)->right);
}
}
// This pointer is NULL, so create a new node and add it here
*root = newNodeElt(newElement);// BINARY 트리
printf("%d\\n",&(*root));
printf("%d\\n",&((*root)->left));
printf("%d\\n",&((*root)->left->left));
printf("%d\\n",&((*root)->right));
printf("%d\\n",&((*root)->right->right));
if(nparent != NULL) (*root)->parent = nparent;//parent 노드의 성립
if(nparent == NULL)
{
(*root)->color = BLACK;//루트 노드의 색 정의
(*root)->parent = NULL;
}
else
{
if((*root)->parent->parent != NULL)
{
gparent = (*root)->parent->parent;
if(gparent->left == (*root)->parent && gparent->right != NULL) uncle = gparent->right;
if(gparent->right == (*root)->parent && gparent->left != NULL) uncle = gparent->left;
}//uncle과 gparent의 선언
if((*root)->parent->color == BLACK)
{
printf("**루트의 값 %d",**root);
printf("&(*root): %d\\n",*(&(*root)));
printf("(*root): %d\\n",(*root));
printf("root: %d\\n",root);
printf("*root: %d\\n",*root);
printTreeInOrder(root);
//이미 balance tree
}
else if((*root)->parent->color == RED)
{
if(uncle != NULL && uncle->color == RED)
{
(*root)->parent->color = BLACK;
uncle->color = BLACK;
gparent->color = RED;
if(gparent->parent == NULL) gparent->color = BLACK;
}//case3
else if(gparent != NULL)//parent red, uncle은 없거나 BLACK case3~5 //parent == red
{
if(((*root) == (*root)->parent->right) && ((*root)->parent == gparent->left))
{
// left rotation 필요
}
else if(((*root) == (*root)->parent->left) && ((*root)->parent == gparent->right))
{
// right rotation 필요
}
(*root)->parent->color = BLACK;
gparent->color = RED;
if((*root) == (*root)->parent->left && (*root)->parent == gparent->left)
{
//right lotation 필요
}
else
{
//left rotation 필요
}
}
}//parent == red end
}
}
댓글 영역
획득법
① NFT 발행
작성한 게시물을 NFT로 발행하면 일주일 동안 사용할 수 있습니다. (최초 1회)
② NFT 구매
다른 이용자의 NFT를 구매하면 한 달 동안 사용할 수 있습니다. (구매 시마다 갱신)
사용법
디시콘에서지갑연결시 바로 사용 가능합니다.