728x90

B+ Tree

실제 데이터베이스의 indexing은 B+트리로 이루어져 있음

search에 있어서 매우~ 유리함.

https://en.wikipedia.org/wiki/B%2B_tree

- internal nodes: Index nodes (다음 노드를 가리킬 수 있는 포인터 주소가 존재)

- leaf nodes: Data nodes (실제 데이터)

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree
https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

 

  1. 모든 key, data가 리프노드에 모여있음 (B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가짐)
  2. 모든 리프노드가 연결리스트의 형태를 띄고 있음 (B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어듦)
  3. 리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같음

*첫 번째 그림과 같이 leaf nodes가 linked list로 연결된 경우도 있음. 이 경우, 다른 leaf node에 접근하기 위해 다시 root를 방문하지 않아도 됨. 그러나 결국 background operation에 의한 비용을 감당해야하지만, 분명한 이득이 있음


Dis Friendliness of B+Tree

1. 페이지 기반 접근

B+tree는 데이터를 페이지 단위로 저장 (페이지는 일정한 크기의 데이터 블록)

페이지 기반 접근을 통해, 디스크에서 데이터를 읽거나 쓸 때마다 필요한 데이터만 읽거나 쓸 수 있음.

 

ex) 
데이터 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
이 데이터를 페이지 단위로 저장하면, 다음과 같이 3개의 페이지로 나눌 수 있음
```
페이지 1: 1, 2, 3
페이지 2: 4, 5, 6
페이지 3: 7, 8, 9, 10
```
이 경우, 디스크에서 데이터를 읽거나 쓸 때마다 필요한 데이터만 읽거나 쓸 수 있는데, 예를 들어, 데이터 2를 읽으려면 페이지 1만 읽으면 됨

 

2. 분산 저장

B+tree는 데이터를 루트 노드, 중간 노드, 리프 노드로 분산하여 저장함.

루트 노드는 메모리에 저장되고, 중간 노드와 리프 노드는 디스크에 저장됨.

루트 노드에는 데이터의 위치 정보가 저장되어 있기 때문에, 디스크에서 데이터를 찾을 때는 먼저 루트 노드에서 데이터의 위치 정보를 찾음.

예를 들어, 위의 데이터를 B+tree에 저장하면 다음과 같이 저장됨
```
루트 노드: 1, 4, 7
중간 노드 1: 2, 5, 8
중간 노드 2: 3, 6, 9, 10
리프 노드 1: 1, 2
리프 노드 2: 3, 4
리프 노드 3: 5, 6
리프 노드 4: 7, 8
리프 노드 5: 9, 10
```
이 경우, 디스크에서 데이터를 찾을 때는 먼저 메모리의 루트 노드에서 데이터의 위치 정보를 찾음. 데이터의 위치 정보를 찾으면, 해당 위치의 리프 노드에서 데이터를 찾을 수 있음.

 

3. 균형 잡힌 트리

B+tree는 균형 잡힌 트리이기 때문에, 데이터를 효율적으로 저장하고 검색할 수 있음. 균형 잡힌 트리는 트리의 높이가 낮기 때문에, 데이터를 찾기 위해 디스크를 읽거나 쓸 때 필요한 I/O 횟수가 적음.


출처

https://ssocoit.tistory.com/217

 

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree

위 글을 보고 정리를 하지 않을 수 없었습니다. 가슴이 시키네요;; 그렇다면 바로 B-Tree, B*Tree, B+Tree의 특징에 대해서 알아봅시다. 목차 0. 이진트리 B-Tree, B*Tree, B+Tree에 대해서 알아보자면서 갑자

ssocoit.tistory.com

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

 

[자료구조] 그림으로 알아보는 B+Tree

정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통한 빠른 검색과 선형탐색까지 가능한 실전형 자료구조 B+ 트리입니다.

velog.io

 

728x90
728x90

0. B Tree 시리즈의 효용에 대해서는 (아주) 간단히 아래 글에 정리해놓음

*하나의 노드에 여러 자료를 배치하며, 이진 트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담음

https://lets-hci-la-ai-withme.tistory.com/190

 

