레드-블랙 트리 (Red-Black Tree)

# 개념

이진 탐색 트리이며 자가 균형 이진 탐색 트리이다.

이진 탐색 트리는 값이 편향적으로 구성되는 경우가 있다.

예를 들어 7, 6, 5, 4, 3, 2, 1 순서로 값을 넣으면 한쪽으로 치우진 트리가 만들어진다.

즉, 이진 탐색 트리의 시간 복잡도는 최악의 경우(위 예시) O(트리의 높이=h)만큼의 시간 복잡도를 가진다.

레드-블랙 트리는 위 단점을 색상을 이용한 정렬로 해결하며 O(logN)의 시간 복잡도를 가진다.

또한 균형을 유지하기 위해서 다음의 조건을 만족해야 한다.

• 노드는 레드 혹은 블랙 중 하나이다.
• 루트 노드는 블랙이다.
• 모든 리프 노드(NIL)들은 블랙이다.
• 레드 노드의 자식 노드들은 항상 블랙이다. (즉, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있으며 레드 노드는 연속적으로 나타날 수 없다)
• 어떤 노드로부터 각 리프 노드에 도달하는 경로의 블랙 노드 개수는 동일하다.

 

---

# 구현

function Node (v, leftNode, rightNode, parentNode, nodeColor) {
  this.value = v;
  this.left = leftNode;
  this.right = rightNode;
  this.parent = parentNode;
  this.color = nodeColor;
};

function RedBlackTree () {
  this.root = null;
  this.black = 'Black';
  this.red = 'Red';
  this.nil = new Node(null, null, null, null, this.black);
};

RedBlackTree.prototype.search = function (v) {
   let node = this.root;
   while( node != this.nil && v != node.value ){
      if( v < node.value ){
         node = node.left;
      } else {
         node = node.right;
      }
   }
   return node;
};

RedBlackTree.prototype.insert = function (v) {
   if(this.root == null){
      this.root = new Node(v, this.nil, this.nil, null, this.black);
      return;
   }
   
   let parent;
   let node = this.root;
   while( true ){
      parent = node;
      if( v < node.value ){
         if( node.left != this.nil ){
            node = node.left;
         } else {
            node.left = new Node(v, this.nil, this.nil, parent, this.red);
            node = node.left;
            break;
         }
      } else {
         if( node.right != this.nil ){
            node = node.right;
         } else {
            node.right = new Node(v, this.nil, this.nil, parent, this.red);
            node = node.right;
            break;
         }
      }
   }
   
   // 정렬 시작
   this.orderByColor(node);
};

RedBlackTree.prototype.orderByColor = function (node) {
   // 루트 노르라면 색상을 Black으로 변경
   if( node.parent == null ){
      node.color = this.black;
   } else {
      this.checkParentColor(node);
   }
};

RedBlackTree.prototype.checkParentColor = function (node) {
   // 부모의 색상이 Black이면 유효
   if( node.parent.color == this.black ){
      return;
   } else {
      // 부모 색상이 Red일 때 삼촌의 색상이 Red인지 체크하여 정렬 
      this.orderWhenRedUncle(node);
   }
};

RedBlackTree.prototype.orderWhenRedUncle = function (node) {
   let uncle = this.findUncle(node);
   
   // 부모와 삼촌의 색상이 전부 Red일 때 처리
   if( uncle != this.nil && uncle.color == this.red ){
      // 부모와 삼촌의 색상을 전부 Black으로 변경
      node.parent.color = this.black;
      uncle.color = this.black;
      
      //조상의 색상은 Red로 변경한 뒤 조상 노드를 기준으로 정렬 시작(재귀) 
      const grandParent = this.findGrandParent(node);
      grandParent.color = this.red;
      this.orderByColor(grandParent);
      
   // 삼촌이 없거나 색상이 Black일 때
   } else {
      this.orderWhenBlackUncle(node);
   }
};

