B Tree와 Red-Black Tree

자료 구조를 선택할 때에는 그 목적을 확실히 할 필요가 있다

목적은 W(Insert, Update)과 R(Search)가 있다

 

자료 구조(Data Structure)는 선형적/비선형적으로 나뉜다

하지만 선형/비선형은 물리적인 구조 외에도 논리적인 구조도 포함할 수 있다

즉, List는 물리적으로는 비선형적이나 논리적으로는 선형적인 구조으로 볼 수 있다

(물리적인 구조로만 보면 Array만 선형적인 자료구조일 것이다...)

 

가장 자주 쓰는 것은 Quick Sort, 정확히는 STL의 std::sort

(부분을 나눠서(Partial) 정렬하는 분할 정렬)

Don't reinvent the WHEEL

하지만 툴을 제대로 사용하기 위해서는 제대로 알아야 한다

 

Tree는 논리적으로 비선형적인 자료 구조이다

트리는 계층 구조이다

트리에서도 주로 사용되는 구조는 이진 트리(Binary Tree)이다

 

이진 트리와 이진 탐색 트리

이진 트리는 그냥 구조지만, 이진 탐색 트리는 Insert할 때 기준이 있다

이진 탐색 트리의 문제는 같은 값이라도 Insert 순서에 따라 형태가 바뀐다

예시) 정렬되거나 역순으로 삽입하면 Worst 케이스가 나온다

 

트리를 빌드할 때 2가지 방법이 있다

정렬 후 삽입, 삽입 후 정렬

 

Binary Search Tree와 Heap의 차이점

데이터를 정렬하는 방식이 다름

이진 탐색 트리는 정렬 후 삽입,

완전 이진 트리는 삽입 후 정렬이다

 

B Tree, AVL Tree, Red-Black Tree

---

여태까지는 메모리에 데이터들이 있는 상태

하지만 항상 데이터가 메모리가 있을 수는 없다...

(최근에는 메모리 DB라는 것도 있지만 결국 어딘가에서는 저장 장치에 저장하는 처리가 필요하다)

 

DB - 별도의 저장 장치, DB서버(프로그램이 따로 있음)

  Tool - Client에서 DB에 접속

  운영 서버 - 따로 운영

 

Search

메모리 안에서 검색할 때와 하드웨어에서 검색할 때는 속도에 엄청난 차이가 발생한다

알고리즘의 비용이 log(N)이라고 해도 하드웨어에 자주 접속하면 속도는 엄청나게 느려질 수 밖에 없다

 

그럼 어떻게 해야 할까?

 

B Tree = Access 횟수를 줄이는 것이 목적(DB 탐색에 주로 사용)

AVL Tree, Red-Black Tree = 빠르게 찾는 것이 목적

 

B Tree

Degree  = 각 노드는 최대 N개의 Child를 가질 수 있다

Key = 노드가 가지는 값(Value), 최대 N-1의 값을 가질 수 있다

(N은 임의로 정할 수 있음)

N이 클수록 깊이가 줄어들어 Access의 횟수를 감소시킬 수 있다

하지만 해당 노드까지 도달하는 횟수가 줄어도 노드에서 특정 값을 찾는 속도는 느려질 수 있다

 

AVL Tree

AVL 트리는 자가 균형 이진 탐색 트리(self-balancing binary search tree)의 일종이다
(AVL은 발명자의 이름인 Adelson-Velsky and Landis에서 따옴)
균형은 Red-black tree보다 잘 잡혀 탐색은 빠르지만, 삽입과 제거가 느리다

삽입할 때 Depth를 조절해서 균형을 맞추는 트리 구조=자가 균형 이진 탐색 트리(Self Balanced Tree)이다

정렬 후 삽입하는 방식이며, 구현에는 배열보다 포인터를 사용하는 방식을 채택한다

(배열로도 구현은 할 수 있지만 의미가 별로 없음)

 

포인터를 사용하는 방식의 Node의 구성

• Value(혹은 Key)
• Left - 왼쪽 노드에 대한 포인터
• Right - 오른쪽 노드에 대한 포인터

AVL Tree에서는 포인터만 바꾸면 트리의 관계가 재설정된다

삽입, 삭제는 느리지만 탐색이 빠르다

따라서, 데이터의 변화가 거의 없고 탐색을 위주로 할 때 주로 사용된다

 

Red-Black Tree

레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)의 일종으로,
대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조이다
by 위키백과

 

Red-Black Tree는 복잡한 자료구조지만, 실 사용에서 효율적이고,

최악의 경우에도 상당히 우수한 실행 시간을 보인다

(트리에 n개의 원소가 있을 때 삽입, 삭제, 검색의 시간복잡도가 모두 O(log n)이다)

 

따라서 보편적으로 사용하는 STL의 Map도 Red-Black Tree를 사용하고 있다

AVL Tree는 탐색은 빠르지만 삽입, 삭제에 시간이 오래 걸리기 때문

삽입/삭제와 탐색의 비용을 절충한 자료 구조

 

레드 블랙 트리는 다음의 규칙을 가진다

1. 노드는 레드 또는 블랙이다
2. 루트 노드는 블랙이다
3. 모든 리프 노드는 블랙이다
4. 레드 노드의 자식은 모두 블랙이다(루트로부터 리프 노드까지의 경로에 레드 노드가 연이어 올 수 없음)
5. 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 있다

SSS