레드 블랙 트리를 이해하는 데에 꽤나 오랜 시간이 걸렸다.

왜냐하면 과제 수행에 마음이 급해서 전반적인 이해의 과정을 가지지 않고 곧장 과제에서 요하는 rotate 함수를 완성하는 것에만 급급했기 때문이다. 앞으로는 돌아가는 것이 가장 가까운 길이라는 것을 명심하고 꾸벅꾸벅 걸어나가야 할 것 같다. 이번 글은 글 대신 이해하는 과정을 작성한 필기본으로 대체한다.

• 레드-블랙 트리는 2-3-4 트리를 표준적인 이진 트리로 표현하기 위해 노드/링크에 색상을 부여함.

  • 3-노드와 4-노드를 표현하기 위해 레드 노드로 이루어진 이진트리로 표현.

  • 레드/블랙 여부를 표현하기 위해 1비트 추가로 필요.

    

• 성질

  • 루트나 단말 노드는 모두 블랙
  • 루트에서 단말 노드까지의 경로 상에 2개의 연속된 노드 포함되지 않음
  • 루트에서 각 단말 노드까지의 경로에 있는 블랙 노드의 개수는 같음

• 분할 과정

  • 부모가 2-노드인 경우

    

  • 부모가 3-노드인 경우

    

  • 회전하기

    • 단일회전

      

    • 이중회전

      

  • 삽입을 통한 트리 구축 과정

    • 2,1,8,9,7,3,6,4,5를 삽입하는 과정

    • 3 삽입

      

    • 6 삽입