Como mencionó Johnny Ho, puede hacer esto usando árboles dinámicos ( es decir, árboles cortados por enlaces), pero esto lo complica demasiado, porque el problema aquí solo involucra caminos, no árboles.
Como resultado, el documento original sobre Dynamic Trees en realidad introduce una estructura de datos más simple llamada rutas dinámicas, que comprende árboles dinámicos. Y, lo adivinaste, las rutas dinámicas se aplican perfectamente aquí por sí mismas.
Para implementar rutas dinámicas, puede usar cualquier BST que admita división y fusión. Por ejemplo, un árbol Splay. (Para dividir, simplemente extienda el nodo donde desea dividir a la raíz, luego corte el árbol en dos en la nueva raíz).
- ¿Cuál es la diferencia entre el orden de fusión de arriba hacia abajo y el de fusión de abajo hacia arriba?
- Si todos los códigos de computadora son 0s y 1s, ¿cómo reconoce y entiende la computadora estos símbolos en primer lugar?
- ¿Qué es importante saber y estudiar para ser un excelente programador? ¿Es importante practicar programación competitiva?
- ¿Cuándo podrán los algoritmos de detección de imágenes filtrar imágenes ofensivas de manera confiable?
- Cómo diseñar una estructura de datos que pueda almacenar 1-1000 números
Usted representa una ruta como BST cuyos nodos se asignan a nodos de su ruta, en orden BST. Cuando una persona adquiere una ventaja, puede hacer que dos caminos se fusionen. Luego simplemente fusiona los BST correspondientes. Del mismo modo, cuando una persona pierde una ventaja, ¡simplemente divide el BST en el lugar apropiado! Hecho.
