helloahram

RB Tree 기본 개념 과 RB Tree 구현하기 #1 에 이어서, rbtree.c 구현 #25. 왼쪽으로 회전시키기 void delete_rbtree(rbtree *t)RB Tree 에 삽입/ 삭제를 수행할 때 회전을 통해 트리의 균형을 유지하는 경우가 많기 때문에왼쪽으로, 오른쪽으로 회전하는 함수를 별도로 구성했다 왼쪽으로 회전하는 경우는 루트의 오른쪽 자식에 새로운 오른쪽 자식이 생기는 상황인데 기존의 오른쪽 자식을 루트로 올리고 루트는 왼쪽 자식으로 내려 보내면서 균형을 맞춘다 그 과정에서 서로를 잘 연결시켜야 하는데 이 부분이 많이 헷갈려서 그림을 그리며 개념을 이해했다 // FixUp 시 좌회전void rotate_left(rbtree *t, node_t *node){ // 1. rig..

Red-Black Tree 기본 개념 을 숙지했으니 이제 구현을 해봤다 rbtree.h 분석1. enum color_t// RBTREE 색을 열거형으로 정의하고, color_t 라는 이름으로 새로운 자료형 정의// Red, Black 를 각각 RBTREE_xxx 으로 정의하여 color_t nodeColor; 로 사용 가능// ex) nodeColor = RBTREE_RED; or nodeColor = RBTREE_BLACK;typedef enum{ RBTREE_RED, RBTREE_BLACK} color_t;2. int key_t// RBTREE 의 키 값을 나타내는 정수형 변수를 key_t 라는 이름으로 정의typedef int key_t;3. struct node_tstruct rbtree 와 ..

Week05 기간 2024.10.11 FRI - 2024.10.17 THU 조원 ㅅㅎ ㅈㅎ Data Structure 구현 Red-Black TreeRBTREE 기본 개념 https://helloahram.tistory.com/89RBTREE 함수 구현 #1 https://helloahram.tistory.com/92RBTREE 함수 구현 #2 https://helloahram.tistory.com/101No.To-do-List구현 여부 1Gitgub Repository 생성O2new_rbtreeO3delete_rbtree 4rbtree_insertO5rbtree_findO6rbtree_minO7rbtree_maxO8rbtree_erase 9rbtree_to_array 테스트 케이스No.Test Case..

내용이 다 이해가 가지 않지만, 일단 내용을 정리해 봤다 1부 https://www.youtube.com/watch?v=2MdsebfJOyM2부 https://youtu.be/6drLl777k-E?si=SwbAbKtcyby9zjji + 개인적으로 저 유튜브 강의는 말도 너무 빠르고Extra Black, Double Black 같은 이상한 개념들이 나오면서 정리가 안 됐다그런 와중에 ㅁㄱ님이 잘 정리해 주신 내용을 공유해 주셔서 내용을 재정리했다 ㅁㄱ님의 RBtree 벨로그 Red-Black Tree이진 탐색 트리 BST 의 한 종류,BST Worst Case 의 단점을 개선하여 스스로 균형 (Balancing) 잡는 트리 + BST Worst Case - 구조가 한쪽으로 편향되는 경우, O(N)/ RB ..