레드블랙트리 삭제 구현 주의사항 1 - DoubleBlack레드블랙트리의 5번째 특징을 고려하면경로로 뻗어가는 모든 경우에서 블랙 노드의 개수가 같아야 한다그러나 삭제가 발생하면 블랙노드의 개수가 달라질 수도 있다예를 들어, 위의 그림에서 20이 삭제되기 전에는모든 경로에서 블랙노드는 2개가 있다20이 삭제된 이후에는 왼쪽에서는 1개 오른쪽에서는 2개가 된다 이러한 상황에서 강제로 가상의 블랙을 현재 삭제한 노드에추가하면서 DoubleBlack 상황을 만든다그리고 이러한 DoubleBlack을 폭탄 돌리기처럼어떻게 이동시키고 해결할지에 초점을 맞춘다 레드블랙트리 삭제 구현 주의사항 2 - 삭제하는 경우 발생하는 case1번 case) 삭제할 노드가 Red인 경우해결법: 그냥 삭제하면 끝이다 2번 case..
균형이진탐색트리이진탐색트리의 문제점은 트리의 균형에 따라서최악의 경우 삽입/삭제/탐색에서 O(N)이 발생한다는 점이다이를 해결하기 위해 균형을 맞추는 대표적인 유형은AVL, 레드블랙트리, Treap이 있다대부분 stl에서는 레드블랙트리가 기본으로 사용된다 균형이진탐색트리 유형정리트리 종류탐색속도 (빠른 순)삽입/삭제 속도 (빠른 순)특징AVL 트리13가장 엄격한 균형, 빠른 탐색, 삽입/삭제 시 회전 연산 많음레드블랙트리22효율적인 균형, 적절한 탐색 및 삽입/삭제 성능, 가장 널리 사용됨Treap31무작위 우선순위, 삽입/삭제 빠름, 구현이 간단함, 평균적인 성능 좋지만 최악의 경우 존재AVL 트리는가장 엄격한 균형으로 인해 삽입/삭제 속도가 느린 것이 단점이다레드블랙 트리는균형 잡힌 성능을 제공하며 ..
이진탐색트리이진탐색에 최적화된 자료구조는 트리이다최대 자식을 두 개를 가질 수 있는 트리는 이진트리라고 한다이러한 이진트리를N의 왼쪽 서브트리에 있는 모든 노드의 값은 N의 값보다 작고N의 오른쪽 서브트리에 있는 모든 노드의 값은 N의 값보다 크다는탐색 속성을 만족시킨 것을 이진탐색트리라고 한다 이진탐색트리 시간복잡도균형이 안 맞는 경우에는삽입/삭제/탐색에서 최악인 O(N)이 발생할 수 있다반면, 어느 정도 균형이 맞혀진 경우에는삽입/삭제/탐색에서 O(logN)이 발생한다 전위/중위/후위 순회부모의 순서가 핵심이다전위순회는 부모노드 -> 왼쪽 자식 -> 오른쪽 자식중위순회는 왼쪽 자식 -> 부모노드 -> 오른쪽 자식후위순회는 왼쪽 자식 -> 오른쪽 자식 -> 부모노드 이진탐색트리 구현 주의사항- Max..
이진 탐색 개념정렬된 배열 상태에서처음부터 순회하며 탐색하는 방식이 아닌재귀적으로 절반을 기준으로 좌/우 중 하나를 선택하여탐색하는 것을 이진탐색이라고 한다따라서 시간복잡도는 O(logN)이 걸린다 이진 탐색의 문제배열로 이진탐색을 구현하는 경우는삽입, 삭제 시 매우 비효율적이다정렬된 연결리스트는 임의 접근이 불가능하기에이진탐색 사용이 불가능하다 이러한 문제를 해결하기 위해서배열이나 연결리스트가 아닌 새로운 자료구조인트리 구조를 이진탐색과 함께 이용한다 이진 탐색 구현 with 배열vector numbers;void BinarySearch(int N){ int left = 0; int right = (int)numbers.size() - 1; while (left numbers[mid]) { c..
다익스트라의 한계최단 거리를 찾기 위한 완전탐색에 가깝다그리고 가중치의 합만이 우선순위 조건으로 된다 A* 알고리즘일반적인 BFS, 다익스트라는시작점만을 기준으로 탐색을 진행했다반면, A* 길찾기 알고리즘은목적지를 추가해 해당 기준도 탐색한다는 것이다 다시 말해,기존 시작점 개념 뿐 아니라목적지라는 개념을 추가해서목적지와의 관계에서 우선순위 조건을 설정해거기에 맞게 탐색하는 것이 특징이다 최단거리는 보장되지 않지만목적지로부터의 특정 우선순위 조건을 자유자재로 설정 가능하다예를 들어정사각형 맵에서출발지가 왼쪽 상단이고 목적지가 오른쪽 하단인 경우,계속 탐색하면서 오른쪽 하단과 최대한 가깝게 길을 탐색하도록 하는경향 및 특징을 주입 가능하다 F = G + H 위의 기준을 설정하는 데 사용되는 개념은 "F ..
주의 사항힙트리에 대한 이론 필요https://motivelessstudy.tistory.com/573 우선순위 큐 구현template, typename Predicate = less>class MyPriorityQueue{public: void push(const T& data) { _heap.push_back(data); // 제일 마지막 위치 int now = static_cast(_heap.size()) - 1; // 루트 노드까지 반복 while (now > 0) { // 부모 노드와 비교해서 더 작은 or 큰 (Predicate에 따라) 경우 교체 int next = (now - 1) / 2; if (_predicate(_heap[now], _heap[next])) ..
이진트리각 노드가 최대 두 개의 자식 노드를 가지는 트리를 의미한다 이진탐색트리부모노드를 중심으로 좌측과 우측으로 구분되는 자식들이부모노드 값보다 작거나(좌측) 큰(우측) 규칙이 유지되는 이진트리를 의미한다 이진탐색트리 장, 단점장점:- 값의 탐색, 삽입, 삭제 모두 시간복잡도 O(logN)이 평균이다- 탐색 GOAT이다단점:- 트리의 높이 최적화가 안된 불균형 트리인 경우는시간복잡도가 O(N)이 걸릴 수도 있다이를 보완하기 위해서 균형이진탐색트리가 등장했다 힙트리부모 노드 값이 항상 자식 노드 값보다크거나(Max) 작은(Min) 특징을 지닌 트리이다위의 특징을 위해 노드들이 Swap을 진행하는 과정을 Heapify라고 한다참고로, 자식 노드들의 좌측 및 우측의 순서는 전혀 상관없다 힙트리 구조데이터가 ..
트리 개념트리는 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다그래프처럼 노드와 간선으로 구성되어 있지만계층적 구조를 갖는다는 점이 다르다 트리 관련 용어- Root: 가장 상위 노드- Parent Node: 특정 노드를 기준으로 상위에 있는 경우- Child Node: 특정 노드를 기준으로 하위에 있는 경우- Siblings: 특정 노드를 기준으로 하위에 있는 여러 Child Node들- Leaf Nodes: 자식이 없는 노드들- Subtree: 모든 트리는 트리의 재귀적인 구조로 각자 하위 트리들로 구성되어 있음을 의미- Level(Depth): Root부터 Level 0으로 시작하는 트리의 깊이를 의미- Height: 가장 깊은 노드의 깊이를 의미한다간선 기준으로는 가장 깊은 노드의 깊이노드..
주의사항- BFS의 한계가중치 그래프 적용이 불가능하다예를 들어, 미로에서 대각선 이동이 가능한 경우에는가중치가 필요하고 이를 구현하기는 불가능하다 - Dijkstra 한계 1BFS처럼 결국 완전탐색으로 동작한다 - Dijkstra 한계 2아래에서 Dijkstra를 구현하는 방식은 list를 활용한다모든 노드를 다 스캔해서 가장 최적을 고르는 방식을 채택한다그런데 우선순위 큐를 활용하면 이를 해결할 수 있다 - Dijkstra 준비물Vertex와 Cost를 합친 VertexCost 구조체를 생성한다map을 사용해서 생성하는 방법도 가능하다그리고발견목록을 저장할 discovered가장 최소거리를 저장할 best경로저장을 위한 parent가 필요하다 - Dijkstra 내부 동작BFS와 비슷한 느낌으로 동작..