본문 바로가기

정글37

WIL (RB트리 vs AVL트리) RB트리는 AVL과 다르게 색상이라는 속성과 그 속성을 이용하여 트리의 레벨 균형을 맞추는 BST트리의 한 종류이다. BST트리중 균형을 잡는 트리는 대표적으로 2개가 있다. RB트리와 AVL트리이다. 두 트리의 차이는 아래와 같다. RB트리 vs AVL RB 트리 AVL 트리 이진 탐색 트리인가? yes yes 삽입/삭제/검색 시간 worst case = O(log n) worst case = O(log n) 삽입 /삭제 AVL 보다 빠름 RB보다 느림 검색 AVL 보다 느림 RB보다 빠름 balance 방식 black - depth balance-factor 응용사례 커널,자바 Tree map,c++ map dictionary,검색용도 AVL 사진 출처: https://en.wikipedia.org/.. 2023. 5. 11.
TIL(18일차) RB트리 삭제 레드 블랙 트리의 삭제는 글만 봐서는 굉장히 어렵기 때문에 유튜버 쉬운 코드 님의 영상을 보고 공부를 하였다. 다른 자료를 찾아봐도 괜찮을 것 같다. successor를 어디다가 두냐에 따라 트리의 모양이 상이 하므로 그려보면서 연습을 하는 것이 나을 것 같다. 먼저 그전에 알아야할 RB트리의 5가지 속성 1. 모든 노드는 red 혹은 black 이다. 2. 루트 노드는 black 3. 모든 nil노드는 black 4. red의 자녀들은 black이어야한다.(red가 두번 나올 수 없다) 5. 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black 수는 같다(자기 자신은 카운트에서 제외) 레드 블랙트리의 삭제 0. 삭제 전 RB트리 속성 만족한 상태확인 1. 삭제 방식은 일반적인 BST와 동일 2.. 2023. 5. 10.
TIL(17일차) 레드블랙트리 삽입 https://www.youtube.com/watch?v=2MdsebfJOyM&t=30s Red-black Tree의 대해서 이 자료 저자료 보다가 시각적으로나 영상으로나 쉬운코드님의 설명이 가장 잘 이해되어서 위 영상을 기반으로 공부를 하게 되었다. Red-Black Tree Red-black Tree은 이진 탐색 트리의 한 종류이다. 스스로 균형을 잡는 트리이다. 균형트리는 AVL 트리를 먼저 접하게 되어 대표적인 자료구조는 AVL이구나 라고 생각했다. BST(binary search tree)의 worst case O(n)이므로 이것을 O(log n)으로 개선한 것이 AVL트리라고만 생각하고 있었다. 근데 Red - black Tree는 AVL의 밸런싱 과정이 시간이 오래 걸린다는 단점을 가지고 있.. 2023. 5. 8.
TIL(16일차) 포인터 디테일 RB 트리 관련 주차인데 기존의 배웠던 포인터에 대해서 다시 보았다. 막상 배웠었으니까 쉽겠지~ 라고 생각했다가 큰 코 다쳐버렸다...ㅋㅋㅋ 개념은 알고 있다고 해도 디테일을 살리는게 굉장히 어렵다는 것을 깨달았다. 포인터의 세계는 너무 방대 한것 같다.... #include #include int main() { int i = 1; int *pint = &i; printf("*pint\n"); printf("pint = %p\n",pint); printf("i = %d\n",i); printf("*pint = %d\n\n",*pint); # 주소의 값을 올려준다. *(pint++); printf("*(pint)++\n"); printf("pint = %p\n",pint); printf("i = %d\n.. 2023. 5. 7.

티스토리툴바