Red - Black Tree

red-black 트리는 binary 트리의 일종, 균형 잡힌 tree, 가장 유명하다.

미완성이긴 하지만 red-black tree의 예시

 

---

Red - Black Tree의 조건

1. 모든 노드는 red 혹은 black의 색깔을 가지고 있다.
2. root 노드는 무조건 black이다.
3. leaf(None) 노드는 black이다.
4. red 노드의 child는 모두 black이다. black노드의 자식 색깔은 상관이 없다. 
5. 각 노드에서 leaf node 까지 갈 때의 black 노드 수가 항상 같아야 한다. 

---

Red - Black Tree의 사실 및 증명

• h(v) = v의 높이(height)
• bh(v) = v에서 leaf node까지 v를 제외한 black노드의 개수

사실 1. v의 서브 트리의 내부 노드 수 >= 2^bh(v) - 1

사실 1 - 귀납적으로 증명

 

 

사실 2.  h = O(logn)

사실 2 증명

• red - black tree의 조건에 따라 black노드의 수는 전체 노드 수의 절반 이상이다.

---

Red - Black Tree의 삽입을 할 때

 

출처: 한국외대 신찬수 교수님 유튜브 강의 - Chan Su Shin 

 

1. BST의 insert 연산을 호출해 새로운 노드 x 삽입

2. x.color = red

3. 여러 가지 경우를 고려하여야 한다

• x 가 트리의 root인 경우 --> x = t.root
• x.parent.color == black  --> do nothing
• x.parent.color == red 

        - x.uncle.color == red (그림 1번)

           --> x.grand.color == black 인것을 grand를 red로 변경, parent, uncle을 black 으로 변경

                1. 자식 색이 중요하지 않게 된다.

                2. red - black tree의 조건 5번 또한 만족

      

         - x.uncle.color == black

           --> 경우 1: x, parent, grand: linear. 그림 2번 

           --> 경우 2: x, parent, grand: triangle. 그림 3번 

 

---

출처: https://www.youtube.com/channel/UCJ4SXKMLQucqaxt4A6PonwQ