일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 백준
- feign
- 페이징
- Spring Cloud Feign
- Spring Cloud
- Intellj
- retry
- 오라클
- db
- 디자인 패턴
- 쿼리
- JPA
- 자바
- 데이터베이스
- 클라우드
- 자료구조
- 코딩
- Spring
- DP
- MVC
- 운영체제
- aws
- golang
- SQL
- Kafka
- PL/SQL
- Jenkins
- MST
- 알고리즘
- Spring Boot
- Today
- Total
justgo_developer
레드블랙트리(red black tree) -1 본문
레드블랙트리(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
'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 |