*일반적으로 이진트리를 다룰 때, 하나의 노드에는 하나의 데이터가, 둘 이하의 자식 노드.

B-Tree(비 트리)

'균형' 이진 탐색 트리의 일종- 그러나 자식 노드를 2개 이상 가질 수 있음

핵심 성질 1: 하나의 노드가, 최대 M개의 자식을 가질 수 있음 (M차 B-Tree)

*internal nodes는 모두 2개 이상의 자식을 가져야 함

핵심 성질 2: 하나의 노드 내에, 2개 이상의 key(데이터)가 저장될 수 있음

 

M차 B-Tree는,

https://code-lab1.tistory.com/217

1. internal nodes의 자식 개수: ceil(M/2) ~ M개 - M값과 자식 개수의 관계

2. 각 노드 내 key의 개수: floor(M/2)-1 ~ (M-1)개 (항상 정렬된 상태, 중복 허용x)  - M값과 k의 관계

3. 한 노드 key의 개수 k에 따라, 그것의 자식 노드의 개수가 k+1로 결정됨 - k와 자식 개수의 관계

4. 특정 노드의 left subtree는 특정 노드 내 '모든 keys'보다 작은 값으로, right subtree는 큰 값으로 정렬

5. 모든 leaf nodes가 같은 레벨에 존재함

 

1) Search가 아주 쉽다 (하향식)

2) Insertion은 좀 복잡하다 (하향해서 적당한 leaf 자리 찾은 후 '적절한 상태'가 되기까지 상향)

case1: 분리가 일어나지 않는 경우 (상향 불필요)

case2: 분리가 일어나는 경우 (상향 필요)

 

3) Deletion은 더 복잡하다...

 


아주 훌륭한 레퍼런스들,,

https://code-lab1.tistory.com/217

 

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

B- 트리란? 보통 B 트리라고 하면 B- 트리를 의미한다. B 트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 이러

code-lab1.tistory.com

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

 

B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정

B 트리, 자료구조, 데이터 베이스

velog.io

https://escapefromcoding.tistory.com/731

 

DB의 인덱스와 B-tree, B+tree

개요 DB의 인덱스 개념이 궁금해 정리했습니다. MySql은 인덱스의 구조도 같이 찾았습니다. 인덱스는 B-tree, B+tree 2가지 구현방식이 있으며, 결론적으로 B+tree 방식이 사용됩니다. 각 특징은 무엇이

escapefromcoding.tistory.com

 

728x90
728x90

메모리 계층 구조

https://joooing.tistory.com/entry/cs3

- 메모리 계층 구조: 메모리를 필요에 따라 여러가지 종류로 나누어 둠, 상단으로 갈 수록 CPU가 빠르게 처리, 적은 양의 데이터, 비쌈

- 목적: CPU가 메모리에 더 빨리 접근하기 위함

 

CPU 내부: 레지스터 & 캐시

CPU 외부: RAM(주 메모리), 하드디스크, ...

 

프로세서(CPU)-메모리(RAM) 격차

CPU는 짧은 시간 내 여러 연산을 빠르게 처리함

CPU가 아무리 빨라도, (CPU 외부로 가서) 데이터를 가져오고 저장하는 속도가 느리면 전체 속도는 느려짐

이같은 격차를 줄이기 위해, 메모리에 효율적으로 접근하는 방법을 고민 → RAM이 연산하는 횟수를 최대한 줄이자

→ CPU 내부 레지스터 용량을 늘리지 못해도

→ CPU와 통합될 수 있는 빠른 보조 메모리를 만들자 = L1, L2 캐시 (레지스터와 RAM 사이에 위치, 속도와 용량이 중간.)

 

- L1 캐시; cpu 레지스터의 캐시

- L2 캐시; L1 캐시의 캐시

메모리 계층은 왜 피라미드일까?: 시간, 공간 지역성(Locality)

시간 지역성 (temporal locality) : 어떤 메모리주소에 접근한 경우, 곧 똑같은 주소에 다시 접근할 가능성이 높음
공간 지역성 (spatial locality) : 어떤 메모리주소에 접근한 경우, 곧 근처 주소에 접근할 가능성이 높음

 

