Red-Black Tree 탐색, 삽입, 삭제 성능: O(log2n) 탐색, 삽입, 삭제에 binary search tree 알고리즘 사용 각 노드는 색상이 할당됨 Properties(Rules) 각 노드는 red 노드거나 black 노드다 루트 노드는 black 노드다 모든 leaf 노드는 black 노드다(NIL 포함) 모든 red 노드는 반드시 2개의 black 노드를 자식으로 갖는다 주어진 어떤 노드에서든 자식 노드까지 모든 경로에서 같은 수의 black 노드를 갖는다 Insertion 새로운 노드는 red 노드 상태로 binary search tree 삽입 uncle 노드를 확인해서 밸런스를 맞춘다 삽입에는 5가지 경우가 있을 수 있다 (N: 삽입하는 노드(red) P: N의 부모 노드, G: ..
