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 | 31 |
Tags
- 마일리지
- 이베이트
- k번째 수
- round 424
- finite group
- 아시아나
- self balancing binary search tree
- gallian
- 이베이트미국
- ccw
- 백준
- indexed tree
- subgroup
- Algorithm
- acmicpc
- persistent indexed tree
- 알고리즘
- Ebate Korea
- 대수학
- Ebate USA
- Codeforces
- 이베이트코리아
- 대한항공
- round 420
- algebra
- persistent segment tree
- BOJ
- Algebraic Geometry
- 7469
- 구간쿼리
Archives
- Today
- Total
목록red black 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