[자료구조] 힙과 트리

megaseunghan·2022년 12월 1일
자료구조
0

힙과 트리

참고

트리

트리란

노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다.

트리는 트리 내의 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 트리가 있는 재귀적 자료구조이다.

트리의 용어들

  • 루트 노드(root node) - 부모가 없는 노드이다. 트리는 하나의 루트 노드를 가지고 있다. 최상위 레벨에 있다.
  • 간선(edge, branch) - 각 노드를 잇는 연결 고리
  • 단말 노드(leaf node) - 자식이 없는 노드이다. 최하위 레벨에 있다.
  • 형제(sibling) - 같은 부모를 가지고 있는 노드들의 집합을 형제 관계라고 한다. 예를 들어 [A - B][A -C]라는 관계에서 A가 부모 노드라면 B와 C는 형제 관계이다.
  • 레벨(level) - 트리의 특정 깊이를 가지는 노드의 집합이다.
  • 깊이(depth) - 루트에서 어떤 노드까지의 간선 수이다.
  • 넓이(WIdth) - 어떠한 레벨에 있는 노드의 개수이다. 레벨 2의 넓이는 4이다.
  • 크기(size) - 자신을 포함한 모든 자식 노드의 개수이다.
  • 높이(height) - 루트 노드부터 가장 먼 단말 노드까지 가는데 거치게 되는 간선의 개수이다. 높이는 전체 노드의 개수를 알고 있으면 log2(n+1) - 1의 공식으로 구할 수 있다.
    • 레벨 0에서의 노드는 1개이다. 위 식에 대입하면 log2(0 + 1) - 1 = 0이 된다. 따라서 높이는 0이다.
    • 레벨 1에서의 노드는 3개이다. 위 식에 대입하면 log2(3 + 1) - 1 = 1이 된다. 따라서 높이는 1이다.
    • ..
    • 레벨 3에서의 노드는 15개이다. 위 식에 대입하면 log2(15 + 1) -1 = 3이 된다. 따라서 높이는 3이다.
  • 노드 차수(degree) - 각 노드의 자식 수(하위 트리 개수 / 간선 수)이다.
  • 트리의 차수(degree of tree) - 트리의 최대 차수이다.

트리의 특징

  • 하나의 루트 노드와 0개 이상의 하위 트리로 구성된다.
  • 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조이다.
  • 트리 내에 또 다른 트리가 있는 재귀적 자료구조이다.
  • 단순 순환을 갖지 않고 연결된 무방향 그래프 구조이다.
    • 그래프의 한 종류로 '최소 연결 트리'라고도 부른다.
  • 노드 간에 부모 자식 관계를 갖는 계층형 자료구조이다. 모든 자식은 하나의 부모 노드를 가진다.
  • 노드가 n개인 트리는 항상 n -1개의 간선을 가진다.
  • 순회는 Pre-order, In-order, Post-order로 이루어진다.
    • 전위 순회(Pre-order) - 루트 노드에서 시작하여 왼쪽 자식 노드에 갔다가 오른쪽 자식 노드로 가는 순회 방법이다. 다른 모든 노드를 지나기 전에 루트 노드를 방문하기 때문에 이름에 전(Pre)이 들어간다.
    • 중위 순회(In-order) - 왼쪽 자식 노드에서 시작하여 루트 노드에 갔다가 오른쪽 자식 노드로 가는 순회 방법이다.
    • 후위 순회(Post-order) - 왼쪽 자식 노드에서 시작하여 오른쪽 자식 노드에 갔다가 루트 노드로 가는 순회 방법이다.

