레드블랙트리

[자료구조] 트리, 레드블랙 트리 (Red-Black-Tree)

Red-Black Tree Binary Search Tree를 기반으로 하는 자료구조. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어. 연산 삽입 insert : O(lon N) 조회 search : O(log N) 삭제 delete : O(log N) 정의 레드 블랙 트리는 다음의 성질들을 만족하는 BST(이진 탐색 트리) 이다. 모든 노드는 Red(빨강) or Black(검정) 의 색을 갖는다. 루트 노드는 검정색이다. 모든 리프 노드들은 검정색이다. 레드 노드의 자식은 모두 검정색이다 모든 리프 노드에서 Black Depth는 같다. 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 각 노드에 대해서 노드로부터 descendan..