justgo_developer

레드블랙트리(red black tree) -1 본문

IT/알고리즘

레드블랙트리(red black tree) -1

다날92 2018. 1. 1. 15:40
728x90
반응형

레드블랙트리(Red-Black Tree)

- 이진탐색트리의 일종

- 균형잡힌 트리 : 높이가 O(logn)

- SEARCH,INSERT,DELETE를 수정함으로써 균형을 잡히도록 만듬


-각 노드는 하나의키(key),왼쪽자식(left),오른쪽자식(right),그리고 부모노드(p)의 주소를 저장

- 자식노드가 존재하지 않을 경우 NIL 노드라고 부르는 특수한 노드가 있다고 가정

- 따라서 모든 리프노드는 NIL노드

- 루트의 부모도 NIL노드라고 가정

- 노드들은 내부노드와 NIL노드로 분류


다음 조건을 만족하는 이진탐색트리 :

1. 각 노드는 red 혹은 black이고,

2. 루트노드는 black이고 

3. 모든 리프노드(즉 NIL노드)는 black이다.

4. red노드의 자식노드들은 전부 black이고(즉, red노듣 연속되어 등장하면 안된다)

5. 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black노드가 존재한다.



레드-블랙 트리의 높이

- 노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 에지의 개수이다.

- 노드x의 블랙-높이 bh(x)는 x로부터 리프노드까지의 경로상의 블랙노드의 개수이다(노드x 자신은 부로함)


-높이가 h인 노드의 블랙-높이는 bh>=h/2이다.

(조건4에 의해 레드노드는 연속될수 없으므로 당연)

- 노드 x를 루트로 하는 임의의 부트리는 적어도 2^bh(x)-1개의 내부노드를 포함한다.

- n개의 내부노드를 가지는 레드블랙트리의 높이는 2log(n+21)이하이다.


Left and Right Rotation

- 시간복잡도 o(1)

- 이진탐색트리의 특성을 유지



Left Rotation

- y=right[x] ≠ NIL이라고 가정

- 루트노드의 부모도 NIL이라고 가정


LEFT-ROTATE(T,x)

y<-right[x]

right[x]<-left[y]

p[left[y]]<-x

p[y]<-p[x]

if p[x]=nil[T]

then root[T]<-y

else if x=left[p[x]]

then left[p[x]<-y

else right[p[x]]<-y

left[y]<-x

p[x]<-y



728x90
반응형

'IT > 알고리즘' 카테고리의 다른 글

순환(recursion)  (0) 2018.01.02
BFS(Breath-First Search, 너비우선순회)  (0) 2018.01.02
그래프 알고리즘(Graph)  (0) 2018.01.01
이진검색트리(Binary Search Tree)  (0) 2017.12.30
검색트리(Search Tree)  (0) 2017.12.29