트리의 종류

  • 이진 트리

    • 각 노드가 최대 두 개의 자식을 갖는 트리

  • 이진 탐색 트리 (Binary Search Tree)

    • 순서화된 이진 트리
    • 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가지고, 오른쪽 자식 노드는 부모의 값보다 커야 한다.

  • 편향 트리(Skew tree)

    • 모든 노드들이 자식을 하나만 가진다.
    • 왼쪽 방향으로만 하나씩만 가질 때 left skew tree, 마찬가지로 오른쪽으로만 하나씩 가질 때는 right skew tree이다.

  • 균형 트리(Balanced Tree, B-Tree)

    • m원 탐색 트리에서 높이 균형을 유지하는 트리
    • height-balanced m-way tree라고도 한다.

  • 원 탐색 트리(M-way Search Tree)

    • 최대 m개의 서브 트리를 가지는 탐색 트리
    • 이진 탐색 트리의 확장된 형태. 높이를 줄이기 위해 사용한다.

  • 완전 이진 트리(Full Binary Tree)

    • 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
    • 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
    • 마지막 레벨 h에서 (1 ~ 2h-1)개의 노드를 가질 수 있다.

  • 정 트리(Full Binary Tree)

    • 모든 트리가 0개 또는 2개의 자식 노드를 갖는 트리

  • 포화 이진 트리(Perfect Binary Tree)

    • 정 트리면서 완전 이지 트리인 경우
    • 모든 말단 노드는 같은 높이에 있어야 하며 마지막 레벨에서 노드 개수는 최대 개수여야 한다.
    • 리프를 제외한 모든 노드가 두개의 또 다른 자식 노드를 가져야 한다.
    • 모든 리프 노드는 같은 레벨에 있어야 한다.
    • 노드의 개수 = 2^(height -1)개여야 한다.

중위 표기법, 후위 표기법

컴퓨터는 괄호, 연산자의 우선순위를 따로 처리하지 않고 왼쪽에서 오른쪽으로 표기된 순서대로 처리하면 결과가 올바르게 나오는 후위 표기법을 사용한다.

  • 중위 표기법 : 연산자를 피연산자의 가운데에 표기한다.
    • 예) 2 + 3
  • 후위 표기법 : 연산자를 피연산자의 뒤에 표기한다.
    • 예) 23 +

트리의 구현

  • 트리 - 노드(부모 노드에 접근하는 구현은 제외함)
class Node<E> {
  E data;
  Node<E> left, right;
  public Node(E obj) {
		this.data = obj;
    left = null;
    right =null;
  }
}
  • 트리 - 새로운 노드 추가(재귀 구현)
    • 루트에서부터 시작한다.
    • 트리의 규칙에 따라 내려간다
    • null인 부분에 새로운 노드를 추가한다.
// 메서드 오버로딩 사용
public void add(E obj) {
  if(root == null) {
		root = new Node<E>(obj);
  } else {
    add(obj, root);
  }
}

private void add(E obj, Node<E> node) {
	if(((Comparable<E>)obj).compareTo(node.data) >= 0) {
    // 오른쪽으로 이동
    if(node.right == null) {
      node.right = new Node<E>(obj);
      return;
    }
    return add(obj, node.right); 
  }
  // 왼쪽으로 이동
  if(node.left == null) {
    node.left = new Node<E>(obj);
    return;
  }
  return add(obj, node.left);
}
  • 트리 - contains
    • 루트에서부터 찾는다.
    • 트리의 규칙에 따라 내려간다
    • 그 요소를 찾으면 true를 반환하고 null인 노드에 다다르면 false를 반환한다.
public boolean contains(E obj) {
  return contains(obj, root);
}

private boolean contains(E obj, Node<E> node) {
  // 트리의 끝이 null일 때
  if(node == null) {
    return false;
	}
	// 찾으려는 값과 일치할 때 
  if(((Comparable<E>)obj).compareTo(node.data) == 0) {
    return true;
  }
  if(((Comparable<E>)obj).compareTo(node.data) > 0) {
    // 오른쪽으로 이동
    return contains(obj, node.right);
  }
  // 왼쪽으로 이동
 	return contains(obj, node.left);
}

  • 트리 - remove

    자식 노드의 개수에 따라 트리의 특정 요소를 제거하는 방법은 다음과 같다.

    1. 리프 노드를 제거할 경우

      • 제거할 노드의 부모 노드의 포인터를 null로 설정한다.

    2. 자식 노드가 하나인 노드를 제거할 경우

      • 제거할 노드의 부모 노드의 포인터를 제거할 노드의 자식 노드로 향하게 한다. 주의할 점은 부모 노드에서 사용했던 포인터와 같은 포인터(left || right)를 사용해야 한다는 것이다.

    3. 자식 노드가 2개인 노드를 제거할 경우

      • 중위 후속자 또는 중위 선임자 중 하나와 자리를 바꾼 후 그 리프 노드를 제거한다.

      • 중위 후속자(In order Successsor)

        : 제거할 노드의 왼쪽(작은 값) 자식 노드 중 그 값이 제일 큰 노드이다. 중위 순회 방식으로 노드를 탐색할 때 루트 노드를 방문하기 직전에 만나게 되는 노드이기 때문에 중위 후속자라고 부른다.

      • 중위 선임자(In order Prodessor)

        : 제거할 노드의 오른쪽(큰 값)자식 노드 중 그 값이 가장 작은 노드이다.

      • 제거 흐름

      • 삭제를 할 때 중위 후속자 또는 중위 선임자 노드가 제거 대상 노드의 자리와 스왑하는 이유는 다음과 같다. 트리는 부모 노드보다 작은 값을 부모의 왼쪽에, 부모 노드 보다 큰 값은 오른쪽에 위치 시킨다. 자식 노드가 2개인 부모 노드를 제거할 땐 위 트리의 규칙을 지켜주어야 하는데 이 규칙을 만족시키는 노드가 중위 후속자 또는 중위 후임자이다.

