Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조의 레드 블랙 트리에 삽입

<시간/>

레드 블랙 트리(Red Black Tree)는 트리의 각 노드가 레드 또는 블랙으로 착색되는 자체 균형 이진 탐색 트리입니다. Red Black Tree에서 수행할 수 있는 작업에는 검색, 삽입 및 삭제의 세 가지 유형이 있습니다.

다음 Red Black Tree에 요소를 삽입해야 한다고 가정해 보겠습니다.

데이터 구조의 레드 블랙 트리에 삽입

레드-블랙 트리에 요소를 삽입하는 아이디어는 매우 간단합니다. 일반 이진 트리에 삽입하는 것처럼 삽입을 수행합니다. 노드의 색상을 확인하여 루트 노드에서 시작하여 특정 위치에 삽입합니다. 그러나 레드-블랙 트리에는 요소를 삽입하기 위한 몇 가지 추가 절차가 있어야 합니다.

그러나 다음 조건을 따를 때 적-검정 트리가 균형을 이룬다는 것을 알아야 합니다.

  • 모든 루트 노드는 검정색이어야 합니다.

  • 모든 노드는 빨간색 또는 검은색입니다.

  • 노드가 빨간색이면 하위 노드는 검정색이어야 합니다.

  • 루트에서 끝까지의 경로는 동일한 수의 블랙 노드를 포함해야 합니다.

레드-블랙 트리에 새 노드를 삽입하려면 삽입 단계를 보면 됩니다.

레드 블랙 트리에 요소를 삽입하는 단계 -

  • 트리가 비어 있는지 여부를 확인합니다. 트리가 비어 있으면 새 노드를 삽입하고 검정색으로 색상을 지정합니다. (루트 노드는 항상 검은색이어야 하기 때문에)'

  • 그렇지 않고 트리가 비어 있지 않으면 새 노드를 리프 노드로 끝에 삽입하고 빨간색으로 색칠합니다.

  • 새 노드의 부모가 빨간색이고 이웃하는(부모의) 노드도 빨간색이면 이웃과 부모 및 조부모의 색상을 뒤집습니다(루트 노드가 아니면 부모 및 이웃의 색만 뒤집음). , 블랙.

  • 새 노드의 부모가 Red이고 이웃(부모) 노드가 비어 있거나 NULL이면 새 노드와 부모를 회전(왼쪽-왼쪽 또는 왼쪽-오른쪽 회전)합니다.

왼쪽 왼쪽 회전과 왼쪽 오른쪽 회전의 두 가지 유형의 회전이 적용됩니다. 순환은 일부 조건에서만 적용됩니다. 조건은 -

  • 새 노드의 부모가 Red이고 인접 노드가 비어 있거나 NULL이면 왼쪽 또는 오른쪽으로 회전합니다.

  • 왼쪽-왼쪽 회전에서 부모와 조부모의 색상을 뒤집습니다. 부모를 조부모로, 조부모를 자식으로 만듭니다.

데이터 구조의 레드 블랙 트리에 삽입


데이터 구조의 레드 블랙 트리에 삽입

알고리즘

RBTreeInsertion(루트, 키)

//The color of the inserted new node is Red
color[key] <- Red
while(key≠root and color (p[key]=Red))
do if p[key]= left(p[p[key]])
   Then y←right[p[p[key]]
// If the parent of the new node is Red(if there is Grandparent instead
root Node) Flip the color.
   if color[y]← Red
   then color(p[key])← Black
      color(p[p[key]])← Red
      key← p[p[key]]
   else if key← right[p[key]]
      then key← p[key]
      //When parent of new node has the red color and its sibling is NULL
   LeftRotate(root,key)
   color(p[key]) ← Black
   color(p[p[key]]) ← Red
RotateRight(root,p[p[key]])
else exchange then left and right elements to make it balance.
color(root)← Black