CafeM0ca

정의 레드블랙트리는 다음 조건을 만족하는 이진탐색트리다. 조건 각 노드는 red 혹은 black이다. 루트 노드는 black이다. 모든 Leaf 노드(NIL 노드)는 black 노드다.(NIL노드: 트리의 각 leaf들이 공통적으로 가리키는 추상적인 노드. root의 부모도 NIL 노드) red 노드의 자식들은 전부 black이다.(red 노드가 연속되어 등장하지 않는다) 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 존재한다. 레드블랙트리의 높이 루트노드로부터 NIL 노드를 만날 때까지의 높이를 측정한다. 노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 정점의 개수이다. 노드 x의 블랙-높이 bh(x)는 x로부터 리..