레드 블랙 트리(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