개발공부 블로그

https://www.boostcourse.org/cs204 자료구조 강의를 듣고 정리한 내용입니다 레드 블랙 트리 색상 변환 -> 노드의 색을 바꾸는 것 색상변환을 하면 부모, 이모노드는 검은색 조부모 노드는 빨간색이 된다 회전을 하고나면 부모, 이모노드는 빨간색 조부모 노드는 검은색이 된다 레드 블랙 트리에서는 트리를 생성한 후 트리의 색을 파악하여 규칙을 어긴 것이 있는 지 확인한다 이때 해당 노드의 조부모 노드를 고쳐야한다 해당 노드를 고치는것이 아니다 레드 블랙 트리 코드 public void checkColor(Node node) { if(node == root) return; if(!node.black && !node.parent.black) //메서드를 호출하여 이모 노드의 색깔을 파악한다..

https://www.boostcourse.org/cs204 자료구조 강의를 듣고 정리한 내용입니다 adding data 균형이 맞아야한다는 규칙에 따른 트리 생성 어떤 종류의 회전을 했는지 기입하고 트리의 상태를 항상 그려야 한다 -> 트리가 균형이 맞는지 확인하는 과정에서 필요하다 트리의 균형을 맞추는 또 다른 방식 레드 블랙 트리 모든 노드를 빨강 또는 검정으로 설정한다 새로운 요소를 추가 할 때 마다 규칙을 확인한다 트리의 규칙(중요) 모든 노드는 빨간색이거나 검은색이다 루트는 항상 검은색이다 //아닐시 강제로 변환 새로 추가되는 노드는 항상 빨간색이다 //빨강 -> 검정 루트에서 잎 노드로 가는 모든 경로 (== 트리에서 만들 수 있는 모든 경로)는 같은 수의 검은색 노드가 있어야 한다 어떤 경..

AVL 트리 스스로 균형을 잡는 이진 트리 자료구조를 말한다. 왼쪽과 오른쪽의 높이 차이는 항상 1보다 작거나 같아야 한다 높이의 차이가 1보다 커지면 트리의 규칙을 어긴것이다 예시 1 4 (노드) 2 8 10 12 불안정 -> 조부모 노드인 8을 좌측 회전을 해야 한다 예시 1 회전 후 4 2 10 8 12 트리의 균형을 되찾음 예시 2 10 8 12 4 2 AVL 규칙에 어긋난다 -> 8에 대해서 우측 회전을 해야한다 회전 후 10 4 12 2 8 왼쪽 자식의 서브 트리에서 문제가 생긴 경우 조부모인 10이 좌측-우측회전을 해야한다 -> 문제 해결을 위해 회전을 해야한다 회전을 할 때는 루트로 올라가서 방금 한 회전이 트리 위쪽에 새로운 문제를 야기했는지 확인해야 한다 만약 문제가 발생시 고쳐야 한다..

트리의 회전 이진 트리의 시간 복잡도는 O(log n)이고 한쪽으로 치우친 트리는 O(n)이다 -> 이 차이점을 균형이라고 한다 //균형잡힌 트리 ->데이터를 효율적으로 관리하기 위해서 균형있는 트리를 만들어야 한다 트리는 최대한 균형 잡히게 만들기 위해서는 숫자들이 정렬되어있어야 한다 균형잡힌 트리를 만들기 위해 트리의 노드 위치를 변경하는 것을 회전이라고 한다 조부모, 부모, 자식 노드 크기 관계에 따라 우측 회전, 혹은 좌측 회전을 한다. 트리를 재정렬하면 항상 중간 크기의 요소가 가장 위에 있는 루트가 된다 회전 방법 불균형이 왼쪽 서브트리에서 나타나는 경우 크기 관계는 조부모 노드 > 부모 노드 > 자식 노드이다 우측 회전을 하여 조부모 노드를 오른쪽 자식 노드의 위치로 옮긴다 불균형이 오른쪽 ..

트리의 표현 * //root 2 3 의 트리가 있을 때 중위식 : 2 * 3 전위식 : * 2 3 후위식 : 2 3 * 트리의 규칙 부모를 기준으로 작은 것이 왼쪽에 와야 한다 연결리스트에서 노드가 next 포인터를 갖고있었던 것처럼 트리에서는 left, right 포인터를 갖는다 트리의 노드 클래스 class Node { E data; Node left, right; public Node(E obj) { this.data = obj; left = right = nll; } } 트리에 새로운 데이터를 추가하는 과정 루트에서부터 시작한다 트리의 규칙에 따라 내려간다 null인 부분을 찾았다면 그 곳에 새로운 노드를 추가한다 트리의 재귀함수 재귀 함수를 이용하여 트리의 규칙에 따라 내려가는 기능을 구현한다 ..

