AVL 트리

Data Structure · 2024-07-07

이진 트리

Binary Tree Tree란 노드의 집합에 의한 계층적 자료구조입니다. 각 노드들은 데이터 값과 자식 노드라고 칭하는 노드들의 포인터 값을 가집니다. 그리고 자신의 포인터 값을 가지고 있는 노드를 부모노드라고 합니다. 트리의 각 노드는 세 가지로 분류될 수 있습니다. 루트 노드 ( Root Node ) : 부모노드를 갖지 않는 경우 말단 노드 ( Leaf Node ) : 자녀노드를 갖지 않는 경우 내부 노드 ( Internal Node ) : 위의 두 경우를 제외한 경우 그리고 자신과 같은 부모 노드를 가지고 있는 노드들을 형제 ( Sibling ) 노드 라고 합니다. 차수 ( Degree, = d ) : 자식 노드의 개수 Level ( = Height ) : 루트 노드는 0 또는 1부터 시작하여, 자식노드는 부모노드보다 1을 더한 값을 얻는다. 이진 트리 ( Binary Tree ) 이진 트리 ( Binary Tree )는 차수가 2 이하인 트리를 말합니다. 그 안에도 여러 종류가 있습니다. 편향 이진 트리 ( Skewed Binary Tree ) 말단 노드를 제외한 모든 노드가 오직 한개의 자식 노드를 갖는 트리를 말합니다. Degenerate Tree 라고도 합니다. 이 경우엔 연결리스트와 같은 기능을 가집니다. 정 이진 트리 ( Full Binary Tree ) 말단 노드를 제외한 모든 노드의 차수가 0 또는 2인 트리를 말합니다. 완전 이진 트리 ( Complete Binary Tree ) 말단 노드를 제외한 모든 노드의 차수가 2인 트리를 말합니다. 또한 마지막 레벨을 제외한 모든 레벨이 채워져 있어야 합니다. 즉, 말단 노드들의 레벨 차이는 최대 1 입니다. 말단 노드들은 트리에 채워질 때, 왼쪽부터 채워집니다. 포화 이진 트리 ( Perfect Binary Tree ) 완전 이진 트리에서 마지막 레벨이 모두 채워진 경우를 포화 이진 트리라고 합니다. 즉, 모든 말단 노드의 레벨이 같습니다. 이진 탐색 트리 (Binary Search Tree, BST) 이진 탐색 트리는 이진 탐색 알고리즘을 트리에 접목시킨 것입니다. 각 노드의 데이터보다 작은 값은 왼쪽 부분 트리로, 큰 값은 오른쪽 부분 트리로 저장됩니다. 특정 값 n을 찾을 때, 현재 노드의 데이터보다 작다면 왼쪽 자식 노드, 크다면 오른쪽 자식 노드로 이동해서 재귀적으로 진행되기 때문에, 이진 탐색과 같이 삽입, 삭제, 탐색 연산이 모두 $O(log_2N)$이 됩니다. 탐색 연산 find “key” 루트 노드부터 탐색을 시작합니다. 노드의 값 == key 이면, 탐색 성공, 종료 노드의 값 < key 이면, 왼쪽 자식 노드로 이동 노드의 값 > key 이면, 오른쪽 자식 노드로 이동 이 과정을 반복하였을 때, 마지막에 key 값과 같은 값을 가진 노드가 존재하지 않다면 탐색 실패로 종료됩니다. 삽입 연산 insert “key” 삽입 연산이 이루어지기 위해서 탐색 연산을 시작합니다. 탐색이 종료되는 경우, 탐색이 종료된 위치에 키 값을 삽입합니다. 삭제 연산 delete “key” 탐색 연산을 시작합니다. 탐색이 실패하면 어떠한 행동도 취하지 않습니다. 탐색이 성공하면 해당 노드를 삭제합니다. 해당 노드가 말단 노드인 경우 : 해당 노드를 삭제합니다. 해당 노드가 하나의 자식 노드를 가지는 경우 : 해당 노드를 삭제하고, 자식 노드로 이를 대체합니다. 해당 노드가 두개의 자식 노드를 가지는 경우 : 해당 노드를 삭제하고, 다음 중 하나의 노드를 골라 이를 대체합니다. 왼쪽 부분 트리에서 가장 큰 값을 가지는 노드 오른쪽 부분 트리에서 가장 작은 값을 가지는 노드 이제 BST를 구현해보도록 하겠습니다. code #include<iostream> #include<ostream> #define inorder 0 #define preorder 1 #define postorder 2 using namespace std; class Underflow {}; template <typename T> class Node { public: T data; Node<T> *left, *right; Node<T>() : left(nullptr), right(nullptr) {} Node<T>(T value) : data(value), left(nullptr), right(nullptr) {} }; template <typename T> class BinaryTree { public: int size; Node<T> *root; BinaryTree<T>() : size(0) , root(nullptr) {} void insert(T value){ insertNode(value, root); size++; } bool search(T value){ return searchNode(value, root); } void remove(T value){ try{ if(size <= 0) throw Underflow(); removeNode(value, root); size--; cout << "\nremoved " << value << '\n'; } catch(Underflow e){ cout << "underflow occurs" << '\n'; exit(0); } } void print(int N){ if(N == inorder){ cout << "inorder : "; inOrder(root); } else if(N == preorder){ cout << "preorder : "; preOrder(root); } else if(N == postorder){ cout << "postorder : "; postOrder(root); } cout << '\n'; } private: void insertNode(T value, Node<T> *&currentNode){ if(currentNode == nullptr) currentNode = new Node<T>(value); else{ if(value <= currentNode->data) insertNode(value,currentNode->left); else insertNode(value, currentNode->right); } } bool searchNode(T value,Node<T> *current){ if(current->data == value) return 1; if(value < current->data) searchNode(value, current->left); else searchNode(value,current->right); return 0; } void getleftMost(Node<T> *&current){ Node<T> *ptr = current->left, *prev = current; while(ptr->right != nullptr){ prev = ptr; ptr = ptr->right; } prev->right = nullptr; current->data = ptr->data; delete ptr; } void removeNode(T value, Node<T> *&current){ if(current != nullptr){ if(value < current->data) removeNode(value,current->left); else if(value > current->data) removeNode(value,current->right); else if (value == current->data){ if(current->left == nullptr){ Node<T> *ptr = current; current = current->right; delete ptr; } else if(current->right == nullptr){ Node<T> *ptr = current; current = current->left; delete ptr; } else{ getleftMost(current); } } } } void inOrder(Node<T>* current){ if(current != nullptr){ inOrder(current->left); cout << "[ " << current->data << " ] "; inOrder(current->right); } } void preOrder(Node<T>* current){ if(current != nullptr){ cout << "[ " << current->data << " ] "; preOrder(current->left); preOrder(current->right); } } void postOrder(Node<T>* current){ if(current != nullptr){ postOrder(current->left); postOrder(current->right); cout << "[ " << current->data << " ] "; } } }; int main(){ BinaryTree<int> test; int k[] = {3, 9, 4, 1, 10, 5, 9, 10, 7, 2}; for(int i = 0; i < 10; i++) test.insert(k[i]); test.print(inorder); test.print(preorder); test.print(postorder); test.remove(3); test.print(inorder); test.print(preorder); test.print(postorder); return 0; } 코드 내에서는 빈 트리에 3, 9, 4, 1, 10, 5, 9, 10, 7, 2를 순서대로 삽입을 진행합니다. 그 과정은 다음과 같습니다. 여기서 inorder, preorder, postorder가 있는데, 이는 이진 트리 순회 방법입니다. 특정한 순서로 각 노드를 방문하여 최종적으로 트리의 모든 노드를 방문하는 방법을 말합니다. inorder traversal : 왼쪽 자식 노드, 자신, 오른쪽 자식 노드의 순서로 순회하는 방법입니다. preorder traversal : 자신, 왼쪽 자식 노드, 오른쪽 자식 노드의 순서로 순회하는 방법입니다. postorder traversal : 왼쪽 자식 노드, 오른쪽 자식 노드, 자신의 순서로 순회하는 방법입니다. result inorder : [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 7 ] [ 9 ] [ 9 ] [ 10 ] [ 10 ] preorder : [ 3 ] [ 1 ] [ 2 ] [ 9 ] [ 4 ] [ 5 ] [ 9 ] [ 7 ] [ 10 ] [ 10 ] postorder : [ 2 ] [ 1 ] [ 7 ] [ 9 ] [ 5 ] [ 4 ] [ 10 ] [ 10 ] [ 9 ] [ 3 ] removed 3 inorder : [ 1 ] [ 2 ] [ 4 ] [ 5 ] [ 7 ] [ 9 ] [ 9 ] [ 10 ] [ 10 ] preorder : [ 2 ] [ 1 ] [ 9 ] [ 4 ] [ 5 ] [ 9 ] [ 7 ] [ 10 ] [ 10 ] postorder : [ 1 ] [ 7 ] [ 9 ] [ 5 ] [ 4 ] [ 10 ] [ 10 ] [ 9 ] [ 2 ] 예시로 보여드린 트리의 구조가 매우 비효율적입니다. 이러한 구조의 트리의 경우, 삽입, 삭제, 탐색 연산의 시간 복잡도가 증가하게 됩니다. 이러한 문제에 대한 해결 방안으로 Height Balanced Tree 중에서, AVL Tree와 Red-Black Tree에 대해서 알아보도록 하겠습니다. 물론 내일..

