BST2 [알고리즘] RB Tree삭제 동작 원리 #2 한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다. 개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다. 하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu #1 레드 블랙 트리 삭제 방식 0. 삭제 전 RB 트리 속성 만족한 상태 1. 삭제 방식은 일반적인 BST와 동일 2. 삭제 후 RB 트리 속성 위반 여부 확인 - 어떻게 확인할 수 있는가 3. RB트리 속성을 위반했다면 재조정 4. RB 트리 속성을 다시 만족 RB.. 2022. 11. 26. [알고리즘] RB Tree개념과 삽입 동작 원리 #1 한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다. 개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다. 하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu #1 레드블랙 트리 기본 개념과 특징 1. 레드블랙 트리 개념 1. 이진 탐색 트리(BST)의 한 종류 2. 스스로 균형 잡는 트리 3. BST의 worst case의 단점을 개선 : worst case = 한 방향으로 편향된 이진탐색 트리 > O(N) 4. 모든 노드.. 2022. 11. 26. 이전 1 다음
