형식이 잘못된 이진 로프 트리

Question

문자열의 대체 데이터 구조로 rope tree을 구현하려고합니다.

위키 피 디아 페이지는 나무를 나누기위한 규칙에 대해 명확하지 않지만, these rules이 처음에는 효과가있는 것으로 보입니다. 그러나 몇 분할 작업 후 나는 잘못된 트리 결국 :

  6 
      /\ 
     /\ 
     4 \ 
     /\  \  
    /\  \ 
    / 2  4 
    / /\ /\ 
    4  2 3 4 7 
    A  B C D E 

숫자는 노드의 무게, 잎의 경우 문자열의 길이를 나타냅니다. 이 잘못된 형식의 트리에서는 하위 문자열 C에 도달 할 수 없습니다.

좋은 나무의 예. 위키피디아에 대한 설명에 따라 모든 캐릭터에 접근 할 수 있습니다.

 6 
     /\ 
    /\ 
    / 7  
    / /\ 
    4 3 \ 
/\/\ \ 
    4 2 3 4 7 
    A B C D E 

나는 CS 배경이 없으므로 트리에 무엇이 잘못되었는지 알지 못합니다. 나는이 나무에 문제를 올바르게 표현하는 법을 알지 못한다. 이 트리의 문제점 (CS 용어로)은 무엇이며 어떻게 해결할 수 있습니까?

Answer 1

루트는 다음과 같은 불변을 위반 :

각 노드의 무게가 왼쪽 하위 트리에있는 모든 잎 '가중치의 합이다.

두 번째 트리는 구조를 변경하여 불변성을 수정하지만, 필요하지는 않습니다. 여기에 같은 구조로 서로 다른 가중치를 사용하여 수정 된 버전입니다 : (우리가 1 기반 색인을 가정하면 위치 (7)의 하나)

 r: 9 
     /\ 
    /\ 
    a: 4 \ 
    /\  \  
/\  \ 
/b: 2  4 
/ /\ /\ 
4  2 3 4 7 
A  B C D E 

가 C의 첫 번째 문자에 도달하려면, 당신은 위키 백과에 따라 Index(r, 7)를 실행하겠습니다 조. 여기에 "로그"입니다 :

• 찾아 7 < 9 것을, 그래서 돌아 Index(a, 7)
• 7> 네, 그래서 3> 2, 그래서 반환 것을 알아 Index(b, 3)
• 을 반환 것을 알아 Index(C, 1)
01 : C

부록의 첫 문자를 반환

위키 피 디아 문서는 제안 것을 23,516,

참고 다음과 같은 불변 (다른!) :

각 노드는 문자열의 길이를 더한 자사의 왼쪽 하위 트리에있는 모든 가중치의 합에 해당하는 "무게"를 가지고있다.

이 제제는 그 위에 바로 그림과 일치하지 않습니다

을 위의 불변에 따르면, 그림에서 노드 B는 15