BST

Red-Black Tree(RBT)

Red-Black Tree 레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 logN이다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하고, 추가된 비트는 삽입 또는 삭제의 과정에서 트리가 균형을 유지하도록 하는 데 사용된다. 대표적으로 C++ STL의 set, multiset, map, multimap 이 레드 블랙 트리를 이용하여 구현되어있다. Why Red-Black Tree? 왜 레드 블랙 트리를 사용하는 걸까? 이 이유에 대해 알기 위해서는 BST(이진 탐색 트리)의 단점부터 파악해야 한다. BST란, 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다. ..

Tree(Binary Tree, 포화 이진 트리, 완전 이진 트리, BST)

Tree 트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고 트리 구조로 배열된 일종의 계층적 데이터의 집합이다. 따라서 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 자료를 저장하는 것이 목표라기보다는, 자료 간의 관계를 표현하는 것이 더 우선인 자료구조라고 볼 수 있다. Tree의 특징 1. 부모/자식 계층 구조를 가진다. 2. V - 1 = E (노드 수 - 1 = 간선 수) 모든 노드가 자신의 부모 노드와 연결된 간선을 가지고 있는데 루트 노드는 부모 노드가 없기 때문에 간선이 하나 부족하다. 3. 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내에서 특정 노드와 특정 노드까지의 경로는 반드시 존재한다. Tree의 구성요소 1. Node(노드) ..