- '시간'과 '공간'을 기준으로 이후에 접근할 가능성이 높은 메모리 주소들을 찾아내기 - 각각 for문, array

- 조만간 접근할 가능성이 높은 메모리 주소들을 미리 예측하고, 그 주소들을 CPU 내부에 미리 저장

- 접근 가능성이 더 높은 메모리 주소의 데이터를, CPU 레지스터와 더욱 가까운 곳에 임시로 저장해

- CPU가 찾는 메모리: 레지스터 > L1 > L2 > RAM... 순으로 찾아봄

 


Cycle?

 

 

여기서 'cycle'이 무슨 뜻일까?

- 사이클이란, CPU가 하나의 명령어를 처리하는 데 걸리는 시간

- CPU가 원하는 데이터에 액세스하기 위해 "한 바퀴"를 몇 번 돌아야 하는지

CPU Cycle

| Fetch | 메모리에서 명령어를 가져오는 단계 |
| Decode | 명령어를 해석하는 단계 |
| Execute | 명령어를 실행하는 단계 |
| Write Back | 명령어의 결과를 저장하는 단계 |

 

CPU Cycle을 도서관에서 책을 찾는 과정에 비유하자면...

  • Fetch 단계: 책을 찾기 위해 도서관에 들어간다.
  • Decode 단계: 책의 제목을 확인한다.
  • Execute 단계: 책을 꺼내 읽는다.
  • Write Back 단계: 책을 제자리에 꽂는다.

CPU Cycle의 길이는 CPU의 종류, 클럭 속도, 메모리 속도 등 다양한 요인에 따라 달라짐

 

CPU time = Clock cycles x Clock cycle time

CPU time = {명령어 개수(instruction count) x  명령어 당 cycle 횟수(CPI)} x Clock Cycle Time

*명령어의 수와 명령어 당 cycle 수로 표현 → 결국 명령어의 수 명령어당 cycle 수를 줄이는 게 핵심

 

*Clock(클럭)에 대해 알기 위해서는 우선 회로에 대한 기본적인 이해가 있어야 함

쉽게 비유해 보자면, 사람이 살아가기 위해 심장에서의 펌핑이 필요하듯이 CPU 동작에 필요한 전압이 펌핑되는 것이라 보면 됨.

High-Low 상태가 반복되며 주기적으로 반복되는  신호를 이용해 CPU 연산을 수행할  있음.

 

*CPU time이 적을 수록, 짧을 수록 더 성능이 좋음. 푸드 파이터도 더 짧은 기록이 나올 수록 좋음. 그럼 시간을 줄이려면 어떻게 해야 할까? 공식에 비춰서 생각해 보면, clock cycle(씹는 횟수)를 줄이고, clock cycle time(한 번 씹을 때 걸리는 시간)을 줄여야 함. 그러나 이게 실제로 가능할까? 결론은 "쉽지 않다." 이유는 두 가지가 trade off 관계에 있기 때문.

 

출처: https://skyjwoo.tistory.com/entry/컴퓨터-구조-CPU-time [jeongstudy:티스토리]

 


B-Tree, B+ Tree의 효용

- 내부 기억장치인 레지스터와 캐시는 CPU와 밀접한 위치에 있어 빠른 속도로 데이터를 처리할 수 있고,

- 외부 기억장치는 대용량 데이터를 효율적으로 저장하고 관리할 수 있는 구조로 설계되어 있음

 

"왜 많은 데이터베이스에서 B tree를 근간으로 사용할까?"

만약 아주 큰 사이즈의 데이터가 들어온다면 (ex. 1TB) 보통의 주요 메모리(RAM)은 8~32GB이므로, 해당 데이터를 레지스터나 캐시나 RAM에서 처리할 수 없음.

 

결국 CPU로부터 더 먼(? 사이클 횟수가 큰, 오래 걸리는) Flash Disk(SSD)나 하드드라이브에 데이터를 저장하게 됨. 이때 하드디스크나 SSD와 같은 외부 기억장치는 블럭(chunk)단위로 파일을 입출력함

이때 발생하는 입출력의 비용은 파일의 크기와는 상관 없이 동일함. (입출력에 있어 1KB짜리 블럭에 1byte짜리 알파벳 하나가 들어가 있어도 1KB가 꽉 차있는 블럭을 입출력하는 것과 차이 없음)

 

