목록RBTree (1)

말감로그

Red-BlackTree

Red-Black 트리 - 이진 탐색 트리(BST)의 한 종류 - 스스로 균형 잡는 트리 - BST의 worst case의 단점을 개선( O(N) -> O(logN) - 모든 노드는 red or black RBTree 특성 #1 모든 노드는 Red or Black #2 루트 노드는 Black #3 모든 nil(leaf)는 Black #4 Red의 자녀들은 black -> red가 연속적으로 존재할 수 없다 #5 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외) nil노드란? 존재하지 않음을 의미하는 노드 자녀가 없을 때 자녀를 nil노드로 표기 값이 있는 노드와 동등하게 취급 RB 트리에서 leaf 노드(자식 없는 노드)는 nil노드 노드 x의 b..
이론/자료구조 2024. 2. 3. 00:54
이전 Prev 1 Next 다음