Cómo obtener la secuencia de árbol Calkin-Wilf de la secuencia de árbol Stern-Brocot

Answer 1

La solución es: invertir la secuencia, por ejemplo [matemáticas] S (RLRR) = C (RRLR) [/ matemáticas]

Encontré este patrón por observación. Sin embargo, esto se puede probar porque

Se puede obtener un árbol del otro realizando una permutación de inversión de bits en los números en cada nivel de los árboles. – Wikipedia

La inversión de bits es la siguiente:

Asigne un número a cada elemento (por ejemplo, [matemática] n [/ matemática]) Escriba el número en binario e invierta los bits, llamemos a este número [matemática] m [/ matemática]. El nuevo lugar del elemento [math] n [/ math] es el lugar del elemento con el número [math] m [/ math]. Por ejemplo, el primer elemento ( 001 ) se asigna al quinto elemento ( 100 ).

Podemos conectar esta representación binaria para atravesar un gráfico binario. Invertir los bits corresponde a invertir las direcciones.

---

Algunos casos:

inversa inversa inversa inversa
CLL = 1/3 CRL = 2/3 CLR = 3/2 CRR = 3/1
SLL = 1/3 SLR = 2/3 SRL = 3/2 SRR = 3/1

============

inversa inversa inversa inversa
CLLL = 1/4 CRLL = 2/5 CLRL = 3/5 CRRL = 3/4
SLLL = 1/4 SLLR = 2/5 SLRL = 3/5 SLRR = 3/4

inversa inversa inversa inversa
CLLR = 4/3 CRLR = 5/3 CLRR = 5/2 CRRR = 4/1
SRLL = 4/3 SRLR = 5/3 SRRL = 5/2 SRRR = 4/1

============

inversa inversa inversa inversa
CLLLL = 1/5 CRLLL = 2/7 CLRLL = 3/8 CRRLL = 3/7
SLLLL = 1/5 SLLLR = 2/7 SLLRL = 3/8 SLLRR = 3/7

inversa inversa inversa inversa
CLLRL = 4/7 CRLRL = 5/8 CLRRL = 5/7 CRRRL = 4/5
SLRLL = 4/7 SLRLR = 5/8 SLRRL = 5/7 SLRRR = 4/5

inversa inversa inversa inversa
CLLLR = 5/4 CRLLR = 7/5 CLRLR = 8/5 CRRLR = 7/4
SRLLL = 5/4 SRLLR = 7/5 SRLRL = 8/5 SRLRR = 7/4

inversa inversa inversa inversa
CLLRR = 7/3 CRLRR = 8/3 CLRRR = 7/2 CRRRR = 5/1
SRRLL = 7/3 SRRLR = 8/3 SRRRL = 7/2 SRRRR = 5/1