[자료구조/정리] 레드 블랙 트리 [ 레드 블랙 트리 ] 자가 균형 이진 트리. 규칙 1. 모든 노드는 빨간색 또는 검은색. 2. 루트 노드는 검은색. 3. 리프 노드는 검은색. 4. 빨간색 노드의 자식들은 모두 검은색. 5. 루프 노드에서 리프 노드까지 사이에 있는 검은색 노드의 수는 모두 동일. +) 삽입되는 노드의 색은 무조건 빨간색. NIL노드 : 데이터를 가지고 있지 않은 더미 노드. 검은색으로 취급. 새로 삽입되는 노드의 양쪽 자식으로 NIL노드를 연결하여 5번 규칙을 만족시키게 함. 회전을 이용하여 규칙을 맞춤. 삽입 2020. 9. 22. [자료구조/정리] AVL 트리 [ AVL트리 ] 자가 균형 트리(편향 트리를 막아줌). [ 전체 코드 ] AVLTree.h #pragma once #include template class CAVLTreeNode { template friend class CAVLTree; template friend class CAVLTreeIterator; private: CAVLTreeNode() // 생성자. { m_pLeft = nullptr; m_pRight = nullptr; m_pParent = nullptr; m_pNext = nullptr; m_pPrev = nullptr; } ~CAVLTreeNode() // 소멸자. { } private: CAVLTreeNode* m_pLeft; CAVLTreeNode* m_pRight; CAVL.. 2020. 9. 22. [자료구조/정리] 이진 탐색 트리(Binary Search Tree) [ 이진 탐색 트리(Binary Search Tree) ] 자식이 최대 2개 존재할 수 있음. 작으면 왼쪽, 크면 오른쪽. 30 15 50 10 25 40 80 100 장점 : 탐색이 빠름. 예) 40을 찾을 경우, 30 40 50 오른쪽 버림. Root : 트리의 최상위 노드. 리프노드 : 가장 끝에 있는 노드. 자식이 없는 노드. 서브트리 : 큰 트리의 일부분. 편향트리 : 한쪽으로 치우친 트리. 예) 10 - 20 - 30 - 40 - 50 편향트리가 나오는 것을 주의해야 함. 이진탐색트리의 장점이 사라짐. Value : 실제 저장할 값. Key : 탐색할 때 사용하는 값. [ 전체 코드 ] BinaryTree.h #pragma once #include template class CBinaryTre.. 2020. 9. 20. [자료구조/정리] 큐(Queue) [ Queue ] 선입선출의 자료구조. 먼저 들어간 데이터가 먼저 나오는 방식. 구현 방법 : 배열 기반, 리스트 기반 [ 전체 코드 ] Queue.h #pragma once #include template class CQueueNode { template friend class CQueue; private: CQueueNode() // 생성자. { m_pNext = nullptr; } ~CQueueNode() // 소멸자. { } private: T m_Data; CQueueNode* m_pNext; }; // 리스트 기반 구현. template class CQueue { public: CQueue() // 생성자. { m_pHead = nullptr; m_pTail = nullptr; m_iSize .. 2020. 9. 17. [자료구조/정리] 스택(Stack) [ 스택(Stack) ] 선입후출의 자료구조. 먼저 들어간 데이터가 나중에 나오는 방식. 구현 방법 : 배열 기반, 리스트 기반(싱글 리스트 기반으로 활용) [ 전체 코드 ] Stack.h #pragma once #include template class CStackNode { template friend class CStack; private: CStackNode() { m_pNext = nullptr; } ~CStackNode() { } private: T m_Data; CStackNode* m_pNext; }; // 리스트 기반 구현. template class CStack { public: CStack() // 생성자. { m_pNode = nullptr; m_iSize = 0; } ~CStack.. 2020. 9. 17. [자료구조/정리] 배열(Array) [ 전체 코드 ] Array.h #pragma once #include /* [assert()] 경고창을 띄워줌. */ template class CArrayNode { template friend class CArray; template friend class CArrayIterator; private: CArrayNode() // 생성자. { m_pNext = nullptr; // nullptr로 초기화. m_pPrev = nullptr; // nullptr로 초기화. } ~CArrayNode() // 소멸자. { } private: T m_Data; CArrayNode* m_pNext; CArrayNode* m_pPrev; }; template class CArrayIterator { templat.. 2020. 9. 16. 이전 1 2 다음