트리
[골4] 1967 - 트리의 지름
#include #include #include using namespace std; #define MAX 10002 vector node[MAX]; bool vis[MAX]; int res, endPoint; void DFS(int p = 1, int len = 0) { if (vis[p]) return; vis[p] = true; if (res ..
[실1] 1991 - 트리 순회
#include using namespace std; int n; struct node { char left; char right; }; struct node tree[100]; void preOrder(char root) { if (root == '.') return; else { cout t1 >> t2 >> t3; tree[t1].left = t2; tree[t1].right = t3; } preOrder('A'); cout left); cout data; In_order(_node->right); } // (왼쪽, 오른쪽, 루트) void Post_order(s_node* _node) { if (!_node) return; Post_order(_node->left); Post_order(_node..
세그먼트 트리 (Segment Tree)
세그먼트 트리는 "구간을 저장하기 위한 트리" 이다. 예를 들어서 int Array[5] = { 1, 2, 3, 4, 5 } 2번째 값 부터 4번째 값 까지의 합은 2 + 3 + 4로 계산할 것이며 1번째 값 부터 5번째 값 까지의 합은 1 + 2 + 3 + 4 + 5로 계산하게 될 것이다. 특정 구간에 대한 연산이라면, 모든 합을 다 구해놓고 계산하는 방식을 생각할 수 있다. 이걸 1번 연산 이라고 칭하자. 2번 째 값을 7로 바꾸면 { 1, 7, 3, 4, 5 }. 이렇게, 특정 값을 바꾸는 연산 2번 연산 이라고 칭하자. 이 후에 2번째 값부터 4번째 값 까지의 합을 구하고 3번째 값부터 5번째 값 까지의 합을 구하고, 4번째 값을 6으로 바꾸는거와 같은 연산들이 쭉 이어진다고 생각해보자. 별로 문..
선 중 후 순회 트리
#include using namespace std; #define SAFE_DELETE(x) if(x != nullptr) delete x; // 트리 구조체 typedef struct s_tree_node { char data; s_tree_node* p_left; // 왼쪽 노드에 대한 포인터 s_tree_node* p_right; // 오른쪽 노드에 대한 포인터 public: // 전위 순회 함수 static void Pre_order(s_tree_node* _p_root_node) { if (_p_root_node) { printf("%3c", _p_root_node->data); Pre_order(_p_root_node->p_left); Pre_order(_p_root_node->p_right..
레드-블랙 트리(Red-Black Tree)
레드-블랙 트리(Red-Black Tree) 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다. 1. 모든 노드는 빨간색 혹은 검은색이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 4. 빨간색 노드의 자식은 검은색이다. == No Double Red(빨간색 노드가 연속으로 나올 수 없다) 5. 모든 리프 노드에서 Black Depth는 같다. == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 레드-블랙 트리 삽입 과정 위 설명만 보고는 레드-블랙 트리가 무엇인지 감이 쉽게 오지 않을 것이다. 레드-블랙 트리를 쉽..
[C] 이진 탐색 트리
이진탐색트리(Binary Search Tree)이란? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 이진 탐색 트리 탐색(Search) 이진 탐색 트리의 탐색은 다음과..
트리
트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을 갖는다. 1. 트리는 하나의 루트 노드를 갖는다. 2. 루트 노드는 0개 이상의 자식 노드를 갖는다. 3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 4. 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 수 없다. 여기서 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 한다. 트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다. 트리의 노드는 s..
트리 구현
#include #include #include // 트리 구조체 typedef struct treeNode { int data; treeNode* left; // 왼쪽 노드에 대한 포인터 treeNode* right; // 오른쪽 노드에 대한 포인터 }; // 트리 객체 초기화 treeNode* makeRootNode(int data, treeNode* leftNode, treeNode* rightNode) { treeNode* root = (treeNode*)malloc(sizeof(treeNode)); root->data = data; // data 초기화 root->left = leftNode; // 왼쪽 링크 초기화 root->right = rightNode; // 오른쪽 링크 초기화 retur..