힙에서 요소를 제거 무언가를 제거할 때 힙에서는 항상 루트에 있는 요소를 제거해야 한다 트리의 마지막 요소를 루트에 넣는다 -> 최대 힙 규칙에 어긋남 -> 적절한 위치를 찾을 때까지 계속 두 노드의 위치를 바꾼다 ->두 자식 중 큰 노드와 교환하는 것이 포인트이다 (중요) 힙에서 제거할 수 있는 요소는 루트뿐이다 루트에 있는 요소를 지우면 구멍이 생기고, 이를 메워야 한다 -> 힙에있는 마지막 요소를 넣는다 ->자식 노드보다 작은지 확인 후 위치를 바꿔야 한다 자식 노드중에서 큰 수와 위치를 변경해야 한다 이러한 과정을 "trickle down"이라고 한다 trickle down 과정이 끝나는 경우 lastposition 변수보다 큰 경우 -> 현재 위치에서 자식 노드가 하나만 있을 수도 있다는 점을 ..

힙, 트리 트리 노드의 제일 위를 트리의 root라고 한다 자식이 딸려 있지 않은 부분은 leaves이다 탐색할때는 뿌리를 통해서 접근한다 간선 edge 두 노드를 연결하는 선 간선의 수에 따라 level을 나눈다 트리의 각각의 요소 : 노드 트리의 자료구조 Heap 규칙 1 부모 노드가 자식 노드보다 크다 -> 최대 힙 MAX HEAP 2 부모 노드가 자식 노드보다 작다 -> 최소 힙 Min HEAP 둘 중 어느 방법을 사용해도 무관하다 가장 큰 숫자가 뿌리에 있게 하려면 최대 힙, 가장 작은 숫자로부터 시작하려면 최소 힙을 사용하면 된다 트리에서의 높이 루트에서 가장 먼 잎까지 가는데 거치게 되는 간선의 개수이다 최대 힙에서 노드의 개수 n, level, height, log_2(n+1) -1log ..

add와 remove 메서드 해시를 추가하는 add 메서드 (boolean 반환) public boolean add(K key, V value) { //제네릭 타입 지정 x if(loadFactor() > maxLoadFactor) resize(tableSize * 2); //새로운 테이블의 크기를 계산 HashElement he = new HashElement(key, value); //새로 추가할 요소 생성 int hashval = key.hashCode(); //추가할 인덱스 탐색 hashval = hashval & 0x7FFFFFFF; hashval = hashval % tableSize; harray[hashval].add(he); //요소추가, 추가하는 방식은 상관 없다 numElements+..

재해싱 충돌을 피하기 위한 대표적인 방법으로는 해시 체인이 있다 -> 배열의 칸마다 리스트를 배정하는 방식 자료구조가 할당될수록 크기를 조정해야 한다 체인해시에서 해시가 너무 많이 할당되면 마찬가지로 크기 조정을 해야 한다 -> 새로운 해시로 모든 요소를 옮겨야 한다 객체를 해시에 추가하려면 우선적으로 hashCode 메서드를 호출해야 한다 int hv = x.hashCode(); hv = hv & 0x7FFFFFFF; hv = hv % tableSize; 다시 찾거나 제거하고자 할 때 위치 0의 연결리스트를 위치 0으로 옮기면 안된다 배열을 크기를 조정하면서 테이블의 크기가 바뀌었기 때문이다 ->각 요소의 위치를 초기화 한 후, 처음부터 다시 위치를 지정해야 한다 새로운 테이블에 빈 연결리스트를 만든 ..

해시충돌을 방지하기 위한 방법 1. 선형 조사법 2. 2차식 조사법 3. 이중 해싱 선형 조사법 찾고자 하는 값을 찾을 때까지 뒤로 간다 빈 공간을 찾을 때까지 자료구조를 살펴본다 자료구조가 차면서 추가된 객체를 찾기 위해 더 많은 칸을 살펴봐야 한다 요소를 제거 할 때 가운데에 있는 요소를 지우고자 할 때 이 요소를 제거하고 이 칸을 null로 설정하는 방식은 사용할 수 없다 -> 나중에 찾고자 하는 요소가 있을 때 중간에 null이 있을 때 null 뒤의 값을 찾을 수 없기 때문이다 어떤 요소가 존재했지만 비었다는 표시를 해야한다 해시값에서 시작해서 null에 도착할 때까지 1씩 더하고 그 위치에 저장한다 -> 추가보다는 제거가 까다롭다 관계가 있든 없든 데이터가 뭉치게 된다 -> 선형 조사법의 비효..