Archived(CSE Programming)/자료구조(C++) (16) 썸네일형 리스트형 레드블랙 트리(Red Black Tree) (변형이진탐색트리) 레드 블랙 트리는 효율적인 탐색을 위해 BST의 height를 낮추는방식으로 고안된 트리이다.다음의 3 가지 조건을 만족해야 한다. 루트 노드와 외부 노드는 Black 노드이다Red 노드가 연속해서 올 수 없다루트로부터 외부 노드로 까지의 가는 경로에서 count 되는 Black 노드의 수는 같다 (최대 경로는 최소 경로의 두배 이하이다) 그리고 이러한 조건을 만족시키기 위해 삽입 시에는 Red 노드로 삽입을 고정시키는 것이 유리하다(블랙 노드로 삽입시 조건 3을 위배시키기 쉬워서 이런 경우에는 복잡한 처리를 수행해야 하기 때문) Red 노드로 삽입 후에는 조건 2만 체크를 하면 된다. 조건 2를 만족시키기 위해 4가지 Case가 있는데 다음과 같다.(right에 삽입되었을 경우를 합치면 총 8가지 ca.. AVL Tree(변형 이진탐색트리) AVL Tree 이진탐색트리(BST, Binary Search Tree)의 효율성은 최대한의 높이(height)를 낮추는 것에 있다. 탐색, 삽입, 삭제와 같은 연산 시의 시간복잡도는 O(h)일 만큼 height에 달려있기에 height를 낮추는 것이 이진탐색트리의 효율성을 높이는 방법이 될 수 있다. 그래서 이진탐색트리(이하 BST)의 효율성을 최대로 살리기 위해 height를 낮추는 방법 중 가장 대표적인 방법으로 AVL 트리를 들 수 있다. 초기에 제안되었던 방식으로 G.M. Adelson-Velskii와 E.M. Landis가 자신들의 이름을 따서 AVL Tree로 명하였다. 핵심은 높이를 낮추는 것으로 Balanced Factor(bf, 또는 높이)를 비교하여 좌측 서브트리와 우측 서브트리의 높.. 이진탐색트리(Binary Search Tree, BST) 이진탐색트리(BST) 이진탐색트리는 트리의 대표적인 형태로 말 그대로 이진트리 중에서도 탐색에 특화된 트리이다. 탐색에 특화된 이유는 트리 내부 부모노드의 값은 왼쪽 자식노드의 값보다 크고 오른쪽 자식노드의 값보다 작다는 특성을 지니고 있기 때문이다. 그래서 실제 값이 들어있는 이진탐색트리를 살펴보면 아래와 같다. 이 트리를 전위순회방식으로 탐색하면 "1 3 4 6 7 8 10 13 14" 로 값을 오름차순으로 출력할 수 있다. 즉 아까의 특성 때문에 값을 찾기 쉽기 때문에 이진탐색트리라고 한다. 이진탐색트리는 Node와 NodePointer를 통해서 구현할 수 있는데, 아까의 특성을 지키기 위해 아래의 로직으로 구현할 수 있다. 삽입은 삽입하고자 하는 값이 부모노드보다 작으면 왼쪽 자식노드로, 크면 오.. 우선순위 큐(Priority Queue) / 힙(Heap) 우선순위 큐(Priority Queue) 우선순위 큐는 말 그대로 Queue 중에서도 특별한 Queue이다. 우선순위를 가지는 큐로써, 가장 우선순위가 높은 자료가 가장 먼저 출력되는 구조를 지닌다. 아래처럼, 완전히 정렬된 형태는 아니지만 출력은 언제나 우선순위가 가장 높은 자료형이 반환된다. 따라서, 출력될 때 우선순위가 가장 높은 자료가 나올 수 있도록 삽입, 삭제가 이루어져야 한다. 삽입과 삭제의 연산에서 많은 연산들이 소모되어서 비효율적으로 보일 수 있지만 언제나 우선순위가 높은 자료형을 O(1)로 꺼낼 수 있기에 이러한 자료형이 필요시 될 때도 있다. 구현 방법에는 다양한 방법이 있지만 Heap을 통해서 우선순위 큐를 구현하는 것이 가장 이상적이다. 아래의 두가지를 만족하는 자료형을 Heap이.. 스택(Stack)과 큐(Queue), 순환 큐(Circular Queue) 스택(Stack) 스택(Stack)은 LIFO(Last In First Out)을 표현하는 대표적인 선형 자료구조 이다. 나중에 입력한 값이 먼저 출력되는 구조이다. 그래서 일반적인 스택은 top이라는 하나의 공간을 통해 입출력이 일어난다. 배열을 통해서 많이 표현하는데 아래와 같이 표현할 수 있다. 위와 같이 top이라는 하나의 공간을 통해 값을 입력, 출력한다. 삽입은 top이 가르키는 공간의 다음 공간으로 이동하여 삽입한다. 삭제는 top이 가르키는 공간의 자료를 꺼낸뒤 top은 이전 공간으로 이동한다. top이 -1일 경우 STACK은 비어있는 상태이다. top이 배열의 마지막 공간을 가르키고 있을 경우 STACK은 가득찬 상태이다. 스택(Stack) 구현 #include #define MAX_S.. 우선순위 큐_대칭 최소최대 힙(Symmetric min max heap) 우선순위 큐_대칭 최소최대 힙(Symmetric min max heap) Symmetric min max heap 은 root가 비어있고 루트 lch에는 가장 작은 값이 루트 rch에는 가장 큰 값이 있어서우선순위의 최소 최대를 편하게 접근할 수 있는 완전 이진 트리(CBT)이다. 조건은 크게 3가지이다.1. 각 노드의 원소는 오른쪽 형제보다 작거나 같다.2. 조부모를 가진 노드 N -> 조부모의 rch > N3. 조부모를 가진 노드 N -> 조부모의 lch < N 이러한 조건을 만족시키는 대칭 최소최대 힙을 삽입하는 과정은 다음과 같다. * 먼저 해당 위치에 E라는 임의 노드를 삽입.그리고 조건 1을 체크를 한다(왼쪽 형제로 가서 값 비교, 오른쪽 형제로 가서 값 비교) * 그리고 부모의 손자노드들로 .. 우선순위 큐_피보나치 힙(Fibonacci Heap) 피보나치 하면 수열이 가장 먼저 떠오르는데 이 수열의 개념이 힙이 결합하는 과정과 유사하여피보나치 힙이라고 불린다. 피보나치 힙은 각 힙들을 doubly circular linked list 형태로 구성되는데피보나치 힙은 삽입의 과정을 거치면 이항 힙과 유사한 형태로 계속 같은 level의 min으로 추가 한다.추가하면서 계속 min을 체크함. * node * fb[MAX]의 노드포인터 배열을 선언하고그리고 최소 값을 반환하는 순간 모양이 재조정되는데, 최소값을 가진 heap의 루트가 반환되고, 해당 heap의자식노드들을 포인터로 기존 min level과 연결한다. * 그리고 가장 최근에 삽입한 heap의 내부노드 수를 판단하여해당 내부노드 수 값의 index에 해당 heap을 삽입한다. * 그리고 다음.. 자료구조 프로그래밍 Lab09) Patricia 만들기 자료구조 프로그래밍 Lab09) Patricia 만들기 문제 해결 구현 알고리즘은 탐색 / 삽입 두가지로 나뉜다 탐색.0) t tree가 NULL 이면 탐색 실패1) tree의 nextNode에 lch를 가져오고 current node에 현재 트리 t를 가져온다2) bitNumber가 더 클 동안 계속 이동한다(bitNumber가 0이면 왼쪽, 값이 있으면 오른쪽 으로 이동)3) nextnode를 반환 삽입.0) t tree가 NULL이면 해당 노드에 값을 할당 후 종료1) tree를 search 해서 값이 똑같으면 삽입 실패(이미 존재하는 값)2) tree를 탐색하는 알고리즘을 통해서 탐색을 한 다음3) 새로운 노드를 할당한 후에, 현재 노드가 부모 노드의 lch라면 부모노드의 lch에 새노드 할당, .. 이전 1 2 다음
