쥬코딩

T-tree: AVL tree(rotation, not perfectly balanced) + B tree(N ~ 2N data for each node) 시간복잡도: O(log2[N/M]) N: total # of keys, M: # of keyw per node

자료구조 2022. 4. 11. 14:21

2-3Tree: 이진탐색트리의 한 종류 (perfectly balanced) 노드의 종류가 2 node와 3 node로 두 개 있다. 시간복잡도: 2 node -> O(log2n), 3 node -> O(log3n) 2-3 tree의 조건 1: -1 왼쪽과 오른쪽의 height의 차이 즉, BF의 절대값이 클수록 노드 탐색 시간이 길어지기 때문이다 2-3 tree의 조건2: 2-node는 1개의 key, 2개의 child를 가진다. 3-node는 2개의 key, 3개의 child를 가진다. struct node { int key1; intkey2; //2-node의 key2는 NULL 값을 갖는다. struct node *left_child; struct node *middle_child; //2-nod..

자료구조 2022. 4. 11. 14:16

이진탐색트리: 이진트리를 정렬하여 노드 탐색 시간을 줄여준다. 이진트리의 특성을 모두 가진다. 정렬방식은 smaller to the left, larger to the right 이진 탐색 트리의 평균 시간 복잡도는 O(log2n)이다. 하지만, 최악의 경우 이진탐색트리의 모양이 아래와 같이 만들어 질 수 도 있다. 이 경우 시간 복잡도는 O(n)이다. 노드의 탐색시간을 더 줄이기 위해 등장한 것이 height-balanced binary search tree이다. 즉, 왼쪽과 오른쪽 subtree의 균형을 맞혀주어서 트리의 높이를 최대한 줄이는 것이다. 트리의 높이가 높을 수록 탐색시간이 길어지기 때문이다. height-balanced binary search tree의 예로는 AVL tree, T-T..

자료구조 2022. 4. 11. 11:40

1) root가 아닌 노드들은 보모가 하나이다. 2) leaf가 아닌 노드들은 자식을 하나 이상 가지고 있다. 용어 정리 (괄호 안에 있는 노드가 위의 트리에서 용어에 해당하는 노드이다) root node: 가장 위에 있는 노드로 부모 노드(parent)가 없다. ( = A) leaf node: 자식 노드(child)가 없는 노드 (= E, C, F, K, I, J) interior node: root 와 leaf노드가 아닌 노드 (= B, D, G, H) Depth == Height == Level: 노드의 높이 ( level 0 = A level 1 = B, C, D level 2 = E, F, G level 3 = H, I, J level 4 = K) Degree: 자식 노드의 개수 (A: degr..

자료구조 2022. 4. 11. 11:28

binary tree: leaf 노드를 제외한 모든 노드의 자식의 수가 최대 2개인 트리 특징: i번째 level의 최대 노드 개수는 2^(i-1)이다. height가 h인 트리가 가질 수 있는 노드의 최대 개수는 (2^h) - 1이다. struct node { int data; struct node *left_child; struct node *right_child; }; full binary tree: leaf node와 root를 제외한 모든 노드의 child가 2개인 트리 complete binary tree: 가장 오른쪽 interior 노드의 right child만 없고, leaf node와 root를 제외한 모든 노드의 child가 2개인 트리

자료구조 2022. 4. 11. 11:13

이진탐색트리: 이진트리의 한 종류 2022.04.11 - [자료구조] - [자료구조] 이진탐색트리(binary search tree) 이진탐색트리의 조건: smaller to the left, larger to the right AVL tree: 이진탐색트리의 한 종류 (not perfectly balanced) 시간복잡도: O(log2n) AVL tree의 조건: -1 왼쪽과 오른쪽의 height의 차이 즉, BF의 절대값이 클수록 노드 탐색 시간이 길어지기 때문이다 따라서 새로운 노드가 삽입된 후 BF의 절대값이 1보다 크다면 re-balancing 작업을 수행해야 한다. 경우에 따라 re-balancing하는 방법이 조금씩 다르다. 1. LL (right rotation) Right Rotation..

자료구조 2022. 3. 28. 09:57

트리를 탐색하는 방법은 크게 Depth-First Traversal, Breadth-First Traversal로 나뉜다. *Breadth-First Traversal은 같은 level(height)에 있는 노드들을 모두 탐색한 후, 다음 level로 넘어가는 방식이다. *Depth-First Traversal은 깊이 우선 탐색방법으로 현재 노드와 연결된 노드들을 먼저 탐색한 후에 다음 노드로 넘어가는 것이다. Depth-First Traversal에는 inorder, postorder, preorder 세 가지 탐색법이 있다. 1. inorder traverse: left subtree -> root -> right subtree 이 방식은 이진트리(binary tree)에서만 사용할 수 있다. 이러한..

자료구조 2022. 3. 18. 12:11

큐은 FIFO(First In First Out)방식으로 가장 먼저 들어온 값이 가장 먼저 빠져나간다. front이라는 변수는 큐의 가장 앞의 값을 가리키고 있고, rear이라는 변수는 큐의 가장 끝을 가리키고 있다. enqueue()를 수행하면 rear에 값이 삽입되고 dequeue()을 수행하면 front의 값이 제거된다. linked list의 기본 요소는 값을 저장할 멤버인 data와 다음 노드의 주소를 저장할 멤버인 next이다. 이를 이용해 linked list로 stack을 구현해보았다. 먼저 struct NODE형인 front와 rear변수를 NULL로 초기화 시켜주었다. enqueue()함수에서 하는 일은 struct NODE형인 임시변수를 하나 생성한 후 거기에 삽입할 값을 저장해두는 ..

자료구조 2022. 3. 13. 10:53