A* 알고리즘을 시각적으로 구현하였다. 맨하탄 방법으로 H를 계산하였고 대각선이동은 이동방향이 좌상단이라 예를들면 좌, 상에 방해물이 없는 경우에만 대각선 이동이 가능하다고 판단하였다.

반환값은 다음 이터레이터를 반환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 1..

ㅇ레드블랙 트리 삭제 레드블랙트리의 삭제는 기본적으로 이진탐색트리의 삭제방식을 사용한다. 이후에 삭제하고 나면, 무너진 레드블랙트리의 규칙을 복원하는 것에 초점을 둔다. 첫째로 삭제된 노드가 RED 인 경우 작업이 필요하지 않다. 왜냐하면 규칙이 무너지는 경우는 RED 노드가 연속적으로 부모 자식 관계인 경우인데 RED가 삭제되는 걸로는 해당 규칙을 벗어나지 않기 때문이다. 하지만 검은색 노드를 삭제하는 경우가 문제가 된다. ㅇ이진 탐색트리의 삭제 이진 탐색트리의 삭제작업은 우선 삭제할 노드를 탐색하는 과정이 끝나면, 세 가지 경우로 나뉜다. 1. 삭제할 노드가 단말노드인 경우 삭제할 노드가 단말노드인 경우에는 그 부모노드가 해당 노드로의 연결을 끊고 리프노드를 연결해 준다. 2. 삭제할 노드가 자식노드..

증가연산자의 경우에는 마지막 원소다음에는 end iterator를 반환하고 감소연산자의 경우에는 begin iterator를 감소하는 경우에는 assert 처리를 해주었다. 레드블랙트리에서의 삭제의 알고리즘이 복잡해서 더 공부하고 구현예정이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 RedBlackTree::iterator& RedBlackTree::iterator::..

다음 목표는 delete 구현이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #pragma once enum class COLOR { BLACK, RED, }; struct Node { int iKey; COLOR Color; Node* Parent; Node* LeftChild; Node* RightChild; Node(); ~Node(); }; class RedBlackTree { private: Node* Root; Node* Leaf; public: void insert(int _key); Node* fi..

레드블랙트리 이진탐색트리의 불균형한 성장은 검색효율이 최악의 경우 O(n) 이 발생한다. 이러한 불균형을 해결하기 위한 방법은 스스로 규형을 복원하는 것이다. 레드 블랙트리의 균형 복원 규칙 1. 모든 노드는 빨간색 아니면 검은색이다 2. 루트노드는 검은색이다. (루트노드 =가장 상위노드) 3. 리프노드는 검은색 (리프노드 =자식노드가 없는 노드) 4. 빨간 노드의 자식들은 모드 검은색, 하지만 검은색 노드의 자식은 빨간색일 필요는 없다. 5. 루트노드에서 리프노드까지 사이에 있는 검은색 노드의 수는 모두 동일 NIL 노드는 아무 데이터도 가지고 있지 않는 더미노드이고 NIL노드의 색깔은 검은색으로 취급한다. 레드 블랙트리의 회전 레드블랙트리가 균형을 회복하기위한 연산과정 중 회전을 한다 회전은 좌회전,..