이진 트리

인덱스(Index)

Index 데이터베이스에서의 인덱스란 데이터를 빠르게 찾을 수 있는 데이터 구조로, RDBMS에서 검색 연산의 속도를 높이기 위한 방법이다. 책 맨 뒷장에 있는 찾아보기처럼 내가 원하는 데이터가 DB의 어디에 저장되어있는지 빠르게 찾을 수 있다. 데이터베이스의 파일 구조에는 인덱스 이외에도 순차 방법과 해싱 방법이 있지만, 순차 방법은 물리적 순서와 논리적 순서를 동일하게 유지해야 하기 때문에 융통성이 떨어지고 탐색 시간이 오래 걸린다는 단점이 있다. 해싱 방법은 등호 연산(=)을 사용할 때는 O(1)로 굉장히 빠르지만, 부등호 연산(>, >=,

Red-Black Tree(RBT)

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