Data Structure · 2024-07-05

스택, 큐

Stack Stack은 FILO(First In Last Out) 형식의, 가장 먼저 추가된 데이터가 가장 나중에 삭제되는 자료구조입니다. 헬스를 하면서 바벨에 원판 끼우고 뺄 때, 가장 나중에 넣은 원판을 가장 먼저 빼는 것, 이것이 스택 자료구조라고 보면 됩니다. 스택은 프로세스 메모리 상에서 임시 로컬 데이터를 저장하는데 쓰이기도 합니다. 예를 들어 C++ 프로그램을 실행하면 코드 내 함수 파라미터, 지역 변수, 리턴 값 등이 이 스택 자료구조에 저장됩니다. 스택에는 push 연산과 pop 연산이 있는데, push 연산은 마지막에 노드를 추가하는 연산이고, pop은 가장 마지막 노드를 제거하는 연산입니다. 스택은 보통 배열 또는 연결리스트를 통해서 구현을 합니다. by Linked List code #include<iostream> #include<ostream> #define MAX 10 class Underflow {}; using namespace std; template <typename T> class Node { public: T data; Node<T> *next; Node<T>() : next(nullptr) {} Node<T>(T value, Node<T>* next1) : data(value), next(next1) {} }; template <typename T> class Stack { public: int length; Node<T> *top; Stack<T>() : length(0), top(nullptr) {} bool empty(){ return (length ? false : true); } void push(T value){ top = new Node<T>(value, top); length++; } T pop(){ try{ if(length == 0) throw Underflow(); T returnValue = top->data; Node<T> *ptr = top; top = top->next; delete ptr; length--; return returnValue; } catch(Underflow e){ cout << "Underflow occurs" << '\n'; exit(0); } } ~Stack<T>(){ Node<T> *ptr = top, *prev; while(ptr != nullptr){ prev = ptr; ptr = ptr->next; delete prev; } } }; template <typename T> ostream& operator<< (ostream& scan, Stack<T> &inputArr){ Node<T> *ptr = inputArr.top; while(ptr != nullptr){ scan << "[ " << ptr->data << " ]-"; ptr = ptr->next; } scan << "[ NULL ]" << '\n'; } int main(){ Stack<int> test; int k = 4; for(int i = 0; i < MAX; i++) test.push(k++); cout << test; test.pop(); cout << test; return 0; } result [ 13 ]-[ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ] [ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ] by Array code #include<iostream> #include<ostream> #define MAX 10 class Underflow {}; using namespace std; template <typename T> class Stack { public: int length; int top; T* arr; Stack<T>() : length(0), top(-1) {} Stack<T>(int size) : length(size), top(-1) { arr = new T(size); } ~Stack<T>(){ delete[] arr; } bool empty(){ return (length ? false : true); } bool full(){ return (top == length - 1 ? true : false); } void push(T value){ if(full()){ T* newArr = new T[length + MAX]; for(int i = 0; i < length; i++) newArr[i] = arr[i]; delete[] arr; arr = newArr; } arr[++top] = value; } T pop(){ try{ if(top < 0) throw Underflow(); return arr[top--]; } catch(Underflow e){ cout << "underflow occurs" << '\n'; exit(0); } } }; template <typename T> ostream& operator<< (ostream& scan, Stack<T> &inputArr){ for(int i = inputArr.top; i >= 0; i--) scan << "[ " << inputArr.arr[i] << " ]-"; scan << "[ NULL ]" << '\n'; } int main(){ Stack<int> test; int k = 4; for(int i = 0; i < MAX; i++) test.push(k++); cout << test; test.pop(); cout << test; return 0; } result [ 13 ]-[ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ] [ 12 ]-[ 11 ]-[ 10 ]-[ 9 ]-[ 8 ]-[ 7 ]-[ 6 ]-[ 5 ]-[ 4 ]-[ NULL ] Queue Queue는 FIFO (First In First Out) 의 형태로, 가장 먼저 추가된 노드가 가장 먼저 삭제되는 자료구조이다. 도로 신호등에 걸린 차량들을 생각해보았을 때, 신호등이 초록불이 되면 먼저 도착해 정지했던 차량이 먼저 출발하는데, 큐가 이러한 구조로 되어있다. 큐는 enqueue와 dequeue 연산이 있는데, enqueue는 가장 마지막에 새로운 노드를 추가하는 연산이고, dequeue는 가장 앞에 있는 (가장 먼저 추가됐었던) 노드를 삭제하는 연산이다. 이러한 큐 자료구조는 한 예로 실행가능한 상태의 프로세스들이 CPU 자원을 할당받고자 대기 중일 때, 이러한 큐 자료구조 형태로 저장된다. By Linked List code #include<iostream> #include<ostream> #define MAX 10 class Underflow {}; using namespace std; template <typename T> class Node { public: T data; Node<T> *next; Node<T>() : next(nullptr) {} Node<T>(T value, Node<T> *next1) : data(value), next(next1) {} }; template <typename T> class Queue { public: int length; Node<T> *front, *rear; Queue<T>() : length(0), front(nullptr), rear(nullptr) {} ~Queue<T>(){ Node<T> *ptr = front,*prev; while(ptr != nullptr){ prev = ptr; ptr = ptr->next; delete prev; } } bool empty() {return (length? false : true);} void enqueue(T value){ if(length == 0) front = rear = new Node<T>(value, nullptr); else{ rear->next = new Node<T>(value, nullptr); rear = rear->next; } length++; } T dequeue(){ try{ if(empty()) throw Underflow(); Node<T> *ptr = front; T returnValue = ptr->data; front = front->next; delete ptr; length--; return returnValue; } catch(Underflow e){ cout << "underflow occurs" << '\n'; exit(0); } } }; template <typename T> ostream& operator<< (ostream& scan, Queue<T>& inputQueue){ Node<T> *ptr = inputQueue.front; scan << "front-"; while(ptr !=nullptr){ scan << "[ " << ptr->data << " ]-"; ptr = ptr->next; } scan << "rear" << '\n'; } int main(){ Queue<int> test; int k = 3; for(int i = 0; i < MAX; i++) test.enqueue(k++); cout << test; test.dequeue(); cout << test; return 0; } result front-[ 3 ]-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear By Array 큐의 한 형태로 원형 큐 (Circular Queue)가 있는데, 이는 배열을 통해 큐를 구현하였을 때, 배열의 크기는 고정된다는 특징으로 저장 공간이 부족하다는 단점을 해결한 형태의 큐입니다. enqueue rear 인덱스 값에 1을 더해 업데이트하고, rear 인덱스 값에 데이터를 삽입합니다. 만약 rear의 인덱스 값이 배열의 크기 이상이 되면 rear 값을 0으로 초기화합니다. dequeue 배열의 front 인덱스에 해당하는 데이터을 리턴하고, front 인덱스 값에 1을 더해 업데이트 합니다. enqueue의 rear와 마찬가지로 front 값이 배열의 크기 이상이 되면 rear 값을 0으로 초기화합니다. code #include<iostream> #include<ostream> #define MAX 10 using namespace std; class Underflow {}; class Overflow {}; template <typename T> class Queue { public: int length; int front,rear; T *arr; Queue<T>() : length(0), front(-1), rear(-1) { arr = new T[MAX]; } ~Queue<T>(){ delete[] arr; } bool full(){ return (length == MAX ? 1 : 0); } bool empty(){ return (length? 0 : 1); } void enqueue(T value){ try{ if(full()) throw Overflow(); rear++; if(rear >= MAX) rear %= MAX; if(length == 0) front = rear; arr[rear] = value; length++; } catch(Overflow e){ cout << "overflow occurs" << '\n'; exit(0); } } T dequeue(){ try{ if(empty()) throw Underflow(); T returnValue = arr[front]; if(front == rear) front = rear = -1; else front++; if(front >= MAX) front %= MAX; length--; return returnValue; } catch(Underflow e){ cout << "underflow occurs" << '\n'; exit(0); } } }; template <typename T> ostream& operator<<(ostream& scan, Queue<T>& inputQueue){ scan << "front-"; int idx = inputQueue.front; while(1){ scan << "[ " << inputQueue.arr[idx] << " ]-"; if(idx == inputQueue.rear) break; idx++; if(idx >= MAX) idx %= MAX; } scan << "rear" << '\n'; } int main(){ Queue<int> test; int k = 3; for(int i = 0; i < MAX; i++) test.enqueue(k++); cout << test; test.dequeue(); cout << test; test.enqueue(k); cout << test; return 0; } result front-[ 3 ]-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-rear front-[ 4 ]-[ 5 ]-[ 6 ]-[ 7 ]-[ 8 ]-[ 9 ]-[ 10 ]-[ 11 ]-[ 12 ]-[ 13 ]-rear Queue By Two Stack 두개의 스택을 통해서 큐를 구현할 수 있습니다. 기본적으로 데이터가 저장되는 스택1과 dequeue 작업을 위해 데이터를 임시적으로 저장할 스택2가 필요한데, enqueue연산의 경우 스택1에 push 연산을 통해 스택의 경우와 똑같이 저장합니다. dequeue연산을 위해서는 가장 밑에 있는 데이터를 추출해야 하는데, 스택의 경우, FILO 구조로 가장 위의 있는 데이터가 먼저 추출될 수 밖에 없다. 여기서 임시 저장소 스택2가 사용되는데, 먼저 스택1에 저장된 데이터들을 가장 밑에 있는 데이터가 나올 때까지 pop 연산을 진행합니다. 그리고 각 연산마다 추출되는 데이터를 스택2에 그대로 push 연산을 진행합니다. 그러면 마지막엔 스택2에는 가장 밑에 있던 데이터를 제외한 나머지 노드들이 삽입된 순서의 반대로 저장되어있을텐데, 밑에 있던 데이터를 추출한 후, 스택2 안에 데이터가 모두 사라질 때까지 pop연산을 진행하고, 연산을 통해 추출된 데이터들을 다시 스택1에 push 연산을 진행합니다. 스택1에서 pop 연산 진행 추출된 데이터를 스택2에 push 연산 진행 1,2 단계를 스택1의 가장 밑에 있는 데이터가 추출될 때까지 진행 목표 데이터 추출 스택2에서 pop연산 진행 추출된 데이터를 스택1에 push연산 진행 5,6 단계를 스택2에 아무 데이터도 남지 않을 때까지 진행 마찬가지로 스택 또한 두개의 큐를 통해서 구현할 수 있습니다.

