들어가기 전에

레드 블랙 트리의 add 메소드에 대해 살펴보도록 하겠습니다.

학습 목표

레드 블랙 트리의 add 메소드를 이해할 수 있습니다.

핵심 단어

• 레드 블랙 트리
• add 메소드
  

강의 듣기

add 메소드

add 메소드의 동작 방식은 AVL 트리와 동일합니다. 단, isLeftChild가 추가되기 때문에 이를 고려해주어야 합니다.

add 메소드에 대한 코드는 다음과 같습니다. 트리가 비어있으면 노드를 추가하고 비어있지 않다면 재귀 add 메소드를 호출합니다.

public void add(K key, V value){
	Node<K,V> node = new Node<K,V>(key, value);
	// 트리가 비어있을 경우
	if (root == null) {
		root = node;
		root.black = true;
		size++;
		return;
	}
	// 트리에 노드가 있을 경우 재귀 메소드 사용
	add(root, node);
	size++;
}
// add 재귀함수, 내부클래스
private void add (Node<K,V> parent, Node<K,V> newNode){
	// newNode의 data가 parent의 data보다 크면 트리의 오른쪽에 추가하면 됩니다.
	if (((Comparable<K>) newNode.key).compareTo(parent.key) > 0){
		if(parent.right == null){
			parent.right = newNode;
			newNode.parent = parent;
			newNode.isLeftChild=false;
			return;
		}
		return add(parent.right, newNode);
	// newNode의 data가 parent의 data보다 작거나 같으면 트리의 왼쪽에 추가하면 됩니다.
	if (parent.left == null){
		parent.left = newNode;
		newNode.parent = parent;
		newNode.isLeftChild=true;
		return;
	}
	return add(parent.left, newNode);
	// 레드 블랙 트리가 규칙에 맞게 잘 되어있는지 확인합니다.
	checkColor(newNode);
}

생각해보기

1) checkColor 메소드는 왜 필요한가요?