트리의 회전

int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18};

위 배열을 트리로 표현해보자

  • 1번 트리

  • 2번 트리

위 두 트리의 차이는 균형이다. 첫 번째 그림인 트리는 균형이 잡혀 있고 두 번째 트리는 그렇지 않다.

2번 트리는 연결 리스트처럼 한 방향으로 나열된 트리이고, 이런 트리를 균형이 잡히지 않은 트리라고 한다. 그리고 이렇게 균형 잡히지 않은 트리의 균형을 잡기 위해 노드 위치를 바꾸는 과정을 회전이라고 한다.

균형 잡힌 트리에서 특정 요소를 탐색하는 시간 복잡도는 O(log n)이다. 반면에 균형 잡히지 않은 트리에서는 연결리스트와 같은 O(n)이 된다. 따라서 데이터를 효율적으로 관리하려면 트리를 균형있게 만들어야 한다.

조부모, 부모, 자식 노드의 크기 관계에 따라 우측 회전 또는 좌측 회전을 한다. 트리를 재정렬하면 항상 중간 크기의 요소가 가장 위에 있는 노드가 된다.

  1. 불균형이 왼쪽 서브트리에서 나타날 경우

    크기 관계는 조부모 > 부모 > 자식 순이다. 우측 회전을 하여 조부모 노드를 부모의 우측 자식 위치로 옮긴다.

    public Node<E> rightRotate(Node<E> node) {
  Node<E> temp = node.left;
  node.left = temp.right; null
  temp.right = node; 
  return tmp;
}

  1. 불균형이 오른쪽 서브트리에서 나타날 경우

    크기 관계는 자식 > 부모 > 조부모이다. 좌측 회전을 하여 조부모 노드를 부모 노드의 왼쪽 자식 위치로 옮긴다.

    public Node<E> leftRotate(Node<E> node) {
  Node<E> temp = node.right;
  node.right = temp.left;
  temp.left = node;
  return tmp;
}

  1. 불균형이 오른쪽 자식의 왼쪽 서브트리에서 나타날 경우

    크기 관계는 부모 > 자식 > 조부모이다. 자식 노드에 대해 부모 노드를 우측 회전 후, 좌측 회전을 하여 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮긴다.

    public Node<E> rightLeftRotate(Node<E> node) {
	node.right = rightRotate(node.right);
  return leftRotate(node);
}

  1. 불균형이 왼쪽 자식의 오른쪽 서브트리에서 나타날 경우

    크기 관계는 부모 > 조부모 > 자식이다. 자식 노드에 대해 부모 노드를 좌측 회전 후, 우측 회전을 하여 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮긴다.

    public Node<E> leftRightRotate(Node<E> node) {
  node.left = leftRotate(node.left);
  return rightRotate(node);
}

힙(Heap)

힙이란

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 기반의 자료구조이다.

힙은 규칙에 의해 느슨한 정렬 상태인 반정렬 상태를 유지한다.

완전 이진 트리란?

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h에서 1부터 2h-1 개의 노드를 가질 수 있다. 출처 : https://ko.wikipedia.org/wiki

힙의 종류

