rbtree insert

#include "rbtree.h"

//노드의 오른쪽 자식의 node의 부모가 된다.

//node의 오른쪽 자식노드가 node을 왼쪽 자식노드로 하겠다.

static void __rb_rotate_left(struct rb_node *node, 

struct rb_root * root)

{

struct rb_node *right = node->rb_right;

struct rb_node *parent = rb_parent(node);

if((node->rb_right = right->rb_left))

rb_set_parent(right->rb_left, node);

right->rb_left = node;

rb_set_parent(right, parent);

if(parent)

{

if(node == parent->rb_left)

parent->rb_left = right;

else

parent->rb_right = right;

}else

root->rb_node = right;

rb_set_parent(node, right);

}

//노드의 왼쪽자식이 node의 부모가 된다.

//노드의 왼쪽자식노드가 노드를 오른쪽자식노드로 하겠다.

static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)

{

struct rb_node *left = node->rb_left;

struct rb_node *parent = rb_parent(node);

//노드와 왼쪽자식노드 사이에 노드가 존재하면

//노드의 왼쪽자식은 사이에 있는 노드로 정한다.

//사이에 있는 노드의 부모는 노드가 된다.

if((node->rb_left = left->rb_right))

rb_set_parent(left->rb_right, node);

//왼쪽자식의 오른쪽자식으로 node를 임명한다.

left->rb_right = node;

//left의 부모는 이제 노드의 parent이다.

rb_set_parent(left, parent);

//부모가 존재하면 NULL이아니면

if(parent)

{

//부모의 오른쪽 자식이랑 노드가 같다면

//부모의 오른쪽 자식을 left로 정한다.

if(node == parent->rb_right)

parent->rb_right = left;

else //그렇지 않다면 부모의 왼쪽자식을  left로 정한다.

parent->rb_left = left;

}

else //부모가 존재하지 않는다는 것은 left가 root라는 것임.

root->rb_node = left;

//node의 부모는 이제 left이다.

rb_set_parent(node, left);

}

void rb_insert_color(strucr rb_node *node, struct rb_root *root)

{

struct rb_node *parent, *gparent;

//노드의 부모가 빨간색이라면 문제가 발생! 회전 ㄱㄱ

while((parent = rb_parent(node)) && rb_is_red(parent))

{

gparent = rb_parent(parent);

//부모노드가 할아버지 노드의 왼쪽자식일 경우

if(parent == gparent->rb_left)

{

{

//삼촌이 빨간색인 경우

//색깔만 변경

register struct rb_node *uncle = gparent->rb_right;

if(uncle & rb_is_red(uncle))

{

rb_set_black(uncle);

rb_set_black(parent);

rb_set_red(gparent);

node = gparent;

continue;

}

}

//삼촌이 검정색이면서, 내가 오른쪽 자식일 때 

//parnet의 오른쪽 자식노드가 parent을 자식노드로 하겠다.

//부모랑 현재노드랑 자리 바꿈

if(parent->rb_right ==node)

{

register struct rb_node *tmp;

__rb_rotate_left(parent, root);

tmp = parent;

parent = node;

node = tmp;

}

rb_set_black(parent);

rb_set_red(gparent);

__rb_rotate_right(gparent, root);

}else {

//부모노드가 할아버지 노드의 오른쪽 자식일 경우

{

//삼촌이 빨간색일 경우

register struct rb_node *uncle = gparent->rb_left;

if(uncle && rb_is_red(uncle))

{

rb_set_black(uncle);

rb_set_black(parent);

rb_set_red(gparent);

node = gparent;

continue;

}

}

//삼촌이 검정색이면서 내가 왼쪽 자식인경우,

//parent의 왼쪽자식이 오른쪽 자식으로 parent를 만듬

if(parent->rb_left == node)

{

register struct rb_node *tmp;

__rb_rotate_right(parent, root);

tmp = parent;

parent = node;

node = tmp;

}

__rb_rotate_left(gparent, root);

rb_set_black(parent);

 rb_set_red(gparent);

}

}

//루트노드는 반드시 검정이어야 한다.

rb_set_black(root->rb_node);

}

그러니깐, parent는 지 자식의 왼쪽노드가 되는거임. 왼쪽노드가 된다고 해서 rotate_left라고 지었나(?)

그러니깐, parent는 지 자식의 오른쪽 자식이 되는거임