Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
Tags
- Ebate USA
- Ebate Korea
- 대한항공
- persistent segment tree
- k번째 수
- 이베이트
- acmicpc
- 이베이트코리아
- Algorithm
- self balancing binary search tree
- 이베이트미국
- Codeforces
- algebra
- finite group
- ccw
- 아시아나
- gallian
- round 424
- 알고리즘
- round 420
- Algebraic Geometry
- 백준
- 마일리지
- subgroup
- BOJ
- 대수학
- 7469
- 구간쿼리
- indexed tree
- persistent indexed tree
Archives
- Today
- Total
목록self balancing binary search tree (1)
Red-Black Tree
Red-Black Tree특징모든 node는 BLACK 또는 RED의 색을 가진다.root node는 항상 BLACK이다.leaf node도 항상 BLACK이다.RED가 연속되어 있을 수 없다. (부모-자식간)root node부터 leaf node사이의 BLACK의 개수는 동일하다.self-balancing BST로 일반 BST와 다르게 5번 규칙에 의해 skewed binary tree가 되지 않음이 보장된다. (삽입/삭제 O(lgN) 보장)동작색상을 RED = 0, BLACK = 1, DOUBLE-BLACK = 2로 생각하면 이해하기 편하다.조회BST와 동일하게 수행삽입새로 삽입되는 노드는 항상 RED로 시작한다.부모노드가 조부노드의 왼쪽 자식인 경우를 가정하고 설명(오른쪽일 경우 대칭적으로 수행)부..
Algorithm/그밖에2
2018. 8. 7. 14:51