이진탐색 트리&레드-블랙 트리

 

이진탐색 트리&레드-블랙 트리

 

목차

 

1. 이진탐색트리

2. 레드-블랙트리

 

이진 탐색 트리

이진 탐색 트리 는 이진 트리 기반의 탐색을 위한 자료구조입니다.

 

정의

1. 모든 원소의 키는 유일한 키를 가진다.

2. 왼쪽 서브 트리 키들은 루트 키보다 작다.

3. 오른쪽 서브 트리의 키들은 루트의 키보다 크다

4. 왼쪽,오른쪽 서브 트리 모두 이진 탐색 트리이다

 

검색, 삽입, 삭제가 빠르다는 장점이 있다.

 

다만 1,2,3,4,5,6을 트리에 순서대로 넣는다고 가정했을 경우 아래와 같이 한쪽에 편향된 트리가 만들어지게 되는데 이러한 문제를 해결한것이 레드-블랙 트리이다.

 

레드-블랙 트리

레드-블랙 트리는 이진탐색트리의 특징을 그대로 따르며 균형잡힌 이진탐색트리이다

 

정의

1. 루트는 블랙이다

2. 모든 리프(NIL)는 블랙이다

3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다(빨간색 노드가 연속으로 나올 수 없다.)

4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

삽입

레드-블랙 트리는 새로운 노드를 삽입할 때 항상 빨간색으로 삽입한다.

이때, Double Red가 발생할 수 있고 2가지 전략을 사용할 수 있다.

 

 

Restructuring

Recoloring

 

1) Restructuring

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

 

2) Recoloring

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