레드블랙트리1

• 

  210701 레드 블랙 트리(Red-Black Tree) 레드 블랙 트리(Red-Black Tree) 모든 노드는 블랙 노드이거나 레드노드이다 루트는 블랙노드이다 모든 리프 노드는 블랙노드이다 (*리프 노드 : child가 없는 노드) 레드 노드의 child들은 모두 블랙 노드이다 임의의 노드에 대해 그 노드부터 후손 리프 노드까지의 경로에는 같은 수의 블랙노드가 있다 균형 이진 탐색 트리 => 탐색시간 O(log n) 키의 개수 n, 리프의 개수 L 이라고 하였을 때, 전체 노드의 수 = n + L = 전체 edge 수 +1 = 2n +1 L= n+1 레드 블랙 트리 평균 높이 : 원래 트리의 높이를 h, 새로운 트리의 높이를 h' 라 하면 h' >= h/2 검색 연산들은 이진검색 트리와 동일. 삽입, 삭제는 Rotation을 이용하여 수행하다 회전(Rota.. 미가공 필기(알고리즘) 2021. 7. 5.