Red-black Tree(with Java code)::자료구조

BST(Binary Search Tree)에서 높이를 log n으로 지향해 조금 더 균형 잡힌 트리로 만드는 기법입니다.

 

 - BST 조건을 만족하는 트리 구조

 - 시간복잡도 O(log n)

 

 

1. Red-black Tree의 활용

 

자바

 Collection에서 ArrayList의 내부적인 알고리즘이 RBT로 이루어져 있습니다.

 Map에서 HashMap의 Separate Chaining(충돌 처리 기법 중 하나, LinkedList로 Hash 충돌을 해결하는 방법)에서 사용됩니다.

 (Hash 충돌 기법에 대해서 더 알아보기 -> https://junboom.tistory.com/27)

 

 

2. Red-black Tree의 조건

 

 - 모든 root 노드와 leaf 노드는 black의 색을 가집니다.

 - red의 색을 가지는 자식 노드 또한 black의 색을 가집니다.

 - red의 색을 가지는 노드는 연속(Double Red)으로 나올 수 없습니다.

 - 모든 leaf 노드에서 root 노드까지 가는 경로까지 black의 색을 가진 노드의 수는 모두 같습니다

   (노드의 수는 다를 수 있다).

 

 

3. Red-black Tree의 재정렬 - O(log n)

Restructuring - O(1)

 

1) Double Red가 발생한 자식 노드를 기점으로 parent 노드, grand parent 노드 총 3개의 노드를 정렬합니다.
2) 중앙값을 parent 노드로 지정하고, 기존 Tree에 대입합니다.
3) parent 노드의 색을 black으로 지정하고, 자식 노드의 색을 red로 지정합니다.

Recoloring - O(log n)

 

1) parent 노드를 black의 색으로 교체합니다.

2) grand parent 노드를 red의 색으로 교체합니다.

3) 계속해서 층별 노드의 색을 교체합니다.

4) 이 때, grand parent 노드가 root 노드라면 다시 black으로 교체하여 root 노드를 제외한 모든 노드의 색을 교체합니다.

 

 

4. Java를 이용한 코드 구현

 

public class RedBlackTree {

	private static final int BLACK = 0;
	private static final int RED = 1;
	
	private static Node root;
	
	private static class Node {
		private int value;
		private int color;
		
		Node left;
		Node right;
		Node parent;
		
		Node(int value) {
			this.value = value;
			color = BLACK;
			
			left = null;
			right = null;
			parent = null;
		}
		
		Node() {
			this(-1);
		}
		
		int getValue() {
			return value;
		}
		
		String getColor() {
			return color == RED ? "RED" : "BLACK";
		}
		
		void setColor(int color) {
			this.color = color;
		}
	}
	
	public static void printTree(Node node) {
		if (node == null)
			return;

		System.out.println(node.getValue() + "(" + node.getColor() + ")");
		printTree(node.left);
		printTree(node.right);
	}
	
	public static Node findNode(Node goal, Node node) {
		if (node == null)
			return null;
		
		if (goal.getValue() < node.getValue()) {
			if (node.left != null)
				return findNode(goal, node.left);
		}
		else if (goal.getValue() > node.getValue()) {
			if (node.right != null)
				return findNode(goal, node.right);
		}
		else {
			return node;
		}
		
		return null;
	}
	
	public static void insertNode(Node node) {
		if (root == null) {
			root = node;
			
			System.out.println("Created RBT !!!\n");
		}
		else {
			Node parent = root;
			
			node.setColor(RED);
			
			while (true) {
				if (parent.getValue() < node.getValue()) {
					if (parent.right == null) {
						parent.right = node;
						node.parent = parent;
						break;
					}
					else {
						parent = parent.right;
					}
				}
				else {
					if (parent.left == null) {
						parent.left = node;
						node.parent = parent;
						break;
					}
					else {
						parent = parent.left;
					}
				}
			}
			
			recolorTree(node);
		}
		
		System.out.println("Inserted " + node.getValue());
	}
	
	private static void recolorTree(Node node) {
		while (node.parent != null && "RED".equals(node.parent.getColor())) {
			Node next = null;
			
			if (node.parent == node.parent.parent.left) {
				next = node.parent.parent.right;
				
				if (next != null && "RED".equals(next.getColor())) {
					node.parent.setColor(BLACK);
					next.setColor(BLACK);
					node.parent.parent.setColor(RED);
					node = node.parent.parent;
					continue;
				}
				
				if (node == node.parent.right) {
					node = node.parent;
					
					rotateLeft(node);
				}
				
				node.parent.setColor(BLACK);
				node.parent.parent.setColor(RED);
				
				rotateRight(node.parent.parent);
				break;
			}
			else {
				next = node.parent.parent.left;
				
				if (next != null && "RED".equals(next.getColor())) {
					node.parent.setColor(BLACK);
					next.setColor(BLACK);
					node.parent.parent.setColor(RED);
					node = node.parent.parent;
					continue;
				}
				
				if (node == node.parent.left) {
					node = node.parent;
					
					rotateRight(node);
				}
				
				node.parent.setColor(BLACK);
				node.parent.parent.setColor(RED);
				
				rotateLeft(node.parent.parent);
				break;
			}
		}
		
		root.setColor(BLACK);
	}
	
	private static void rotateLeft(Node node) {
		if (node.parent == null) {
			Node right = root.right;
			root.right = root.right.left;
			right.left = new Node();
			right.left.parent = root;
			root.parent = right;
			right.left = root;
			right.parent = null;
			root = right;
		}
		else {
			if (node == node.parent.left)
				node.parent.left = node.right;
			else
				node.parent.right = node.right;
			
			node.right.parent = node.parent;
			node.parent = node.right;
			
			if (node.right.left != null)
				node.right.left.parent = node;
			
			node.right = node.right.left;
			node.parent.left = node;
		}
	}
	
	private static void rotateRight(Node node) {
		if (node.parent == null) {
			Node left = root.left;
			root.left = root.left.right;
			left.right = new Node();
			left.right.parent = root;
			root.parent = left;
			left.right = root;
			left.parent = null;
			root = left;
		}
		else {
			if (node == node.parent.left)
				node.parent.left = node.left;
			else
				node.parent.right = node.left;
			
			node.left.parent = node.parent;
			node.parent = node.left;
			
			if (node.left.right != null)
				node.left.right.parent = node;
			
			node.left = node.left.right;
			node.parent.right = node;
		}
	}
	
	public static void main(String[] args) {
		root = null;
		
		insertNode(new Node(100));
		insertNode(new Node(50));
		insertNode(new Node(30));
		insertNode(new Node(80));
		insertNode(new Node(200));
		insertNode(new Node(400));
		insertNode(new Node(10));
		insertNode(new Node(500));
		insertNode(new Node(250));
		insertNode(new Node(120));
		
		System.out.println();
		printTree(root);
	}

}

 

[ 결과 ]

 

Created RBT !!!

Inserted 100
Inserted 50
Inserted 30
Inserted 80
Inserted 200
Inserted 400
Inserted 10
Inserted 500
Inserted 250
Inserted 120

100(BLACK)
50(RED)
30(BLACK)
10(RED)
80(BLACK)
400(RED)
200(BLACK)
120(RED)
250(RED)
500(BLACK)