이때 하나의 블럭(chunk)여러 데이터들을 동시에 저장할 수 있다면 블럭을 보다 효율적으로 사용

=> B-트리, B+트리가 유용한 주요 이유

B+ Tree

 

https://ssocoit.tistory.com/217 [코딩하는 경제학도]
Copyright © SsocoIT

refer to: https://joooing.tistory.com/entry/cs3

728x90
728x90

목적:  방향 그래프, 음의 가중치를 갖는 그래프에서 SSP를 찾는 것

DP 스타일.

 

- 모든 SP는 negative cycle 이 없을 때만 수행 가능

- 벨만 포드는, 다익스트라와 달리, 그래프 내에 negative edge가 있더라도 실행 가능 (심지어 negative cycle의 유무를 detect)

 

- |V|-1까지 단계를 진행했을 때 'single source로부터 그래프 내 모든 node의 최단거리'가 확정됨! (|V| = G 내 노드 개수)

- 정점의 개수만큼 모든 간선을 Relax


Why |V|-1?

source 제외한 각 노드 (총 |V|-1 개)에 대해, 그래프 내 모든 edge에 대한 연산 수행해야 함.

연산량 무려 O(|V||E|)

결국 정해진 source에 대한 특정 노드까지의 최단거리를 구해야 하는데, 해당 최단 거리는 더 작은 최단 거리들의 합으로 구성되어 있음.

source로부터 가장 멀리 떨어진 노드 간 연결하는 edge 개수는, 최대 |V|-1 이고, 각각은 최단거리들의 합임 (마치 optimal substructure). 따라서 

 

https://ssungkang.tistory.com/entry/Algorithm-%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://ssungkang.tistory.com/entry/Algorithm-%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

=> 최악의 경우일 때, 순환을 포함해서는 안되므로(negative cycle은 불가능, non-negative cycle은 최단 경로로 포함될 수 없음) 최대 V개의 정점을 가지고, 그 때의 간선의 개수가 V-1기 때문


Relax?

- δ(s,v) : source -> v까지 실제 최단경로 비용

- d[v] : source -> v까지 추정 최단경로 비용 (그래프 노드 안에 적힌 값으로 표현, node.d)

Relaxation:  d[v]가 δ(s,v)의 상한이 되도록 유지하고 조정하는 함수, 궁극적으로는 d[v]가 δ(s,v)까지 줄어들도록 조정함

 

https://victorydntmd.tistory.com/103

v까지 최단거리 발견하면 그걸로 다시 업데이트! 또 업데이트!!! 반복쓰 ~.


벨만포드 전체 알고리즘 !

 

- Bellman-Ford 알고리즘은 정점의 개수만큼 모든 간선을 Relax하기 때문에 엄청난 연산

- 덕분에 음의 가중치가 있는 그래프의 단일 출발지 최단경로를 구할 수 있고, 그래프가 음의 순환구조를 갖는다면 이를 식별할 수 있음

 

구체적인 예시:

https://victorydntmd.tistory.com/104

 

[알고리즘] SSP(2) - 벨만 포드 알고리즘 ( Bellman-Ford Algorithm )

1. 벨만 포드 알고리즘 개요SSP의 첫 번째 알고리즘인 벨만 포드 알고리즘에 대해 알아보겠습니다.벨만 포드 알고리즘은 방향 그래프, 음의 가중치를 갖는 그래프에서 SSP를 찾는 것이 목적입니다

victorydntmd.tistory.com


Time-Analysis?

line 1 : theta(|V|)

그래프를 초기화

d[s] = 0, d[v] = infinite

 

line 2 ~ 4 : O((|V|-1)*(|E|)) = O(|V||E|)

정점의 개수만큼 반복문을 돌면서, 모든 간선에 대해 Relax를 수행

 

line 5 ~ 8: theta(|E|)

음의 가중치를 갖는 순환경로가 존재하는지 확인

존재한다면 false를 반환하고, 존재하지 않으면 벨만 포드 알고리즘이 잘 작동했다는 true를 반환

 

출처: https://victorydntmd.tistory.com/104


