공부모임 동영상 강의 (red-Black Tree)

아래 동영상을 시청하기 위해서는 구매하기를 진행 하신후,

본인 소유의 구글(gmail.com) 계정에 로그인 되어 있어야 합니다.

커널연구회 공부모임에 참가하여 월회비를 납부하신 분은 추가적인 구매없이 바로 시청할 수 있습니다.

커널 공부모임 동영상1 (hash list 사용 설명, 상영시간: 2시간 23분)

• hash list 소스 분석 및 실행(실습)
• qt: train_hlist_test01/test02/test03() 함수 소스 설명
• hlist_add_head(n, h) 소스 실습
• hlist_add_before(n, next) 소스 실습
• hlist_add_behind(n, prev) 소스 실습
• hlist_for_each(pos, head) 매크로 소스 설명
• hash_for_each_possible() 매크로 소스 설명

동영상 링크: https://youtu.be/Lj-niGwkqkU

동영상 상영시간: 2시간 23분

커널 공부모임 동영상2 (red-Black Tree 구조체 설명, 상영시간: 2시간 37분)

include/linux/rbtree_types.h

Red-Black 트리 구조체 설명.

Left < Root < Right (키)값 순으로 red-Black 속성값을 만족하도록 균형 잡히게 연결:

            g(5)

          /       \

     P(4)        U(6)

    /

n(3)

lib/rbtree.c

Red-Black 트리 속성 설명: https://en.wikipedia.org/wiki/Rbtree

• 1) A node is either red or black
• 2) The root is black
• 3) All leaves (NULL) are black
• 4) Both children of every red node are black
• 5) Every simple path from root to leaves contains the same number of black nodes.

동영상 링크: https://youtu.be/vo2XLG1cf38

동영상 상영시간: 2시간 37분

커널 공부모임 동영상3 (red-Black Tree 노드 삽입 설명, 상영시간: 2시간 55분)

Red-Black Tree 소스 설명:

소스 파일 위치:

✔ include/linux/rbtree_types.h

✔ include/linux/rbtree.h

✔ lib/rbtree.c

✔ lb/rbtree_test.c

rb_node 구조체를 사용한 left-root-right 포인터 연결 이해:

struct rb_node {

unsigned long __rb_parent_color;   //*parent | 1bit(1:B, 0:R)

struct rb_node *rb_right;

struct rb_node *rb_left;

}

rb_insert() 함수 소스 분석:

qt: train_rb_test01():

rb_test_insert(node, root)

while(*newp); //find leaf node

rb_link_node(node, parent)

node->__rb_parent_color = parent;

rb_insert_color(node, root)

__rb_insert(node, root)

//left-right rotate

G(10)

\

p(20)

\

n(30)

/* Case 3 - left rotate at gparent */

P(20)

/       \

g(10)          n(30)

동영상 링크: https://youtu.be/joXmHZm_wwY

동영상 상영시간: 2시간 55분

커널 공부모임 동영상4 (red-Black Tree 노드 삭제 설명, 상영시간: 2시간 43분)

Red-Black 노드 추가:

rb_insert():

    rb_link_node()        //추가 위치 결정

    rb_insert_color()    //좌우 균형 조정(rotate)

        __rb_insert()

Red-Black 노드 검색:

rb_search():

    while()

        left --> root --> right

Red-Black 노드 삭제:

rb_erase():

    __rb_erase_augmented()    //삭제 위치 결정

    ____rb_erase_color()    //좌우 균형 조정(rotate)

좌우 균형 조정(rotate)

동영상 링크: https://youtu.be/FuHeLjsQGbc

동영상 상영시간: 2시간 43분