레드 블랙트리(The red black tree): 규칙, 회전, 삽입

루트 노드에서 leaf 노드로 가는 경로를 보았을 때 red black 트리는 한 경로가 다른 경로보다 2배 이상 길지 않다. 그래서 대체적으로 균형잡혀 있다.각각의 노드는 color, key, left, right, p 속성을 가지고 있다.red black 트리는 아래 규칙을 만족하는 이진 탐색 트리이다.규칙모든 노드는 색을 가진다. (red 또는 black)루트 노드는 black모든 leaf 노드는 NIL, blackred 노드는 red 자식 노드를 가질 수 없다.(2개의 black 자식을 가져야 한다.)각 노드에서 leaf 노드로 가는 경로들은 같은 수의 black 노드를 가지고 있어야 한다.회전Left-Rotate 왼쪽 회전y의 왼쪽 서브트리는 x의 오른쪽 서브 트리가 된다.(바꾼다라는 표현이 헷..