0
이 개념을 이해하는 데 어려움을 겪고 있습니다. 검은 색 노드가 균형을 잡으면 주어진 RB 불균형은 트리 전체를 고려하면 가질 수있는 최대 불균형은 무엇입니까? 위키 인용빨강 검정 나무의 최대 불균형
A
답변
0
: the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf. 최대 불균형 나뭇잎 최단 경로 길이의 두 배 수단
.
article은 좋은 이유를 설명합니다.
아니요. 그러나 검은 노드가 균형을 이룬다는 사실을 고려하지 않았습니다. – Bhargav
입니다. 어떤 경로에있는 검은 노드의 수가 B라면, 최대 깊이는 붉은 색과 검은 색 노드가 교대로 포함되므로 깊이는 2 * B (2 * B-1은 정확히 검은 노드로 시작하고 끝납니다) , 최소 깊이는 검정 노드 만 포함하므로 B가됩니다. –