방앗간

※ 트리: 노드 클래스 - 트리에서는 엄마 노드보다 작은 데이터가 왼쪽 자식 노드에 와야 하고 엄마 노드보다 큰 데이터가 오른쪽 자식 노드에 와야 한다. 그래서 어떤 수를 찾고자 할 때 엄마 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동하게 된다. 전체 데이터의 반은 무시하고 logn의 복잡도를 가진다. 연결 리스트에서 노드가 next 포인터를 갖고 있던 것 처럼, 트리에서는 노드가 left, right 포인터를 갖는다. 노드 클래스를 코드로 표현하면 다음과 같다. class Node{ E data; Node left, right; public Node(E obj){ this.data = obj; left=right=null; } }

※ 트리: 표현 - 표현식 트리를 활용해 복잡한 식도 트리 형식으로 표현할 수 있다. 중위 표기식: 2 * 3 (LNR) 후위 표기식: 2 3 * (LRN) 전위 표기식: * 2 3 (NLR)

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

※ 완전 트리와 정 트리 - Complete Tree(완전트리): 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고 마지막 줄은 좌측에서 우측으로 채워진 상태의 트리이다. Full Tree(정 트리): 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 모든 잎이 같은 레벨에 있는 트리이다.

※ 힙: 정렬 - 힙 규칙에 맞게 숫자의 순서를 재구성 하는 과정을 힙 정렬 알고리즘이라고 한다. 임의의 숫자들을 나열하고 힙 규칙에 맞게 TrickleDown을 반복하면 숫자들이 정렬된다. 힙 정렬 알고리즘의 시간 복잡도는 O(nlogn)이다. 각 수를 비교해 하나를 고르는 방식으로 숫자를 골라내기 때문이다. 총 n 개의 숫자를 logn개의 숫자와 비교함 숫자들의 순서를 바꾸어 정렬하기에 데이터의 복사본을 만들 필요가 없다는 것이 힙 정렬의 장점이다.

※ 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)array[parent]).compareTo(array[left])= lastpositon) return; ..

※ 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 = a..

※ 힙: 추가와 제거 - 힙에 새로운 데이터를 추가하거나 제거할 때 힙의 규칙을 지켜야 한다. 최대 힙이면 부모 노드가 자식 노드보다 커야 최소 힙은 자식 노드가 부모 노드보다 커야한다. 노드 추가 1. 비어있는 공간에 노드 추가 2. 부모 노드보다 큰 숫자인지 확인 후 참인 경우 두 노드의 위치를 바꾼다. (trickle up) 루트 제거 1. 루트를 제거한다 2. 트리의 마지막 요소를 루트에 넣어준다 3. 루트에서 시작해 두 자식 중 큰 노드와 바꿔 힙의 규칙을 만족하게 한다. (tricle down) 무언가를 제거할 때 힙에선 항상 루트를 제거해주어야 한다.

※ Tree Levels - 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조 이다. 힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있다. 부모 노드가 자식 노드보다 크면 최대 힙이고 반대라면 최소 힙이다. 가장 큰 숫자가 뿌리에 있도록 하려면 최대 힙, 가장 작은 숫자부터 시작하려면 최소 힙을 사용하면 된다. 요약) parent > children => Max Heap parent Min Heap

※ 힙과 트리 - 가계도처럼 노드를 나무 형태로 연결 구조를 트리라고 한다. 트리에 있는 각각의 요소는 노드이다. 노드는 부모, 자식 형태로 이어진다. 뿌리(root): 트리의 시작 부분으로 뿌리를 통해 들어가 트리를 탐색한다. 잎(leaf): 자식이 딸려있지 않은 부분입니다. 간선(edge): 두 노드를 연결하는 선입니다.