# Red Black Tree By [Primrose](https://paragraph.com/@primrose) · 2023-03-19 --- Red Black Tree ============== Red Black Tree(이하 RB)는 가장 유명하고 많이 사용되는 ‘균형 이진 탐색 트리’ 구조이다. 이름에서 알 수 있듯이 RB의 노드에는 색깔이 있다. 빨간색과 검은색. 한 번 그림을 보자. ![Introduction to Red-Black Tree - GeeksforGeeks](https://storage.googleapis.com/papyrus_images/94e1bdbf6b6cd86e8da4e5dde7ac7b28057719fc87c0230618fa1999f837762e.png) Introduction to Red-Black Tree - GeeksforGeeks 검은색 노드와 빨간색 노드가 있다. 리프노드를 보면 `NIL`이라고 표기가 되어있는데, Python의 None, C의 NULL과 같다. RB에서는 NIL 노드를 독립된 노드로 표현하고, 해당 노드를 모두 리프 노드라고 부르기로 한다. > Red black Tree에서는 NIL 노드를 리프노드라고 표현. 나머지를 내부 노드라고 표현한다. Red Black Tree의 조건 ------------------ Red Black Tree가 되기 위해서는 다섯 가지 조건을 만족해야 한다. 당연한 얘기지만 ‘이진 탐색트리이면서’ 해당 조건들을 만족해야 한다. 1. 모든 노드는 색이 있어야 한다 (Red / Black) 2. 루트 노드는 Black Node여야 한다. 3. 리프 노드는 Black Node여야 한다. 4. Red Node는 두 개의 자식 노드를 가진다. (중요) > Red Node는 반드시 두 개의 자식 노드가 Black Node여야 한다. 5. 각 노드에서 리프 노드(NIL 노드)로 가는 경로에 있는 Black Node의 수는 항상 같아야 한다. > 위 그림을 예로 들면, 18번 노드에서 NIL 노드로 가는 경로의 Black Node 수는 어디로 가던 항상 같다. 여기까지 왔을 때, 이런 생각이 든다. > 대체 이 짓거리를 왜 해야할까? 이 트리의 장점이 무엇인가? 설명을 하기 위해서 다음과 같이 용어를 정의한다. H(v) = V의 높이 (height) bH(v) = V에서 리프노드로 갈 때 만나는 Black Node의 개수 (black height) * v는 제외하고 리프노드로 갈 때 만나는 Black Node의 개수를 센다. 이제부터 아래 사실을 증명하겠다. 내부 노드는 NIL 노드를 제외한 노드라는 것을 상기하자. > V의 서브트리의 내부 노드 개수 >= 2^bH(v) - 1 증명은 H(v), V의 Height에 대한 귀납법(induction)으로 할 수 있다. ### Base Case : H(v) = 0 H(v)가 가장 작을 때는 0이다. 높이가 0이라는 것은 리프 노드밖에 없다는 것이다. 리프 노드는 NIL node이다. NIL node는 Black이다. 즉, bH(v)는 0이다. > H(v) = 0 일 때, bH(v) = 0이다. v의 서브트리의 내부 노드 개수는 0일 것이다. 2^bH(v)는 2의 0승으로, 1일 것이다. 즉, `0 = 0`으로 위의 공식이 성립한다. ### Hypothesis : H(v) <= k H(v)가 특정한 수 K보다 작거나 같은 높이에 대해서… | v의 서브트리 | >= 2^bH(v) - 1 이라고 가정해보자. 가정이기 때문에 증명할 필요는 없다. ### Induction : H(v) = k + 1일 때 성립함을 증명 해당 부분은 유튜브 강의를 참고하면 좋을 것 같다. 그려보려고 했는데 재능이 모자라서 링크로 대신한다. [![]({{DOMAIN}}/editor/youtube/play.png)](https://www.youtube.com/watch?v=SHdYv41iCmE) --- *Originally published on [Primrose](https://paragraph.com/@primrose/red-black-tree)*