먼저 레드-블랙 트리가 탄생하게 된 이유는 이진탐색트리에서 시작합니다.
데이터를 이진탐색트리로 구성해 놓는 이유는 데이터의 값을 기준으로 빠르게 원하는 값을 찾
거나 추가, 삭제하기 위해서 입니다. 이렇게 데이터를 구성해 놓으면 최선의 경우 O(logN)의
효율로 데이터를 검색, 추가, 삭제 가능하다군요.
그러나 이진탐색트리에서 노드를 추가해나가다 보면 트리가 불균형하게 자라는 경우가 발생
할 수 있습니다. 예를 들면 데이터를 1,2,3,4,5의 순서로 이진탐색트리에 추가하게 된다면 (
이 경우 데이터 값의 크기를 기준으로 큰 값은 오른쪽 자식, 작은 값은 왼쪽 자식으로 구성
하였습니다.) 아래 그림과 같은 형태로 이진탐색트리가 구성되게 됩니다.
선형적으로 되기 때문에 O(N)의 형태에 가까워
집니다. 그래서 이렇게 이진 탐색트리가 불균형
하게 자라는 것을 방지하기 위해서 데이터 추가
,삭제할 때마다 트리의 균형을 잡아주기 위하여
레드-블랙 트리가 나왔다고 합니다~!
레드-블랙 트리가 균형을 유지하는 비결은 다음의 6가지 규칙을 준수하기 때문인데요. 6가지
의 규칙으로는
1. 노드는 레드 or 블랙 중 하나의 색을 가진다.
2. 루트 노드는 반드시 블랙이다.
3. 모든 잎 노드는 블랙이다.
4. 레드노드의 자식노드는 블랙이다. 블랙노드의 자식으로는 어떤 노드가 와도 상관이 없다.
5. 루트노드에서 모든 잎노드까지의 경로상의 블랙노드의 개수는 모두 같다.
6. 새로 추가되는 노드는 레드노드이다.
이진탐색트리가 이런 규칙을 만족시킨다면은 이 트리의 특정 노드의 왼쪽 서브트리와 오른쪽
서브트리간에 2배 이상 노드의 불균형이 발생하지 않습니다.(2배이상 왼쪽 서브트리와 오른
쪽 서브트리의 높이차이가 발생하지 않습니다) 왜냐하면은 4번 조건으로 레드노
드는 자식으로 레드노드를 가지지 못하고(즉 연속으로 레드노드가 2번 나오지 못하고) 5번 조
건으로 루트노드에서 특정 리프노드로 가는 경로상의 모든 블랙노드의 갯수는 같아야 하기 때
문이죠.
그리고 레드-블랙 트리에서는 노드의 추가, 삭제 연산을 하고 트리를 균형잡힌 트리로 재 구성
하기 위해서 회전이라는 연산도 제공합니다. 회전은 우회전과 좌회전이 있습니다.
우회전은 특정 노드의 왼쪽 자식노드를 부모노드로 바꾸고 왼쪽 자식노드의 오른쪽 자식노드
를 부모노드로 연결하는 연산입니다. 이 때 원래 있던 왼쪽자식의 오른쪽 자식노드는 부모의
모의 왼쪽 자식노드로 변경하여 줍니다.
기까지 올리고 다음에는 삽입, 삭제 시 어떻게 레드블랙트리가 재구성 되어 균형을 유지하는
지와 직접 소스코드 수준으로 만들어서 올려보겠습니다!~ ^^
내용이 좋아~
답글삭제