2
새 요소를 삽입 한 후 RB 트리의 루트가 빨간색으로 변하면 색이 검정색으로 변경됩니다. 왜 그런가요? 빨간 뿌리가 제대로 작동하는 것처럼 보입니다. 이 색상 변경이 후속 작업을보다 효율적으로 수행 할 수 있도록 간단하게 수행 되었습니까?RB 트리의 루트가 검게 보이는 이유는 무엇입니까?
A
답변
0
하나의 가능한 설명은 나무의 높이에서 비롯됩니다. 높이는 Theta(log n)입니다.
RB-Trees가 BT이기 때문에 적어도 Omega(log n)에있는 것 이상입니다. 그런 다음 O(log n)이 등장합니다.
빨간색 노드에는 빨간색 부모가 없으므로 하나의 외부 노드 (모든 외부 노드가 동일한 BD를 가짐)의 최대 흑색 깊이 (BD)의 2 배를 넘지 않습니다. 따라서 <= log n (층에 있음).
이제 루트가 하나의 노드 만있는 트리를 상상해보십시오. 검은 색이면 모든 외부 노드의 BD가 1보다 크거나 2보다 크거나 같으며 괜찮습니다.
루트가 빨간색 인 경우 외부 노드의 깊이는 2 * 0보다 작아야합니다. 실제로는 실제로는 1입니다. 모순은 1 < 0부터입니다.
그래서 루트를 항상 검은 색에서 빨간색으로 변경할 수있는 것은 아닙니다. 반대로, 예를 들어 삭제 또는 삽입 할 때 회전 한 후에 검은 높이까지 늘릴 수 있습니다.
[위키 백과에 따르면] (http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties) : "이 규칙은 때때로 생략됩니다. 루트는 항상 빨간색에서 검은 색으로 변경 될 수 있기 때문에 하지만 반드시 그 반대가 아니더라도이 규칙은 분석에 거의 영향을 미치지 않습니다. " – Fizz
한편, 검은 색 뿌리가없는 RB 나무는 CLR과 다른 몇 곳에서 "여유있는 붉은 검은 나무"라고 불립니다. – Fizz
RB 트리 정의의 다른 부분을 "완화"하기 위해 동일한 용어가 사용되기도합니다. – Fizz