Data Structure · 2024-07-04

연결 리스트

블렌더 모델링 너무 힘들어서 머리 좀 식히고자 복습할 겸 작성합니다.. Linked List 연결리스트는 각 노드가 연속되어 저장되는 배열과 달리, 각 노드들의 위치가 연속되지 않지만, 각자 다음 노드의 위치 정보를 함께 저장하여 연결되는 자료구조입니다. 각 노드는 데이터와 다른 노드에 대한 포인터가 저장된다. 연결리스트는 노드의 추가, 삭제에 있어서 특정 노드들의 연결만 업데이트하면 되므로 배열보다 월등히 빠르다. 그러나 특정 노드에 접근하기 위해서는 첫 노드로부터 순차적으로 접근해야하기 때문에 리스트의 노드 수에 따라서 선형적이며, 특정 노드와의 연결이 끊어지게 되는 경우, 끊어진 노드와 연결된 다른 노드들의 정보도 잃어버린다는 단점이 있다. Singly Linked List Singly Linked List는 단순히 각 노드가 다음 노드의 포인터만을 가지고 있는 연결 리스트이다. 이는 운영체제의 파일 시스템에서 연속 할당 (Contiguous Allocation) 방식에서 사용되기도 한다. code #include<iostream> #include<ostream> #define MAX 10 using namespace std; class InvalidIndex {}; class Underflow {}; template <typename T> class Node{ public: T data; Node<T> *nextNode; Node<T>() : nextNode(nullptr) {} Node<T>(T value, Node<T> *next1) : data(value), nextNode(next1) {}; ~Node<T>(){ nextNode = nullptr; } }; template <typename T> class LinkedList{ public: int length; Node<T> *head; LinkedList() : length(0), head(nullptr) {} ~LinkedList(){ Node<T> *ptr1 = head, *ptr2; while(ptr1 != nullptr){ ptr2 = ptr1; ptr1 = ptr1->nextNode; delete ptr2; } } int size(){ return length; } void insert(int idx, T value){ try { if(idx < 0 || idx > length) throw InvalidIndex(); if(idx == 0) head = new Node<T>(value, head); else{ Node<T> *ptr = head; for(int i = 0; i < idx - 1; i++) ptr = ptr->nextNode; ptr->nextNode = new Node<T>(value,ptr->nextNode); } length++; } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } } void erase(int idx){ try{ if(length <= 0) throw Underflow(); if(idx < 0 || idx >= length) throw InvalidIndex(); Node<T> *ptr = head; if(idx == 0){ head = head->nextNode; delete ptr; } else{ for(int i=0; i < idx - 1;i++) ptr = ptr->nextNode; Node<T> *deletedNode = ptr->nextNode; ptr->nextNode = deletedNode->nextNode; delete deletedNode; } length--; } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } catch(Underflow e){ cout << "underflow" << '\n'; } } bool serach(T value){ Node<T> *ptr = head; while(ptr != nullptr){ if(ptr->data == value) return 1; ptr = ptr->nextNode; } return 0; } T& operator[] (int idx){ Node<T> *ptr = head; for(int i=0 ; i < idx; i++) ptr = ptr->nextNode; return ptr->data; } }; template <typename T> ostream& operator <<(ostream &scan, LinkedList<T> &inputArr){ Node<T> *ptr = inputArr.head; while(ptr != nullptr){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->nextNode; } scan << "[ NULL ]" << '\n'; } int main(){ LinkedList<int> test; int k = 4; for(int i = 0; i < MAX; i ++) test.insert(i,k); cout << test; return 0; } result [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ NULL ] Doubly Linked List Doubly Linked List는 각 노드가 다음 노드의 포인터와 이전 노드의 포인터를 저장하여, 이중으로 연결된 연결리스트를 말한다. 각 노드가 이중으로 연결되었기 때문에, 혹여나 특정 노드가 다음 노드와의 연결이 끊어지더라도, 끊어진 다음 노드에 저장된 이전 노드 포인터를 이용하여 복원할 수 있다는 장점이 있다. code #include<iostream> #include<ostream> #define MAX 10 using namespace std; class InvalidIndex {}; class Underflow {}; template <typename T> class Node { public: T data; Node<T> *prev, *next; Node<T>() : prev(nullptr), next(nullptr) {} Node<T>(T value, Node<T> *prev1, Node<T> *next1) : data(value), prev(prev1), next(next1) {} }; template <typename T> class DoublyLinkedList { public: int length; Node<T> *head, *tail; DoublyLinkedList<T>() : length(0), head(nullptr), tail(nullptr) {} int size() { return length; } void insert(int idx, T value){ try { if(idx < 0 || idx > length) throw InvalidIndex(); if(idx == 0) { head = new Node<T>(value, nullptr, head); if(length == 0) tail = head; else head->next->prev = head; } else{ tail = new Node<T>(value,tail,nullptr); tail->prev->next = tail; } length++; } catch(InvalidIndex e) { cerr << "invalid index" << '\n'; exit(0); } } void erase(int idx){ try{ if(!length) throw Underflow(); if(idx < 0 || idx >= length) throw InvalidIndex(); if(idx == 0){ Node<T> *ptr = head; head = head->next; head->prev = nullptr; delete ptr; } else if(idx == length - 1){ Node<T> *ptr = tail; tail = tail->prev; tail->next = nullptr; delete ptr; } else{ if(idx >= (length - 1) / 2.0){ Node<T> *ptr = tail; for(int i = length - 1; i > idx + 1; i--) ptr = ptr->prev; Node<T> *erasedNode = ptr->prev; ptr->prev = erasedNode->prev; ptr->prev->next = ptr; delete erasedNode; } else{ Node<T> *ptr = head; for(int i = 0; i < idx - 1; i++) ptr = ptr->next; Node<T> *eraseNode = ptr->next; ptr->next = eraseNode->next; ptr->next->prev = ptr; delete eraseNode; } } length--; } catch(Underflow e){ cout << "underflow occur" << '\n'; exit(0); } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } } }; template <typename T> ostream& operator <<(ostream &scan, DoublyLinkedList<T> &inputArr){ Node<T> *ptr = inputArr.head; scan << "[ NULL ] - "; while(ptr != nullptr){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->next; } scan << "[ NULL ]" << '\n'; } template <typename T> ostream& operator >>(ostream &scan, DoublyLinkedList<T> &inputArr){ Node<T> *ptr = inputArr.tail; scan << "[ NULL ] - "; while(ptr != nullptr){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->prev; } scan << "[ NULL ]" << '\n'; } int main(){ DoublyLinkedList<int> test; int k = 4; for(int i = 0; i < MAX; i ++) test.insert(i,k++); cout << test << '\n'; cout >> test << '\n'; test.erase(7); cout << "delete indxe.7\n" << test << '\n'; test.erase(2); cout << "delete index.2\n" << test << '\n'; return 0; } result [ NULL ] - [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ NULL ] [ NULL ] - [ 13 ] - [ 12 ] - [ 11 ] - [ 10 ] - [ 9 ] - [ 8 ] - [ 7 ] - [ 6 ] - [ 5 ] - [ 4 ] - [ NULL ] delete indxe.7 [ NULL ] - [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ NULL ] delete index.2 [ NULL ] - [ 4 ] - [ 5 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ NULL ] Circular Linked List Circular Linked List는 tail, 마지막 노드가 head, 처음 노드와 연결된 구조를 말한다. 순차적으로 재생되는 음악 재생목록이라고 보면 된다. code ##include<iostream> ##include<ostream> ##define MAX 10 using namespace std; class InvalidIndex {}; class Underflow {}; template <typename T> class Node { public: T data; Node<T> *prev, *next; Node<T>() : prev(nullptr), next(nullptr) {} Node<T>(T value, Node<T> *prev1, Node<T> *next1) : data(value), prev(prev1), next(next1) {} }; template <typename T> class CircularLinkedList { public: int length; Node<T> *head, *tail; CircularLinkedList<T>() : length(0), head(nullptr), tail(nullptr) {} int size(){ return length; } void insert(int idx, T value){ try{ if(idx < 0 || idx > length) throw InvalidIndex(); if(idx == 0){ head = new Node<T>(value, tail, head); if(length == 0) tail = head; else head->next->prev = head; } else{ tail = new Node<T>(value,tail,head); tail->prev->next = tail; tail->next->prev = tail; } length++; } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } } void erase(int idx){ try{ if(!length) throw Underflow(); if(idx < 0 || idx >= length) throw InvalidIndex(); if(idx == 0){ Node<T> *ptr = head; head = head->next; head->prev = tail; tail->next = head; delete ptr; } else if(idx == length - 1){ Node<T> *ptr = tail; tail = tail->prev; tail->next = head; head->prev = tail; delete ptr; } else{ if(idx >= (length - 1) / 2.0){ Node<T> *ptr = tail; for(int i = length - 1; i > idx + 1; i--) ptr = ptr->prev; Node<T> *erasedNode = ptr->prev; ptr->prev = erasedNode->prev; ptr->prev->next = ptr; delete erasedNode; } else{ Node<T> *ptr = head; for(int i = 0; i < idx - 1; i++) ptr = ptr->next; Node<T> *erasedNode = ptr->next; ptr->next = erasedNode->next; ptr->next->prev = ptr; delete erasedNode; } } length--; } catch(Underflow e){ cout << "underflow occur" << '\n'; exit(0); } catch(InvalidIndex e){ cout << "invalid index" << '\n'; exit(0); } } }; template <typename T> ostream& operator <<(ostream &scan, CircularLinkedList<T> &inputArr){ Node<T> *ptr = inputArr.head; for(int i = 0; i < inputArr.size(); i++){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->next; } scan << "[ " << ptr->data << " ]" << '\n'; } template <typename T> ostream& operator >>(ostream &scan, CircularLinkedList<T> &inputArr){ Node<T> *ptr = inputArr.tail; for(int i = inputArr.size() - 1; i >= 0; i--){ scan << "[ " << ptr->data << " ] - "; ptr = ptr->prev; } scan << "[ " << ptr->data << " ]" << '\n'; } int main(){ CircularLinkedList<int> test; int k = 4; for(int i = 0; i < MAX; i ++) test.insert(i,k++); cout << test << '\n'; cout >> test << '\n'; test.erase(7); cout << "delete indxe.7\n" << test << '\n'; test.erase(2); cout << "delete index.2\n" << test << '\n'; return 0; } result [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 11 ] - [ 12 ] - [ 13 ] - [ 4 ] [ 13 ] - [ 12 ] - [ 11 ] - [ 10 ] - [ 9 ] - [ 8 ] - [ 7 ] - [ 6 ] - [ 5 ] - [ 4 ] - [ 13 ] delete indxe.7 [ 4 ] - [ 5 ] - [ 6 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ 4 ] delete index.2 [ 4 ] - [ 5 ] - [ 7 ] - [ 8 ] - [ 9 ] - [ 10 ] - [ 12 ] - [ 13 ] - [ 4 ]

Data Structure · 2024-07-03

이승준

Contact

Data Structure