hello world
red black tree 본문
Binary Search Tree 3가지 Search insert delete
- 노드입장에서 왼쪽은 나보다 작고 다른쪽은 큰 트리. 극단적으로 치우칠수 있다.
O(n), O(h)
Random Permitation -
실제로 극단적인 경우를 제외하고 저장되는 데이터들이 랜덤하다면 평균 시간복잡도가 n 이 된다.
저장된 데이터의 순서가 정렬된 bst에 insert 된다면 처음 온것이 루트가 될것이다.
동작원리 - 2진검색트리와 비슷(단, 트리가 완벽하게 Balance 가 맞춰있다면....)
최악의 겨우 트리가 극단적으로 unBalance 될 수 있다. 그러므로 트리가 무너지지 않도록 추가적인 작업이 필요하다.
->>>>>> 여러가지 방법중 대표적인 예시가
red black tree 이다.
red black tree (레드 - 블랙 트리)
-이진 탐색 트리의 일종이다. BST
-insert와 delete 알고리즘을 적절하게 수정한것이다.
O(log2n)
-Search, Insert, Delete 의 시간복잡도는 높이에 비례한다. O(h)
-각의 노드는 각각의 키와 부모노드의 주소를 가지고(저장) 있을 수 있다. (단 부모노드의 주소를 저장하지 안고 작성된것들도 있다.)
-자식노드가 존재하지 않을 경우 NIL 노드라고 부르느 특수한 노드가 있다 가정한다.
회색(레드노드로 가정)
다음의 조건을 만족하는 이진트리느 red black tree (레드 - 블랙 트리)
1.각 노드는 red 혹은 black이고,
2.루트노드는 black이고,
3.모든 리프노드(즉 ,NIL노드)는 black이고,
4.red노드의 자식노드들은 전부 black이고(즉, red 노드는 연속되어 등장하지않음)
5.모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의
black 노드가 존재한다.
red black tree의 SEARCH/ INSERT /DELETE
1.SEARCH : 이진트리와 별다를게 없음
2.
LEFT-ROTATE : 왼쪽그림에서 오른쪽그림으로 수정하는 것 ( 수정해도 이진 트리의 탐색 특성이 그대로 유지됨)
RIGHT_ROTATE : LEFT ROTATE 반대
LEFT-ROTATE(T,x){ //T : tree , x: node
y <- right[x]
right[x] <- left[y]
p[left[y]] <- x
p[y] <- p[x] //x의 부모가 y의 부모
if p[x] = nil[T] //현재 x의부모가 nil이라면 (= x가 루트라면)
then root[T] <- y //y가 새로운 트리의 루트
else if x = left[p[x]] //x의 부모노드가 실제로 존재한다면 x 부모의 왼쪽자식이라면
then left[p[x]] <- y //y가 x부모의 왼쪽자식
else right[p[x]] <- y //y가 x부모의 새로운 오른쪽자식
left[y] <- x //x가 y의 왼쪽자식
p[x] <- y //x의 부모가 y가 됨
}
참고 영상
