자료구조 - Heap(힙) & Tree(트리)

힙과 트리

트리

• 노드를 나무 형태로 연결한 구조를 트리라고 한다
• 트리에 있는 각각의 요소는 노드라고 한다.
• 노드는 부모와 자식형태로 이어진다.
  • root(뿌리) - 트리의 시작 부분, 뿌리를 통해서 트리를 탐색한다
  • leaf(앞) - 자식이 딸려있지 않은 부분
  • edge(간선) - 두 노드를 연결하는 선, 뿌리로부터 간선의 수에 따라 Level을 나눔

---

힙 - Tree levels

힙

• 최대값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 구조
• max heap(최대 힙)과 min heap(최소힙)이 있다.
  • 최대 힙 : 부모 노드 > 자식노드, 가장 큰 숫자가 뿌리에 있다
  • 최소 힙 : 부모 노드 < 자식노드, 가장 작은 숫자가 뿌리에 있다

• log​2​​(n+1)−1 은 height와 일치 -> 트리의 요소의 개수를 알면 트리의 높이를 계산할 수 있다.

---

힙 - 추가와 제거

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

---

노드 추가

1. 비어있는 공간에 노드를 추가
2. 부모 노드보다 큰 숫자인지 확인 -> 두 노드를 바꾼다(trickle up)

---

루트 제거

1. 루트를 제거
2. 트리의 마지막 요소를 루트에 넣어준다
3. 루트에서 시작하여 두 자식 중 큰 노드와 바꿔주어 힙의 규칙을 만족한다(trickle down)

• 힙에서는 무언가를 제거 할때 항상 루트를 제거해야한다

---

힙 - TrickleUp 함수

• 완전이진트리이기 때문에 노드의 위치는 다음과 같은 성질을 가진다
  • children(자식 노드) : 2 * parent + 1 또는 2 * parent + 2
  • parent(부모 노드) : floor((child-1)/2)

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(position, parent);
		trickleup(parent);
	}
}

---

힙 - TrickleDown 함수

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);
	}
}

---

힙 - 정렬

• 힙 규칙에 맞게 숫자의 순서를 맞추는 과정을 힙 정렬 알고리즘이라고 한다
• 힙 규칙에 맞게 TrickleDown을 반복하면 그 숫자들이 정렬된다
• 시간 복잡도는  O(nlogn), 두 수를 비교해서 하나를 고르는 방식으로 숫자를 골라내기 때문이다. (총 n개의 숫자를 logn개의 숫자와 비교합니다.)
• 숫자들의 순서를 바꿔 정렬하기 때문에 데이터의 복사본을 만들 필요가 없다(힙 정렬의 장점)

---

트리 - 완전 트리와 정트리

완전 트리(complete tree)

• 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있다
• 마지막 줄은 왼쪽에서 오른쪽 순서로 채워져 있는 트리

 

정 트리(full tree)

• 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있다
• 모든 잎이 같은 레벨에 있는 트리

---

트리 - 순회

• 전위 순회(Pre order  traversal)
  • root -> left -> right
  • 루트 노드에서 시작하여 왼쪽 자식 노드에 갔다가 오른쪽 자식 노드로 가는 순회 방법
  • 다른 모든 노드를 지나기 전에 루트 노드를 방문하기 때문에 이름에 전(Pre)이 들어간다
• 중위 순회 (In order traversal)
  • left -> root -> right
  • 왼쪽 자식 노드에서 시작하여 루트 노드에 갔다가 오른쪽 자식 노드로 가는 순회 방법
• 후위 순회 (Post order traversal)
  • left -> right -> root
  • 왼쪽 자식 노드에서 시작하여 오른쪽 자식 노드에 갔다가 루트 노드로 가는 순회 방법
• 너비 우선 선회/레벨 순서 순회 (Breadth first traversal/level order traversal)
  • 가장 위에 있는 노드에서 시작하여 왼쪽에서 오른쪽으로 가는 순회 방법

---

트리 - 표현

 

• 중위 표기식: 2 * 3
• 후위 표기식: 2 3 *

---

• 중위 표기식: (((22 / 11) + 3) * (6 + 5)) - 50
• 후위 표기식: 22 11 / 3 + 6 5 + * 50 -

---

트리 - 노드 클래스

ㅜ

• 부모 노드보다 작은 데이터가 왼쪽 자식 노드
• 부모 노드보다 큰 데이터가 오른쪽 자식 노드
• 전체 데이터의 반은 무시하고 시간 복잡도 (logn)
• 트리에서는 노드가 left, right 포인터를 갖는다

class Node<E> {
	E data;
	Node <E> left, right;
	public Node(E obj){
		this.data = obj;
		left=right=null;
	}
}

---

트리 - 재귀 함수