https://jeonyeohun.tistory.com/96

 

[알고리즘 정리] 최단경로(Shortest Path)

Shortest Path(최단 경로)는 가중치가 있는 그래프에서 어떤 정점에서 다른 정점으로 이동하기까지 가장 짧은 가중치의 합으로 목적지에 도달하는 방법을 찾기 위한 전략이다. 최단 경로문제는 몇

jeonyeohun.tistory.com

 

 

728x90
728x90

0과 1의 세상

 

- 컴퓨터는 0 또는 1이라는, 2진수 형태(binary)로 이해함

- 기본적으로, Byte(8개 단위의 Bit)를 사용함 

 

1비트: (0, 1) → 2^1

2비트: ((0, 1), (0, 1)) → 2^2 가지

3비트: 2^3가지

...

8비트: 2^8가지 = 256의 경우의 수

더보기

- 비트(bit) - 컴퓨터에서 사용하는 가장 작은 데이터 단위, 하나의 비트는 2진수 1 또는 0으로 표현되어
데이터를 처리, 저장, 전송 할 때 사용된다.

- 바이트(Byte) - 데이터 파일의 크기, 디스크 또는 그 외 저장 매체의 공간, 그리고 네트워크를 통하여 
전송 되는 데이터의 양을 표현하는데 사용 되는 측정 단위, 1바이트는 8비트 (1Byte = 8bit) 와 같다.

https://semiconductor.samsung.com/kr/support/tools-resources/dictionary/bits-and-bytes-units-of-data/

 

https://semiconductor.samsung.com/kr/support/tools-resources/dictionary/bits-and-bytes-units-of-data/

 

1 byte = 8 bits

1 KB = 2^10 bytes

1 MB = 2^10 KB = 2^20 bytes

1 GB = 2^30 bytes

1 TB = 2^40 bytes

 

1 KB부터는 2^10 배로 단위가 커짐!

 

refer: https://mindnet.tistory.com/entry/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-1%ED%8E%B8-Bit-%EC%99%80-Byte-%EC%B0%A8%EC%9D%B4%EC%A0%90

https://semiconductor.samsung.com/kr/support/tools-resources/dictionary/bits-and-bytes-units-of-data/


Data Types

char: 1 byteexpress 256 values

short: 2 bytes

int: 4 bytes (32 bits) 

long: 8 bytes (64 bits)

 

string: an array of chars = an array of bytes(each byte: 0~255)


ASCII 코드

- 결국 컴퓨터는 모든 것을 0과 1의 조합(binary)로 읽음

 

- 컴퓨터에서 문자(영어 알파벳 / 숫자 / 특수 문자 / 제어 문자 / 공백 문자)를 binary로 표현하기 위한 표준 코드

- 문자와 binary를 일대일로 매핑 → 7비트(128가지) 또는 8비트(256가지)의 binary로 표현

10진/16진으로 돼있는데 -> 컴퓨터는 결국 binary로 읽음

- 아스키코드에서 10진을 보면.. 우리가 이해하기 더 쉬움.

아무튼 127까지 있는 걸 보니 문자를 7 bit로 할당(128가지의 문자를 binary로 매핑)

 


728x90

728x90

https://boycoding.tistory.com/250

C++ 09.10 - this 포인터

this 포인터 객체 지향 프로그래밍에서 가장 많은 질문 중 하나는 "클래스의 멤버 함수를 호출할 때 C++는 어떻게 호출할 객체(인스턴스)를 찾는가?" 이다. 이 질문에 대한 정답은 this라는 숨겨진

boycoding.tistory.com

 
모든 멤버 함수는 함수가 호출된 객체(인스턴스)를 가리키는 this 포인터를 가지고 있다.
호출된 객체의 주소를 가리키는 상수 포인터다.
상수 포인터 자료형이므로 포인터 자체가 다른 것을 가리키도록 할 수는 없다.
모든 과정은 컴파일러에 의해 자동으로 수행된다.
 
그러나, 명시적으로 this를 참조해야 하는 경우가 있다.
 
- 첫째, 멤버 변수와 이름이 같은 매개 변수를 가진 생성자(또는 멤버 함수)가 있는 경우, this를 사용해서 구분할 수 있다. 