어떤 종류의 힙인지에 따라 두 가지의 다른 규칙이 존재한다.

  1. 부모 노드가 자식 노드보다 크다. *MAX HEAP
  2. 부모 노드가 자식 노드보다 작다 *MIN HEAP

가장 큰 숫자가 루트 노드가 되게 하려면 MAX HEAP의 규칙을, 가장 작은 숫자가 루트 노드가 되게 하려면 MIN HEAP의 규칙을 사용하면 된다.

힙의 추가와 제거

힙에 새로운 데이터를 추가하거나 제거할 때는 힙의 규칙을 지켜야 한다. 최대 힙이면 부모 노드가 자식 노드보다 커야 하고 최소 힙일 때는 자식 노드가 부모 노드보다 커야 한다.

노드 추가(MAX HEAP)

  • 완전 이진 트리이기 때문에 노드의 위치는 다음과 같은 성질을 가진다.

    • children : 2 parent + 1 또는 2 parent + 2
    • parent : floot((children-1)/2)

  • 삽입 과정

    1. 비어있는 공간에 노드를 추가한다.
    2. 부모 노드보다 큰 숫자인지 확인하고 만약 그렇다면 두 노드를 바꾼다(TRICKLE UP)

  • 삽입 구현

int lastposition; // 어디까지 요소를 넣었는지 기록
E[] array = (E[]) new Object[size]; // 힙이 구현될 배열
public void add(E obj){ //
	array[++lastposition] = obj; // 1. 노드 추가
	trickleup(lastposition); // 2. trickle up
}
public void swap(int from, int to){ // 위치 변경
	E tmp = array[from];
	array[from] = array[to];
	array[to] = tmp;
}
public void trickleup(int position){
	if (position == 0) // 루트 노드일 때는 이미 작업이 모두 끝난 상태
		return;
	int parent = (int) Math.floor((position-1)/2); // 매개변수 포지션으로 부모 노드의 위치를 구함
	if (((Comparable<E>) array[position]).compareTo(array.parent)>0) { // 포지션 위치의 노드가 부모 노드 보다 값이 크다면 swap
		swap(position, parent);
		trickleup(parent); // 루트 값까지 비교할 수 있게 재귀 사용
	}
}

노드 제거(MAX HEAP)

힙에서의 노드 제거는 무조건 루트를 제거해야 한다.

  1. 루트를 제거한다.
  2. 트리의 마지막 요소를 루트에 넣는다.
    • 마지막 요소를 루트에 넣지 않고 루트의 자식 중 값이 큰 노드로 바꿔주게 되면 최하위 레벨의 단말 노드까지 노드의 위치를 바꿔야 하기 때문에 마지막 요소를 루트에 넣는 것이다.
  3. 루트에서 시작하여 두 자식 중 큰 노드와 위치를 바꿔주며 힙의 규칙을 만족하게 한다.(TRICKLE DOWN)
  • 삭제 구현
