Prerequisite 삽입이든, 삭제든 반드시 BST의 삽입, 삭제를 우선적으로 처리하고 그 다음에 Red-black의 property가 깨지면 그것을 보정하는 방향으로 이해해야 한다. 즉, 만약에 BST의 삽입, 삭제 규칙을 지키면서 처리했는데, Red-black의 property가 깨지는 것이 없다면 그대로 끝내주면 된다. Insert 1. 해당 트리에 아무것도 없는 경우에는 삽입하는 노드를 검은색으로 칠하고, 그렇지 않은 경우에는 빨간색으로 칠한다. 2.1. 삽입된 노드의 부모가 검은색인 경우 : 이 경우에는 Red-black property가 깨지는 것이 전혀 없으므로 바로 종료한다. 2.2 삽입된 노드의 부모가 빨간색인 경우 : 이 경우에는 Red-black property 중 red-prop..

등장 배경 이 2개의 자료구조가 등장한 배경은 연속적인 데이터를 처리하는 방식의 효율적인 처리를 하기 위함이다. 스택의 경우, LIFO(Last in First out) 구조로 후입선출이 필요할 때 사용하게 된다. 대표적인 예시로 하노이탑을 생각해보면 된다. 나중에 들어온 것이 먼저 들어온 것보다 더 먼저 처리되어야 한다. 큐의 경우, FIFO(First in First out) 구조로 선입선출이 필요할 때 사용하게 된다. 대표적인 예시로 줄 서는 것을 생각해보면 된다. 먼저 들어온 것이 더 먼저 처리되어야 한다. 기본적으로 데이터들을 순차적으로 처리하는데, 처리하는 순서의 기준이 분명한 경우 해당 자료구조를 사용하게 되면 쉽게 처리할 수 있게 된다. 구현 방법 스택과 큐를 구현하는 방법에는 연결리스트를..

등장 배경 이 자료구조가 등장한 배경은 연속적이지 않은 데이터들을 처리하기 위해서 등장하였다. 배열의 경우, 선언할 때 기본적으로 크기를 지정하게 되어있다. 컴퓨터는 이 정보를 활용해서 메모리 상에 consecutive하게 정보를 저장한다. 예를 들어 int arr[4](c class)라고 설정한 경우 컴퓨터는 int형 자료형이므로 4byte씩 4개 총 16개의 byte의 메모리를 할당하여 해당 메모리에 정보들이 consecutive하게 저장된다. 포인터 개념으로 이해해보면, 정보가 연속적으로 저장되어있기에 배열의 시작포인터와 자료형만 알면 해당 배열 index에 저장된 정보를 바로 읽을 수 있는 것이다. 그런데, 정보를 저장함에 있어 크기를 당장 정할 수 없는 경우도 존재한다. 물론 배열의 크기를 무..