RedBlackTree.prototype.orderWhenBlackUncle = function orderWhenBlackUncleThenCurve(node) {
   const grandParent = this.findGrandParent(node);
   
   //// 삼촌이 없거나 검정 색상일 때 처리 
   
   // 기준 노드가 부모의 우측 자식이고 그 부모가 조상의 좌측 자식이라면 부모를 기준으로 좌회전
   // 즉 꺾여있는 노드의 형태를 직선으로 변경해준다고 생각하면 됨.
   if( node == node.parent.right && node.parent == grandParent.left ){
      this.rotateLeft(node.parent);
      node = node.left;
      
   // 기준 노드가 부모의 좌측 자식이고 그 부모가 조상의 우측 자식이라면 부모를 기준으로 우회전
   // 즉 꺾여있는 노드의 형태를 직선으로 변경해준다고 생각하면 됨.
   } else if ( node == node.parent.left && node.parent == grandParent.right ){
      this.rotateRight(node.parent);
      node = node.right;
   }
   
   this.orderWhenBlackUncle2(node);
};

RedBlackTree.prototype.orderWhenBlackUncle2 = function orderWhenBlackUncleThenLine(node) {
   const grandParent = this.findGrandParent(node);
   
   node.parent.color = this.black;
   grandParent.color = this.red;
   
   // 기준 노드가 부모의 좌측 자식이면 우회전
   if( node == node.parent.left ){
      this.rotateRight(grandParent);
      
   // 기준 노드가 부모의 우측 자식이면 좌회전
   } else {
      this.rotateLeft(grandParent);
   }
};

RedBlackTree.prototype.delete = function (v) {
   this.removeNode(this.root, v);
};

RedBlackTree.prototype.removeNode = function (node, v) {
	// 삭제할 노드를 찾았을 때
	if( v == node.value ){
		// 자식이 없다면 해당 노드만 삭제
		if( node.left == this.nil && node.right == this.nil ){
			return this.nil;
		}
		
		// 자식이 2개일 때 successor를 구한 뒤 값을 대입하고 successor 노드를 삭제한다.
		if( node.left != this.nil && node.right != this.nil ){
			const successorValue = this.findSuccessorNode(node).value;
			this.delete(successorValue); // 값을 대입하기 전에 삭제.
			node.value = successorValue;
            
			
		// 자식이 1개일 때 자식 노드의 값을 삭제 노드에 대입하고 자식 노드를 삭제한다.
		} else{
			if(node.left != this.nil){
				node.value = node.left.value;
				node.left = this.nil;
			} else {
				node.value = node.right.value;
				node.right = this.nil;
			}
		}

		this.deleteOneChild(node);
	// 삭제할 노드를 찾을 때까지 탐색
	} else if( v < node.value ){
		node.left =  this.removeNode(node.left, v);
	} else {
		node.right = this.removeNode(node.right, v);
	}
	
	return node;
}

RedBlackTree.prototype.deleteOneChild = function (node) {
   const child = this.isLeaf( node.right ) ? node.left : node.right;
   
   this.replaceNode(node, child);
   if(node.color == this.black){
      if(child.color == this.red){
         child.color = this.black;
      } else {
         this.deleteCase1(child);
      }
   }
};

RedBlackTree.prototype.deleteCase1 = function (node) {
   if(node.parent != null){
      this.deleteCase2(node);
   }
};

RedBlackTree.prototype.deleteCase2 = function (node) {
   let sibNode = this.findSibling(node);
   
   if(sibNode.color == this.red){
      node.parent.color = this.red;
      sibNode.color = this.black;
      if(node == node.parent.left){
         this.rotateLeft(node.parent);
      } else {
         this.rotateRight(node.parent);
      }
      this.deleteCase3(node);
   }
};

RedBlackTree.prototype.deleteCase3 = function (node) {
   let sibNode = this.findSibling(node);
   
   if(node.parent.color == this.black && 
         sibNode.color == this.black && 
         sibNode.left.color == this.black && 
         sibNode.right.color == this.black) {
      sibNode.color = this.red;
      this.deleteCase1(node.parent);
   } else {
      this.deleteCase4(node);
   }
};

RedBlackTree.prototype.deleteCase4 = function (node) {
   let sibNode = this.findSibling(node);
   
   if(node.parent.color == this.red &&
         sibNode.color == this.black &&
         sibNode.left.color == this.black &&
         sibNode.right.color == this.black) {
      sibNode.color = this.red;
      node.parent.color = this.black;
   } else {
      this.deleteCase5(node);
   }
};

