Cada borde se atraviesa como máximo 3 veces y hay n-1 bordes en un árbol, de ahí el O (n).
Creo que la parte que te confunde es el bucle de búsqueda predecesor porque baja por el árbol que sigue al nodo más a la derecha.
/* Find the inorder predecessor of current */ pre = current->left; while (pre->right != NULL && pre->right != current) pre = pre->right; Esta ruta completa solo se procesa dos veces:
- ¿Es posible que el modelo de espacio vectorial que utilizamos para entrenar algoritmos de aprendizaje automático sea inadecuado para la representación del aprendizaje humano?
- ¿Dónde aprendo árboles AVL?
- ¿Por qué no puedo resolver la subsecuencia creciente más larga simplemente ordenando la secuencia y luego iterando a través de cada elemento asegurándome de que la secuencia siempre esté aumentando?
- ¿Cómo se puede hacer un sistema como Google AdWords y AdSense?
- Cómo mejorar en la resolución de problemas para JEE
- cuando el puntero actual llega al nodo
- cuando hemos procesado su subárbol izquierdo
Además, la clave es que esta ruta no se procesa nuevamente mientras estamos en el subárbol izquierdo.
Quizás un árbol más grande lo aclare.
. 1
/ \
2 3
/ \
4 5
/ \
6 7
Actual es 1
- Encuentre el predecesor (pred) de 1. Comience en 2, bordes transversales 2 -> 5 -> 7.
- Nodo 7 -> puntos correctos a 1
La corriente es 2
- Encuentre el pred de 2. Comience a las 4 y termine de inmediato.
- 4 -> derecha = 2
La corriente es 4
- No pred, print 4. current-> right is 2
Current es 2 otra vez
- Encuentre pred de 2. Comience a las 4 y termine de inmediato.
- 4 -> right es 2, que agregamos antes. bórrelo, imprima 2 y muévase a 2-> derecha
La corriente es 5
- Encuentra pref de 5. Es 6
- 6 -> derecha = 5
La corriente es 6
- Sin pred, imprimir 6. actual-> derecha es 5
Current es 5 otra vez
- Igual que con 2. Encuentra 6, borra 6-> a la derecha, imprime 5 y pasa a 7
La corriente es 7
- Sin pred, imprime 7 y muévete a 7 -> derecha, que es 1
Current es 1 otra vez
- Encuentre la preferencia de 1. Bordes transversales 2 -> 5 -> 7. Dado que 7-> a la derecha es 1, imprima 1, muévase a 3
La corriente es 3
- Imprimir 3
Como dije, observe que la ruta 1 -> 2 -> 5 -> 7 solo se calcula dos veces. Cuando nos movemos en el subárbol izquierdo del nodo 1, lo atravesamos pero solo 1 borde a la vez. Entonces cada borde se atraviesa como máximo 3 veces.
