로프 데이터 구조 가중치는 노드의 문자와 왼쪽 하위 트리의 가중치 또는 왼쪽 및 오른쪽 하위 트리의 가중치입니까?

Question

위키 백과 entry 메시지 :

각 노드는 문자열의 길이와 동일한 "가중치"와 왼쪽 하위 트리의 모든 가중치의 합계를 더한 값을가집니다. 따라서 두 개의 하위가있는 노드는 전체 문자열을 두 부분으로 나눕니다. 왼쪽 하위 트리는 문자열의 첫 번째 부분을 저장합니다. 오른쪽 하위 트리는 두 번째 파트를 저장하고 그 무게는 두 파트의 합입니다.

약간 혼란 스럽습니다. 노드 무게는 문자열의 길이와 왼쪽 하위 트리의 모든 가중치의 합입니다. 그런 다음 노드에 두 개의 하위 노드 (왼쪽 및 오른쪽 하위 트리)가있는 경우에는 왼쪽 하위 트리가 아니라 두 부분의 합계가됩니다. 다이어그램을 보면 의미가 있습니다. (22 아래의 9는 9이고, 7의 하위/하위 트리가 체중에 기여하지 않기 때문에 9보다 크지 않습니다).하지만 문구가 나에게 보이거나 내가 오해하고있는 것입니까?

Answer 1

그래, 문구가 꺼져 있습니다. "weight"는 파티션 포인트이므로 왼쪽 부분 문자열 (또는 포함 된 문자열)을 포함합니다. (즉, 확인, 그래서) O (로그 n 수 있어야합니다.)

당신은 노드의 전체 길이를 저장해야하지만 밧줄을 수정하는 것은 모든 부모 노드가 변경 통지 할 것을 요구하지 않는다