RB Tree란? Red-Black Tree는 이진 탐색 트리의 한 종류이다. 가장 기본적인 형태의 이진 탐색 트리는 최악의 경우 트리의 높이가 n으로 나타나 비효율적인 면이 있는데, 이를 보완하기 위해 삽입 또는 삭제 연산 시 트리의 균형을 맞추는 트리들이 나타났다. 이를 자가 균형 트리라고 부르며, 대표적으로 AVL Tree와 Red-Black Tree가 있다. 이번에는 Red-Black Tree에 대해 알아보자. RB Tree에는 총 다섯 가지의 규칙이 있으며, 이 규칙을 통해 트리의 밸런스를 유지한다. 다섯 가지의 규칙은 아래와 같다. RB Tree의 다섯 가지 규칙 1. 모든 노드는 빨간색 혹은 검은색 노드이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드들은 검은색이다. 4. 빨간색 노..
이번 알고리즘 문제에 트리 순회 관련 문제가 있어 정확히 트리가 무엇인지, 트리 순회가 무엇인지 알아보고자 포스팅을 하게 되었다. Graph 트리에 대해 알아보기 전에, 조금 더 넓은 개념인 그래프를 살펴보고 가자. 그래프는 노드와 노드를 연결하는 간선으로 구성되어 있는 자료구조이며, 정확히는 노드 간의 관계를 간선을 통해 표현할 수 있는 자료구조이다. 그림으로 보면 다음과 같은 구조를 그래프라고 한다. 그림을 보면 몇 가지 특징을 알 수 있는데, 정리하자면 다음과 같다. 특정 노드에서 어떤 특정 노드로 가는 경로가 하나가 아닐 수도 있다. 계속 같은 경로를 도는 순환이 발생할 수 있다. 가장 최상위 노드가 존재하지 않는다. 부모-자식의 관계가 없다. 간선의 방향이 있을수도 있고, 없을 수도 있다. Tr..
Queue 오늘은 큐에 대해 공부했다. 큐의 구현 방식에는 Linear Queue, Circular Queue, Double Ended Queue 등 다양한 방식이 있는데, 오늘은 Circular Queue의 구현을 집중적으로 다뤄볼 예정이다. 큐는 후입선출 구조인 스택과는 다르게, 선입선출 구조를 가진 자료구조이다. 선입선출 구조란? 영어로는 First In First Out, 줄여서 FIFO라고 부르기도 하며, 자료구조에 먼저 삽입된 데이터가 먼저 빠져나온다는 의미이다. 우리가 맛집 웨이팅을 할 때 대기줄이 먼저 온 사람부터 들어가는 구조와 같다! 가장 기본적인 큐 자료구조는 리스트를 활용하여 구현한다. 리스트의 맨 앞부터 원소를 하나하나 쌓아나가고, 큐에서 원소를 삭제하면 가장 앞에 있는 원소부터 ..
