아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 완전 이진 트리(Complete binary tree) 마지막 줄을 제외한 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고, 마지막 줄은 왼쪽에서 오른쪽 순서로 채워져 있는 트리이다. 정 이진 트리(Full binary tree) 모든 잎이 아닌 노드가 2개의 자식 노드를 가지고 있고, 모든 잎이 같은 레벨에 있는 트리이다. (모든 노드가 0 개 또는 2개의 자식 노드만을 가짐) 트리 순회 전위 순회 (Pre order traversal) 1) 루트 노드에서 시작하여 2) 왼쪽 자식 노드에 갔다가 3) 오른쪽 자식 노드로 가는 순회 방법. 다른 모든 노드를 지나기 전에 루트 노드를 방문하기 때문에 전위(Pre order) 순회라고 한다. 중위..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 트리 순회 중위 순회 - 왼쪽, 루트, 오른쪽 순서로 순회 전위 순회 - 루트, 왼쪽, 오른쪽 순서로 순회 후위 순회 - 왼쪽, 오른쪽, 루트 순서로 순회 레벨 순회 - 레벨 순서대로 순회 TrickelUp 완전이진트리에서 레벨 순회식 노드의 위치는 다음과 같은 성질을 가진다. children - 2 * parent + 1 // 또는 // 2 * parent + 2 parent - floor(내림)( (child-1) / 2 ) 이진 힙을 코드로 구현하기 위해서는 배열(0~..)을 만들어 인덱스를 노드 위치로 하여 이러한 규칙을 사용할 수 있다. int lastposition; // 배열에서 어디까지 요소를 넣었는지 기록: 힙이 시작점에서 얼마나 떨..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 트리 (Tree) 가계도처럼 노드를 나무 형태로 연결한 비선형 자료구조를 트리라고 한다. 트리를 구성하고 있는 각각의 기본 요소는 노드로, 노드는 부모, 자식 형태로 이어진다. 루트 (root): 트리의 시작 부분. 부모가 없는 최상위 노드. 루트를 이용해 트리를 탐색한다. 리프, 단말노드 (leaf): 자식 노드가 없는 노드. 간선 (edge): 두 노드를 연결하는 선. 뿌리로부터의 간선의 수에 따라 level을 나눈다. ( 루트는 0 level) 형제 노드(sibling): 같은 부모를 가지는 노드. 힙 (Heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조이다. 힙에는 두 가지 규칙이 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. Resize 해시가 가득 차게되면 테이블의 사이즈를 더 크게 하여 새로운 배열을 만들어 다시 데이터를 넣어주어야 한다. = O(n) 일반적으로 원래 배열의 두 배의 크기로 만들게 된다. public void resize(int newSize){ // 새로운 체인 해시 생성
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. add, remove 해시에 요소를 추가하고 삭제하는 코드. 연결 리스트의 addFirst로 add한다. public boolean add(K key, V value){ if (loadFactor() > maxLoadFactor)// 적재율 확인 resize(tableSize*2);// resize 메소드 - 테이블 크기 2배로 늘이기 // 키와 값을 저장해 놓을 object he 정의 HashElement he = new HashElement(key, value); // he의 index 찾기 int hashval = key.hashCode(); hashval = hashval & 0x7FFFFFFF;// 양수만들기 hashval = hashval..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 재해싱 체인 해시에서도 해시가 너무 많이 찰 경우 크기 조정을 해야 한다. 해시의 크기 조정 과정을 재해싱이라고 한다. 일반적으로, 배열에서 적재율이 높아져 가득 차게 되면 배열의 크기를 두 배로 새로 만들어 모든 요소를 기존의 위치대로 옮긴다. 그러나 체인 해시에서는 이와 같이 이전 위치 그대로 요소를 옮기는 방식을 사용할 수 없다. 테이블의 크기를 키웠기 때문에, 다시 객체를 찾고자 할 때 해싱 과정에서 크기를 최적화하기 위해 테이블 크기만큼 %연산을 하게되면 다른 해시값이 나오기 때문이다. 따라서, 새 테이블에 연결 리스트를 만들어 첫 요소부터 시작하여 모든 요소마다 1. hashCode를 구하고 2. 양수로 변환한 뒤 3. 새 테이블 크기만큼..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. LoadFactor(적재율) 메소드 LoadFactor(적재율)는 해시에 데이터가 얼마만큼 있는지 알려주는 메소드이다. 배열의 크기에 비해 얼마정도 차 있는지를 알기 위합이다. 적재율은 자료 구조에 있는 항목 수를 자료 구조의 크기만큼 나눈 값으로, λ(람다)로 표기한다. (100 배열에 25칸 = 0.25λ) λ의 크기(0 - 비어있음 / 1/2 - 반 차있음 / 1 - 완전히 차 있음)에 따라 해시 테이블의 크기를 조절해야 한다. 해시 충돌을 해결하는 방식에 따라 적재율은 달라지기 때문에 충돌을 해결하는 것이 중요하다. 해시 충돌의 해결 방법 1. 개방 주소법 선형 조사법 (linear probing) 채우려는 공간이 이미 차 있다면, 비어있는 ..
