SuperVingo

여기에서는 AVL과 Red-Black Tree에 대해서 설명한다. Self-balancing Binary Search Tree "자가 균형 이진 탐색 트리(Self-balancing Binary Search Tree)"라고 한다. 이 트리는 트리의 전체적인 균형을 맞추는데, 이러한 과정이 필요한 이유는 BST의 Worst Case를 보아야한다. 바로 편향 이진 트리 상황이다. 만약 N개의 노드가 있다면, 최대 트리의 높이는 logN이므로, 탐색 시간은 $$ O(log N) $$ 이 된다. 하지만, 편향 이진 트리의 경우에는 만약 N개의 노드가 있다면, 최대 트리의 높이가 N이 되어 탐색시간은 $$ O(N) $$ 이 된다. 이러한 문제를 해결하는 것은 이진 트리의 양쪽 높이를 일정하게 유지하는 것이다. 이..

Tree Tree : 하나 이상의 Node로 이루어진 유한 집합. 용어 설명 루트(Root) 노드 부모가 없는 하나의 노드 / A 노드 차수(Degree) 노드의 서브 트리 수 트리의 차수 각 노드의 차수 중 가장 큰 차수 단말(Leaf) 노드 차수 = 0인 노드 비단말 노드 차수 != 0인 노드 형제 부모가 같은 자식 노드 레벨 루트 노드 = 레벨 1부터 1씩 증가 트리의 높이 가장 깊은 노드의 레벨 Binary Tree 최대 차수가 2인 트리를 이진 트리, Binary Tree라고 함 왼쪽과 오른쪽 서브트리를 구분함. 즉, 두 트리는 다른 트리로 구분된다. Skewed, Complete, Full Skewed Binary Tree / 편향 이진 트리 오른쪽 또는 왼쪽 서브트리만 가짐 Complete ..

Stack Stack이라는 뜻에 맞게 데이터가 쌓이는 형태로 표현한다. LIFO / Last In First Out / 후입선출 방식이라고 불리며, "늦게 들어온 데이터가 먼저 나간다"라고 생각하면 된다. 데이터를 스택에 넣는 과정을 Push라고 하고, 데이터를 스택에서 가져오는 과정을 Pop이라고 한다. Queue Queue는 FIFO / First In First Out / 선입선출 방식으로 먼저 들어온 데이터가 먼저 나오는 방식이다. 데이터를 큐에 넣는 과정을 Enqueue라고 하고, (Insert라고 표현하는 경우도 있었다.) 데이터를 큐에서 가져오는 과정을 Dequeue라고 한다. Circular Queue 큐를 계속 쓰다보면, 언젠간 자리가 다 차게되는 문제가 발생할 수 있다. 그래서 다음과 ..

Doubly Linked List Head : Linked List의 시작 노드를 가르키는 포인터 Node : 1. 데이터를 가르키는 포인터(Data) 2. 다음 노드를 가르키는 포인터(Right) 3. 이전 노드를 가르키는 포인터 (Left) 첫 노드의 Left = 마지막 Node의 Right = NULL Search node = *head; while(!node) { if(node->data == want) return true; node=node->right; } return false; Insertion Case 1. Insertion at The Front 새로운 Node 생성(New) New->Right = Head New->Left = NULL Head->Left(A) = New Head =..

끝을 다시 처음 노드를 이어 원형 구조를 이루는 것

Head : Linked List의 시작 노드를 가르키는 포인터 Node : 데이터를 가르키는 포인터(Data) + 다음 노드를 가르키는 포인터(Next) 마지막 Node의 Next : NULL Search node = *head; while(!node) { if(node->data == want) return true; node=node->next; } return false; Insertion Case 1. Insertion at The Front 새로운 Node 생성(New) New->Next = Head Head = New Case 2. Insertion after The Node 새로운 Node 생성(New) New->Next = Curr->Next Curr->Next = New Case 3. ..