red black tree

[자료구조] Red Black Tree 1. 정의 BST를 기반으로하는 트리 형식의 자료구조 검색, 삽입, 삭제의 시간이 $O(logN)$이 소요 됨 2. 규칙 모든 노드는 빨간색이나 검은색 루트는 항상 검은색 새로 추가되는 노드는 빨간색 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 함 어떤 경로에서도 빨간색 노드가 연속으로 2개가 있으면 안됨 모든 빈 노드(null)는 검은색이라고 가정 2.1 균형을 맞추는 방법 이모 노드가 검은색인 경우 회전을 시킴 회전 후에, 부모 노드는 검은색, 두 자식 노드는 빨간색이어야 함 이모 노드가 빨간색인 경우 색깔을 전환 전환 후에, 부모 노드는 빨간색, 두 자식 노드는 검은색이어야 함 3. 구현 public class RedBlackTree..