• 트리에 새로운 데이터를 추가하는 과정
  1. 루트에서부터 시작
  2. 트리의 규칙에 따라 내려간다
  3. null인 부분을 찾았다면 그곳에 새로운 노드를 추가

public void add (E obj, Node<E> node){
	if (((Comparable<E>) obj).compareTo(node.data) > 0){
		// go to the right
		if(node.right == null) { // 3
			node.right = new Node<E>(obj);
			return;
		}
		return add (obj, node.right); // 2
	}
	// go to the left
	if(node.left == null) { // 3
		node.left = new Node<E>(obj);
		return;
	}
	return add (obj, node.left); // 2
}
// 트리가 비어있을 경우 (오버로딩)
public void add (E obj){
	if (root==null)
		root = newNode<E>(obj);
	else
		add(obj, root);
	currentSize++;
}

---

트리 - Contains

• 특정 요소가 트리에 포함되어있는지 확인하는 함수
  1. 루트에서부터 시작
  2. 트리의 규칙에 따라 내려간다
  3. 그 요소를 찾으면 True를 반환, null인 노드에 다다르면 False를 반환

public boolean contains (E obj, Node<E> node){
	// 트리의 끝에 도달했는데 null
	if (node==null)
		return false;
	// node의 data와 일치
	if (((Comparable<E>) obj).compareTo(node.data) == 0)
		return true;
	// go to the right
	if (((Comparable<E>) obj).compareTo(node.data) > 0)
		return contains(obj, node.right);
	// go to the left
	return contains(obj, node.left);
}

---

트리 - 제거

1. 잎 노드를 제거할 경우
   • 그 노드의 부모 노드의 포인터를 null로 설정
2. 자식 노드가 하나인 노드를 제거할 경우
   • 그 노드의 부모 노드의 포인터를 자식 노드로 향하게 하면 된다
   • 주의할 점은 부모 노드에서 사용했던 포인터와 같은 포인터(left, right 중 하나)를 사용해야 한다
3.  자식 노드가 2개인 노드를 제거할 경우
   • 중위 후속자와 중위 선임자 중 하나와 자리를 바꾼 후 그 잎 노드를 제거
   • 중위 후속자(in order successor)
     • 제거하고자 하는 노드에서 시작하여 왼쪽으로 한 번 내려갔다가 계속 오른쪽으로 내려간 곳의 잎 노드
     • 제거하고자 하는 노드보다 작은 노드들 중에서 가장 큰 노드
   • 중위 선임자(in order predessor)
     • 제거하고자 하는 노드에서 시작하여 오른쪽으로 한 번 내려갔다가 계속 왼쪽으로 내려간 곳의 잎 노드
     • 제거하고자 하는 노드보다 큰 노드들 중에서 가장 작은 노드

---

트리 - 회전

• 균형 잡힌 트리를 만들기 위해 트리의 노드 위치를 바꾸는 과정
• 연결 리스트처럼 한 방향으로 나열된 트리는 균형 잡혀 있지 않다고 표현
• 균형 잡힌 트리에서는 특정 요소를 탐색하는 시간 복잡도가 O(logn)이지만 균형 잡히지 않은 트리에서는 연결 리스트와 같은 O(n)
•  데이터를 효율적으로 관리하려면 트리를 균형 있게 만들어야 한다.
• 조부모 노드, 부모 노드, 자식 노드의 크기 관계에 따라 우측 회전, 혹은 좌측 회전
• 트리를 재정렬하면 항상 중간 크기의 요소가 가장 위에 있는 루트

---

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

• 크기 관계는 (조부모 노드) > (부모 노드) > (자식 노드)
• 우측 회전을 하여 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮겨준다.

 

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

• 크기 관계는 (조부모 노드) < (부모 노드) < (자식 노드)
• 좌측 회전을 하여 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮겨준다.

 

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

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

 

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

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

---

트리 - 회전(코드)

// 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다.
public Node<E> leftRotate (Node<E> node){
	Node<E> tmp = node.right; // set temp=grandparents right child
	node.right = tmp.left; // set grandparents right child=temp left child
	tmp.left = node; // set temp left child=grandparent 
	return tmp; // use temp instead of grandparent
}

// 우측 회전: 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮깁니다.
public Node<E> leftRotate (Node<E> node){
	Node<E> tmp = node.left; 
	node.left = tmp.right; 
	tmp.right = node; 
	return tmp;
}

// 우측 회전 후 좌측 회전
public Node<E> rightLeftRotate(Node<E> node){
	node.right = rightRotate(node.right);
	return leftRotate(node);
}

// 좌측 회전 후 우측 회전
public Node<E> leftRightRotate(Node<E> node){
	node.left = leftRotate(node.left);
	return rightRotate(node);
}

 

참고 https://www.boostcourse.org/cs204

자바로 구현하고 배우는 자료구조