RedBlackTree.prototype.deleteCase5 = function (node) {
   let sibNode = this.findSibling(node);
   
   if(sibNode.color = this.black) {
      if(node == node.parent.left &&
            sibNode.right.color == this.black &&
            sibNode.left.color == this.red) {
         sibNode.color = this.red;
         sibNode.left.color = this.black;
         this.rotateRight(sibNode);
      } 
   } else 
   if(node == node.parent.right &&
         sibNode.left.color == this.black && 
         sibNode.right.color == this.red) {
      sibNode.color = this.red;
      sibNode.right.color = this.black;
      this.rotateLeft(sibNode);
   }
   this.deleteCase6(node);
};

RedBlackTree.prototype.deleteCase6 = function (node) {
   let sibNode = this.findSibling(node);
   
   sibNode.color = node.parent.color;
   node.parent.color = this.black;
   
   if(node == node.parent.left){
      sibNode.right.color = this.black;
      this.rotateLeft(node.parent);
   } else {
      sibNode.left.color = this.black;
      this.rotateRight(node.parent);
   }
};

RedBlackTree.prototype.findGrandParent = function (node) {
  if( node != this.nil && node.parent != null ){
    return node.parent.parent;
  } else {
    return this.nil;
  }
};

RedBlackTree.prototype.findUncle = function (node) {
  let uncle = this.findGrandParent(node);
  
  if( uncle == this.nil ){
    return this.nil;
  }
  if( node.parent == uncle.left ){
    return uncle.right;
  } else {
    return uncle.left;
  }
};

//좌측 자식 노드가 없는 가장 좌측의 노드가 min값
RedBlackTree.prototype.min = function (node) {
   return ( node.left != this.nil ) ? this.min(node.left) : node;
};

// 우측 자식 노드가 없는 가장 우측의 노드가 max값
RedBlackTree.prototype.max = function (node) {
   return ( node.right != this.nil ) ? this.max(node.right) : node;
};

/**
* node보다 큰 노드들 중 가장 작거나 node보다 작은 노드들 중 가장 큰 노드인 successor를 찾는다.
*/
RedBlackTree.prototype.findSuccessorNode = function (node) {
   
   // node의 우측 노드가 없다면 좌측 노드의 최대 노드를 반환
   if( node.left != this.nil ){
      return this.max(node.left);
   }
   
   // node의 우측 노드가 있으면 우측 노드의 최소 노드를 반환
   if( node.right != this.nil ){
      return this.min(node.right);
   }
   
   return node;
};


RedBlackTree.prototype.findSibling = function (node) {
   if( node == node.parent.left ){
      return node.parent.right;
   } else {
      return node.parent.left;
   }
};

RedBlackTree.prototype.isLeaf = function (node) {
   return ( node == this.nil ) ? 1 : 0;
};

RedBlackTree.prototype.replaceNode = function (node, child) {
   child.parent = node.parent;
   // 루트 노드일 때
   if(node.parent == null){
  	 // child가 좌측 노드라면 우회전
  	 if( node.left == child ){
  		 this.rotateRight(node)
  		 
  	 // child가 우측 노드라면 좌회전
  	 } else if ( node.right == child ){
  		 this.rotateLeft(node);
  	 }
   } else if( node.parent.left == node ){
      node.parent.left = child;
   } else if ( node.parent.right == node ){
      node.parent.right = child;
   }
};

RedBlackTree.prototype.rotateLeft = function (node) {
   let child = node.right;
   
   node.right = child.right;
   if(child.right != this.nil){
      child.right.parent = node;
   }
   
   child.right = child.left;
   
   child.left = node.left;
   if( node.left != this.nil ){
      node.left.parent = child;
   }
   
   node.left = child;
   
   const tempValue = node.value;
   node.value = child.value;
   child.value = tempValue;
   const tempColor = node.color;
   node.color = child.color;
   child.color = tempColor;
};

RedBlackTree.prototype.rotateRight = function (node) {
   let child = node.left;
   
   node.left = child.left;
   if(child.left != this.nil){
      child.left.parent = node;
   }
   
   child.left = child.right;
   
   child.right = node.right;
   if( node.right != this.nil ){
      node.right.parent = child;
   }
   
   node.right = child;
   
   const tempValue = node.value;
   node.value = child.value;
   child.value = tempValue;
   const tempColor = node.color;
   node.color = child.color;
   child.color = tempColor;
};