아래 동영상을 시청하기 위해서는 구매하기를 진행 하신후,
본인 소유의 구글(gmail.com) 계정에 로그인 되어 있어야 합니다.
커널연구회 공부모임에 참가하여 월회비를 납부하신 분은 추가적인 구매없이 바로 시청할 수 있습니다.
2024년 07월 06일(토) 공부모임 동영상 (상영시간: 2시간 23분)
동영상 링크: https://youtu.be/Lj-niGwkqkU
동영상 상영시간: 2시간 23분
2024년 07월 13일(토) 공부모임 동영상 (상영시간: 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
동영상 링크: https://youtu.be/vo2XLG1cf38
동영상 상영시간: 2시간 37분
2024년 07월 20일(토) 공부모임 동영상 (상영시간: 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분
2024년 07월 27일(토) 공부모임 동영상 (상영시간: 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분
공부모임 동영상 강의[2024년 07월]