public E remove(){
	E tmp = array[0];
	swap(0, lastposition--); // 루트와 마지막 노드를 바꿔주고 lastposition을 줄여 배열에서 제거합니다.
	trickleDown(0);
	return tmp;
}
public void trickleDown(int parent){
	int left = 2*parent + 1;
	int right = 2*parent + 2;
	// 마지막에 왼쪽 자식이 클 때
	if (left==lastposition && (((Comparable<E>)array[parent]).compareTo(array[left])<0){
		swap(parent, left)
		return;
	}
	// 마지막에 오른쪽 자식이 클 때
	if (right==lastposition && (((Comparable<E>)array[parent]).compareTo(array[right])<0){
		swap(parent, right)
		return;
	}
	// 마지막에 부모가 클 때
	if (left >= lastposition || right >= lastposition)
		return;
	// 왼쪽 자식이 클 때
	if (array[left] > array[right] && array[parent] < array[left]) {
		swap(parent, left);
		trickleDown(left);
	}
	// 오른쪽 자식이 클 때
	else if (array[parent] < array[right]){
		swap(parent, right);
		trickleDown(right);
	}
}

AVL 트리

AVL 트리란

위 트리의 회전에서 언급한 회전을 사용하여 스스로 균형을 잡는이진 탐색 트리의 속성을 가진 트리이다.

AVL 트리의 특징

  • AVL 트리에서는 왼쪽과 오른쪽의 높이가 항상 1보다 작거나 같아야 한다.
  • 높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄인다.
  • 추가, 삭제, 검색의 시간 복잡도가 O(log N)이다.

AVL 트리 불균형 종류

헷갈려서 다시 정리했다.

  • LL(Left Left) - 왼쪽 자식 노드의 왼쪽 서브트리에서 불균형 발생

    • 우회전을 적용하면 불균형이 해소된다.

  • RR(Right Right) - 오른쪽 자식 노드의 오른쪽 서브트리에서 불균형 발생

    • 좌회전을 적용하면 불균형이 해소된다.

  • LR(Left Right) - 왼쪽 자식 노드의 오른쪽 서브트리에서 불균형 발생

    • 좌회전 적용 후 우회전을 적용하면 불균형이 해소된다.

  • RL(Right Left) - 오른쪽 자식 노드의 왼쪽 서브트리에서 불균형 발생

    • 우회전 적용 후 좌회전을 적용하면 불균형이 해소된다.

AVL 트리 구현

  • 노드
class Node<T> {
  T data;
	Node<T> left;
  Node<T> right;
  Node<T> parent;  
  public Node(T obj) {
    this.data = obj;
    left = right = parent = null;
  }
}
  • 추가
public AVLTree() {
  root = null;
  currentSize = 0;
}

public void add(E obj) {
  Node<E> node = new Node<E>(obj);
  // 트리가 비어있을 경우
  if(root = null) {
    root = node;
    currentSize++;
    return;
  }
  // 트리에 노드가 있을 경우 add메서드를 재귀로 호출
  add(root, node);
}

// 재귀 add
public void add(Node<E> parent, Node<E> newNode) {
  if(((Comparable<E>)newNode.data.compareTo(parent.data) > 0) {
    if(parent.right == null) {
      parent.right = newNode;
      newNode.parent = parent;
      currentSize;
    } else {
      add(parent.right, newNode);
    }
  } else {
    if(parent.left == null) {
      if(parent.left == null) {
        parent.left = newNode;
        newNode.parent = parent;
        currentSize++;
      } else {
        add(parent.left, newNode);
      }
    }
  }
  checkBalance(newNode);
}
  • 균형 확인
public void checkBalance(Node<E> node) {
  // 높이 차이가 1 초과 또는 미만
  if(
    (height(node.left) - height(node.right) > 1) ||
    (height(node.left) - height(node.right) < -1)
  ) {
  		rebalance(node); 
  }
  // 부모 노드를 계속 확인해서 루트까지 간다.
  if(node.parent == null) {
    return;
  }
  checkBalance(node.parent);
}
  • 균형 맞추기
public void rebalance(Node<E> node) {
	// 왼쪽 자식 > 오른쪽 자식
  if(height(node.left) - height(node.right) > 1) {
    // 노드의 왼쪽 자식의 왼쪽 서브트리가 오른쪽 서브 트리보다 크다면 우측 회전
    if(height(node.left.left) > height(node.left.right)) {
      node = rightRotate(node); 
    // 노드의 왼쪽 자식의 오른쪽 서브트리가 왼쪽 서브 트리보다 크다면 좌측-우측 회전
    } else {
      node = leftRightRotate(node);
    }
  } else {
		// 노드의 오른쪽 자식의 왼쪽 서브트리가 오른쪽 서브 트리보다 크다면 우측-좌측 회전
    if(height(node.right.left) > height(node.right.right)) {
      node = rightLeftRotate(node); 
    // 노드의 왼쪽 자식의 오른쪽 서브트리가 왼쪽 서브 트리보다 크다면 좌측 회전
    } else {
      node = leftRotate(node);
    }
  }
  if(node.parent == null) {
    root = node;
  }
}
  • 추가 예제

아래 GIF는 강의의 실습 예제이다.

AVL 시뮬레이터를 통해 직접 추가하면서 그 과정을 GIF로 담았다.

AVL의 규칙에 따라 루트 노드인 43에 18, 22, 9, 21, 6, 8, 20, 63, 50, 62, 51을 순서대로 추가한 결과이다. 추가될 때 마다 균형이 깨졌는지 확인하고 회전을 하여 균형을 유지한다.

레드-블랙 트리

레드-블랙 트리란

레드-블랙 트리는 자가 균형 이진 탐색 트리로써, 이진 탐색 트리(BST)의 한 종류이며, 스스로 균형을 잡는 트리이다.

BST의 worst case의 단점을 개선하게 된다.(최악의 경우에도 O(N)이 아닌 O(logN)의 시간복잡도를 가진다.)

레드-블랙 트리의 규칙

우선 알아둬야 할 것

  • nil 노드
    • 존재하지 않음을 의미하는 노드
    • 자녀가 없을 때 자녀를 nil 노드로 표기한다.
    • 값이 있는 노드와 동등하게 취급한다.
    • RB트리에서 leaf노드는 nil노드이다
  • black height
    • 아래 4번의 규칙을 만족해야 이 개념이 성립된다.
    • 노드 X에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black의 수(자기 자신은 카운트에서 제외한다.)

레드-블랙 트리의 규칙은 다음과 같다.

  1. 모든 노드는 빨간색이거나 검은색이다. 다른 색은 존재하지 않는다.
  2. 루트는 항상 검은색이다. 만약 루트가 검은색이 아니라면 강제로 검은색으로 만들어 주어야 한다.
  3. 새로 추가되는 노드는 항상 빨간색이다. 만약 새로 추가된 노드가 루트 노드라면 우선 빨간색으로 추가한 다음 2에서 언급한 내용처럼 강제로 검은색으로 만들어준다.
    • 새로 삽입하는 노드가 빨간색이어야 하는 이유는 삽입 후에도 규칙 4번을 만족해야 하기 때문이다.
  4. 루트에서 리프 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 한다.
  5. 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어선 안된다. 즉, 빨간색의 자식은 모두 검은색이여야 한다.
  6. 모든 비이었는 노드는 검은색이라고 가정한다.

레드-블랙 트리의 균형

삽입 또는 삭제 시 주로 위 규칙의 4, 5를 위반하고, 이것을 해결하기 위해 구조를 바꾸다보면 자연스럽게 트리의 균형이 잡히게 된다. 레드-블랙 트리에서 균형이 깨지면 회전, 색상 전환을 통해 이를 해결한다.

  1. 이모 노드가 검은색일 경우 - 회전

    회전을 하고 나면 부모 노드는 검은색, 두 자식 노드는 빨간색이 되어야 한다.

  2. 이모 노드가 빨간색일 경우 - 색상 전환

    색상 전환을 하고 나면 부모 노드는 빨산색, 두 자식 노드는 검은색이 되어야 한다.

레드-블랙 트리 구현

  • 클래스
public class RedBlackTree<K,V> implements RedBlackI<K,V> {
	Node<K,V> root;
	int size;
	class Node<K,V> {
		K key;
		V value;
		Node<K,V> left, right, parent;
		boolean isLeftChild, black;
		public Node (K key, V value) {
			this.key = key;
			this.value = value;
			left = right = parent = null;
			black = false;
			isLeftChild = false;
		}
	}
}

  • 삽입 - add 메서드

    1. 이진 탐색 트리와 삽입 방식은 동일하다.
    2. 삽입 후에 레드-블랙 트리 위반 여부를 확인한다.
    3. 트리 규칙을 위반했다면 재조정한다.
    4. 레드-블랙 트리의 규칙을 다시 만족한다.
    public void add(K key, V value){
	Node<K,V> node = new Node<K,V>(key, value); // black = false, isLeftChild = false
	// 트리가 비어있을 경우
	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보다 작거나 같으면 트리의 왼쪽에 추가하면 됩니다.    
  } else {
    if (parent.left == null){
      parent.left = newNode;
      newNode.parent = parent;
      newNode.isLeftChild=true;
      return;
    }
    return add(parent.left, newNode);
    // 레드 블랙 트리가 규칙에 맞게 잘 되어있는지 확인합니다.
    checkColor(newNode);
}

  • 색깔 검증 - checkColor 메서드

    • 레드-블랙 트리의 6가지 규칙을 만족하는지 확인해준다.
    public void checkColor(Node<K,V> node) {
  // 루트 노드는 항상 검은색이므로 확인할 필요가 없습니다.
  if(node == root) {
    return;
  }
  // 노드 2개가 연속적으로 빨간색이 나오는 경우
  if(!node.black && !node.parent.black) {
    correctTree(node); 
  }
  // 부모 노드를 재귀적으로 확인합니다.
  checkColor(node.parent);
}

  • 연속된 빨간색 노드 수정 - correctTree 메서드

    • 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어선 안된다. 즉, 빨간색의 자식은 모두 검은색이여야 한다.의 규칙이 만족되지 않았을 때 해당 노드의 이모 노드 색깔을 파악한 후, 회전 또는 색상 변환을 수행한다.
    public void correctTree(Node<K,V> node) {
	// node의 부모 노드가 왼쪽 자식이면 이모 노드는 조부모 노드의 오른쪽 자식입니다.
  if(node.parent.isLeftChild) {
    // 이모 노드가 검은색(이모 노드가 비어있는 경우 포함)
    if(node.parent.parent.right == null || node.parent.parent.right.black) {
      // 회전
      return rotate(node);
    }
    // 이모 노드가 빨간색인 경우
    if(node.parent.parent.right != null) {
      // 색상 변환
      node.parent.parent.right.black = true;
    }
    node.parent.parent.black = false;
    node.parent.black = true;
    return;
  }
  // node의 부모 노드가 오른쪽 자식이면 이모 노드는 조부모 노드의 왼쪽 자식입니다.
  // 위 코드와 동일하게 하되, 이모 노드를 node.parent.parent.left로 바꿔야 합니다.
   else {
    // 이모 노드가 검은색(이모 노드가 비어있는 경우 포함)
     if(node.parent.parent.left == null || node.parent.parent.left.black) {
       // 회전
       return rotate(node);
     } 
     // 이모 노드가 빨간색인 경우
     if(node.parent.parent.left != null) {
       // 색상 변환
       node.parent.parent.left.black = true;
     }
     node.parent.parent.black = false;
     node.parent.black = true; 
     return;
   }
}

  • 회전 - rotate 메서드

    • 현재 노드와 부모 노드가 각각 오른쪽 자식인지 왼쪽 자식인지에 따라 필요한 회전이 달라진다. 각각의 경우에 따라 수행이 다르다.
    • 파라미터로 들어가는 node는 규칙을 어긋나게한 노드의 조부모 노드이다.
    public void rotate(Node<K,V> node){
	// 현재 노드가 왼쪽 자식
	if (node.isLeftChild) {
		// 부모 노드가 왼쪽 자식
		if (node.parent.isLeftChild) {
			// 조부모 노드를 우측회전
			rightRotate(node.parent.parent);
			node.black = false;
			node.parent.black = true;
			if(node.parent.right != null)
				node.parent.right.black = false;
			return;
		}
		// 부모 노드가 오른쪽 자식
		// 조부모 노드를 우측-좌측 회전
		rightLeftRotate(node.parent.parent);
		node.black = true;
		node.right.black = false;
		node.left.black = false;
		return;
  // 현재 노드가 오른쪽 자식
	} else {
  	// 부모 노드가 오른쪽 자식
		if (!node.parent.isLeftChild) {
			// 조부모 노드를 좌측회전
			leftRotate(node.parent.parent);
			node.black = false;
			node.parent.black = true;
			if(node.parent.left != null)
				node.parent.left.black = false;
			return;
		}
		// 부모 노드가 왼쪽 자식
		// 조부모 노드를 좌측-우측 회전
		leftRightRotate(node.parent.parent);
		node.black = true;
		node.left.black = false;
		node.right.black = false;
		return;		
}

  • 좌측 회전 - leftRotate 메서드

    • 파라미터로 들어가는 node는 규칙을 어긋나게한 노드의 조부모 노드이다.
    // 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다.
public void leftRotate (Node<K,V> node){
	Node<K,V> temp = node.right;
	node.right = temp.left;
	// 부모 노드 node.right가 temp가 되면서 조부모 노드가 없어집니다.
	if(node.right != null) {
		node.right.parent = node;  
		node.right.isLeftChild = false;
	}
	// node가 루트인 경우
	if(node.parent = = null) {
		root = temp;
		temp.parent = null;
	}
	// node가 루트가 아닌 경우
	else {
		temp.parent = node.parent;
		if(node.isLeftChild) {
			temp.isLeftChild = true;
			temp.parent.left = temp;
		} else {			
			temp.isLeftChild = false;
			temp.parent.right = temp;
		}
		temp.left = node;
		node.isLeftChild = true;
		node.parent = temp;
	}
}

  • 우측 회전 - rightRotate 메서드

    • 파라미터로 들어가는 node는 규칙을 어긋나게한 노드의 조부모 노드이다.
    // 우측 회전: 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮깁니다.
public void rightRotate (Node<K,V> node){
	Node<K,V> temp = node.left;
	node.left = temp.right;
	// 부모 노드 node.left가 temp가 되면서 조부모 노드가 없어집니다.
	if(node.left != null) {
		node.left.parent = node;  
		node.left.isLeftChild = true;
	}
	// node가 루트인 경우
	if(node.parent == null) {
		root = temp;
		temp.parent = null;
	}
	// node가 루트가 아닌 경우
	else {
		temp.parent = node.parent;
		if(node.isLeftChild) {
			temp.isLeftChild = true;
			temp.parent.left = temp;
		} else {			
			temp.isLeftChild = false;
			temp.parent.right = temp;
		}
		temp.right = node;
		node.isLeftChild = false;
		node.parent = temp;
	}
}

  • 좌측-우측 회전 - leftRightRotate 메서드

    • 파라미터로 들어가는 node는 규칙을 어긋나게한 노드의 조부모 노드이다.
    public void leftRightRotate(Node<K,V> node) {
  leftRotate(node);
  rightRotate(node);
}

  • 우측-좌측 회전 - rightLeftRotate 메서드

    • 파라미터로 들어가는 node는 규칙을 어긋나게한 노드의 조부모 노드이다.
    public void rightLeftRotate(Node<K,V> node) {
  rightRotate(node);
  leftRotate(node);
}

  • 높이 - height 메서드

    public int height() {
  if(root == null) {
    return 0;
  }
  return height(root) - 1;
}

private int heigth(Node<K,V> node) {
 	if(node == null) {
    return 0;
  } 
  int leftHeight = height(node.left) + 1;
  int rightHeight = height(node.right) + 1;
  if(leftHeight > rightHeight) {
    return leftHeight;
  } else {
    return rightHeight;
  }
}

  • 검은색 노드 개수 - blackNodes 메서드

    public int blackNodes(Node<K,V> node) {
  if(node == null) {
    return 1;
  }
  int rightBlackNodes = blackNodes(node.right);
  int leftBlackNodes = blackNodes(node.left);
  // 오른쪽과 왼쪽의 검은색 노드 개수가 다르면 에러를 내거나 고쳐준다.
  if(rightBlackNodes != leftBlackNodes) {
    throws new Exception("양쪽 서브 트리의 검은색 노드의 개수가 일치하지 않습니다.");
    // 또는 고쳐준다.    
  }
  if(node.black) {
    leftBlackNodes++;
  }
  return leftBlackNodes++;
}

  • 삭제 - remove 메서드

    • 노드를 삭제하고 삭제된 후의 트리가 규칙에 어긋나는지를 확인해야 한다. 그 중 삭제되는 색이 규칙의 위배되는지를 확인하는 방법이 될 수 있다. 삭제되는 색은 다음과 같이 정의된다.
      1. 삭제되는 노드의 자녀가 1개이거나 없는 경우
        • 삭제되는 색 : 삭제되는 노드의 색깔
      2. 삭제되는 노드의 자녀가 2개인 경우
        • 삭제되는 색 : 삭제되는 노드의 successor(중위 후속자)의 색
    • 삭제되는 색이 어떤 색이냐에 따라 바로 규칙을 위배하는지 알 수 있다.
      1. 빨간색 - 6가지 중 어떠한 속성도 위배하지 않는다.
      2. 검은색 - 1. 루트 노드는 항상 검은색, 2. 빨간색의 자식은 모두 검은색, 3. 루트에서 리프 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 함의 3개 규칙을 경우에 따라 위배하게 된다.
        • 그 중 3번 규칙은 특수한 상황을 제외하면 항상 위배하게 된다.
profile
megaseunghan
이전 포스트

약 1년 회고, 내가 느낀 1일 1커밋의 장단점

0개의 댓글