class Something
{
private:
    int data;

public:
    Something(int data)
    {
        this->data = data;
        // this->data는 멤버 변수이고,
        // data는 매개 변수
    }
};

 
- 둘째, 클래스 멤버 함수가 작업 중이던 객체(인스턴스)를 반환하는 방식이 유용할 때가 종종있다. 이렇게 하면 같은 객체의 여러 멤버 함수를 연속해서 호출할 수 있는 방법이다.
만약 각각의 멤버 함수가 *this 반환한다면 체이닝 기능이 있는 새로운 버전의 Calc 만들 있다.

class Calc
{
private:
    int m_Value = 0;

public:
    Calc& Add(int value) { m_Value += value; return *this; }
    Calc& Sub(int value) { m_Value -= value; return *this; }
    Calc& Mul(int value) { m_Value *= value; return *this; }

    int GetValue() { return m_Value; }
}

int main()
{
    Calc calc;

    calc.Add(5).Sub(3).Mul(4); //함수 체이닝

    cout << calc.GetValue() << endl; // 8
    return 0;
}

출처: https://boycoding.tistory.com/250 [소년코딩:티스토리]

728x90
728x90

- recoloring이든 reconstruction이든, 부모를 검은 색으로!!!
 

레드블랙트리는, 자가 균형 이진 탐색 트리 중 하나이다.

Properties of Red Black Tree

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 빨간색 노드의 자식은 검은색이다.
   == No Double Red(빨간색 노드가 연속으로 나올 수 없다)
5. 모든 리프 노드에서 Black Depth는 같다.
   == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다

 
레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다. 
이렇게 되면 4번 조건이 위배되는 상황이 발생한다. 즉, 빨간색 노드가 연속으로 2번 나타날 수 있다(Double Red)
 
레드 블랙 트리는 이러한 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다.
 

새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 하자. 즉, 삼촌 노드는 말 그대로 부모의 형제라고 생각하면 된다. 
 
Double Red가 발생했을 때 

  • 삼촌 노드가 검은색이라면 -> Restructuring을 수행하면 된다.
  • 삼촌 노드가 빨간색이라면 -> Recoloring을 수행하면 된다.

Restructuring

1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

Recoloring

1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
   1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
   1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

 

1-1) simple reconstruct 결과 root가 빨간색이 되어버린 경우

1-2) simple reconstruct 결과 부모 위에서 double red가 나타난 경우

-> double red가 나타난 지점 중 아래 노드를 기준으로, uncle을 살펴본다 (uncle이 검은 색이면 reconstruct, 빨간 색이면 recolor)
 


https://code-lab1.tistory.com/62

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

레드-블랙 트리(Red-Black Tree) 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다. 1. 모든 노드는 빨간색 혹은 검은색이다. 2. 루트 노드는 검은색

code-lab1.tistory.com

 

728x90

728x90

선형 자료 구조(연결 리스트, 스택, 큐 등): 순차적으로 요소에 접근

트리 자료구조는 노드들을 방문하기 위해 다른 방식을 사용해야 함

 

트리 순회(Tree Traversal): 트리의 모든 노드들을 방문하는 과정 - 주로 세 가지가 있음: 전위 순회, 중위 순회, 후위 순회

 

전위 순회와 후위 순회 모두 Recursion을 통해 간단하게 구현 가능.

특히, 두 순회는 print 코드가 Recursion 코드의 이전에 있는지 / 이후에 있는지에 따라 나뉨.

 

1. 전위 순회(Preorder Traversal)

: Work at a node is performed before its children are processed

 

2. 후위 순회(Postorder Traversal)

: Work at a node is performed after its children are processed

 

 

https://yoongrammer.tistory.com/70

 

[자료구조] 트리 순회 (Tree Traversal)

목차 트리 순회 (Tree Traversal) 트리의 모든 노드들을 방문하는 과정을 트리 순회(TreeTraversal)라고 합니다. 선형 자료 구조(연결 리스트, 스택, 큐 등)는 순차적으로 요소에 접근하지만 트리 자료구

yoongrammer.tistory.com

 

728x90

+ Recent posts