Level ancestor problem
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಮತ್ತು ಸೈದ್ಧಾಂತಿಕ ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ, ಮಟ್ಟದ ಪೂರ್ವಜರ ಸಮಸ್ಯೆಯೆಂದರೆ, ಮರದ ಮೂಲದಿಂದ ನಿರ್ದಿಷ್ಟ ದೂರದಲ್ಲಿ ನಿರ್ದಿಷ್ಟ ನೋಡ್ನ ಪೂರ್ವಜರನ್ನು ನಿರ್ಧರಿಸಬಲ್ಲ ದತ್ತಾಂಶ ರಚನೆಯಲ್ಲಿ ನಿರ್ದಿಷ್ಟವಾಗಿ ಬೇರೂರಿರುವ ಮರದ ಟಿ ಅನ್ನು ಪೂರ್ವಭಾವಿಯಾಗಿ ಸಂಸ್ಕರಿಸುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಹೆಚ್ಚು ನಿಖರವಾಗಿ ಹೇಳುವುದಾದರೆ, ಟಿ ಎಂಬುದು n ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುವ ಬೇರೂರಿರುವ ಮರವಾಗಿರಲಿ, ಮತ್ತು ವಿ ಎಂಬುದು ಟಿ ಯ ಅನಿಯಂತ್ರಿತ ನೋಡ್ ಆಗಿರಲಿ. ಎಲ್ಎ (ವಿ, ಡಿ) ಮಟ್ಟದ ಪೂರ್ವಜರ ಪ್ರಶ್ನೆಯು ನೋಡ್ ವಿ ಯ ಪೂರ್ವಜರನ್ನು ಡಿ ಆಳದಲ್ಲಿ ವಿನಂತಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಮರದಲ್ಲಿನ ನೋಡ್ ವಿ ಯ ಆಳವು ಮರದ ಮೂಲದಿಂದ ನೋಡ್ ವಿ ಗೆ ಹೋಗುವ ಕಡಿಮೆ ಮಾರ್ಗದಲ್ಲಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಓ (ಎನ್) ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮತ್ತು ಓ (ಎನ್) ಶೇಖರಣಾ ಸ್ಥಳವನ್ನು ಬಳಸುವ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ನಿರ್ಮಿಸುವ ಪೂರ್ವಸಂಸ್ಕರಣೆಯ ಅಲ್ಗಾರಿದಮ್ನ ನಂತರ, ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ಸ್ಥಿರವಾದ ಸಮಯದಲ್ಲಿ ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಸಾಧ್ಯವಿದೆ. ನಿಷ್ಕಪಟ ವಿಧಾನಗಳು ನೋಡ್ನ ಸಮತಟ್ಟಾದ ಪೂರ್ವಜರನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸರಳವಾದ ಮಾರ್ಗವೆಂದರೆ ಮರದ ಬೇರಿನ ಕಡೆಗೆ ಮರವನ್ನು ಹತ್ತುವುದು. ಮರದ ಬೇರಿನ ಹಾದಿಯಲ್ಲಿ, ನೋಡ್ನ ಪ್ರತಿಯೊಂದು ಪೂರ್ವಜರನ್ನು ಭೇಟಿ ಮಾಡಬಹುದು ಮತ್ತು ಆದ್ದರಿಂದ ವರದಿ ಮಾಡಬಹುದು. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಮರವನ್ನು ಪೂರ್ವಭಾವಿಯಾಗಿ ಸಂಸ್ಕರಿಸುವ ಅಗತ್ಯವಿಲ್ಲ ಮತ್ತು ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸುವ ಸಮಯವು ಒ (ಎಚ್) ಆಗಿರುತ್ತದೆ, ಅಲ್ಲಿ "ಎಚ್" ಎಂಬುದು ಮರದ ಎತ್ತರವಾಗಿದೆ. ಮರವು ದೊಡ್ಡ ಎತ್ತರವನ್ನು ಹೊಂದಿರಬಹುದಾದ ಮತ್ತು ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಪ್ರಶ್ನೆಗಳನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಬೇಕಾದ ಸಂದರ್ಭಗಳಲ್ಲಿ ಈ ವಿಧಾನವು ಕಾರ್ಯಸಾಧ್ಯವಲ್ಲ. ಪರ್ಯಾಯವಾಗಿ, ಸಾಧ್ಯವಿರುವ ಎಲ್ಲಾ ಪರಿಹಾರಗಳನ್ನು ಪೂರ್ವಭಾವಿಯಾಗಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು ಮತ್ತು ಕೋಷ್ಟಕದಲ್ಲಿ ಸಂಗ್ರಹಿಸಬಹುದು. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಪ್ರಶ್ನೆಗಳಿಗೆ ಓ (1) ನಲ್ಲಿ ಉತ್ತರಿಸಬಹುದು ಆದರೆ ಸ್ಥಳ ಮತ್ತು ಪೂರ್ವ ಸಂಸ್ಕರಣಾ ಸಮಯವು ಓ (ಎನ್ 2) ಆಗಿದೆ. ಯಾವುದೇ ಪೂರ್ವ ಸಂಸ್ಕರಣೆಯಿಲ್ಲದೆ ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಉತ್ತರಿಸಬಹುದಾದ ಸರಳವಾದ ಪ್ರಶ್ನೆಗಳೆಂದರೆ ಎಲ್ಎ (ವಿ, 0) ಮತ್ತು ಎಲ್ಎ (ವಿ, ಡೆಪ್ತ್ (ವಿ)). ಮೊದಲನೆಯ ಸಂದರ್ಭದಲ್ಲಿ, ಉತ್ತರವು ಯಾವಾಗಲೂ ಮರದ ಮೂಲವಾಗಿರುತ್ತದೆ ಮತ್ತು ಎರಡನೆಯ ಸಂದರ್ಭದಲ್ಲಿ, ಉತ್ತರವು ನೋಡ್ v ಆಗಿರುತ್ತದೆ. ಈ ಪ್ರತಿಯೊಂದು ಫಲಿತಾಂಶವು ಒ (1) ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ವಕ್ರವಾದ ಬೈನರಿ ಯಾದೃಚ್ಛಿಕ ಪ್ರವೇಶ ಪಟ್ಟಿಯಲ್ಲಿ ಮರದ ಮೂಲಕ ಹಾದಿಗಳನ್ನು ಸಂಗ್ರಹಿಸುವುದರಿಂದ ಮರವನ್ನು ಇನ್ನೂ ಒಂದು ಸಮಯದಲ್ಲಿ ಒಂದು ಓ (1) ಹಂತಕ್ಕೆ ಕೆಳಕ್ಕೆ ವಿಸ್ತರಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ, ಆದರೆ ಈಗ ಹುಡುಕಾಟವನ್ನು ಒ (ಲಾಗ್ (ಪಿ)) ನಲ್ಲಿ ಮುಂದುವರಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ, ಅಲ್ಲಿ "ಪಿ" ವಿನಂತಿಸಿದ ಆಳಕ್ಕೆ ವಿ ನಿಂದ ದೂರವಾಗಿದೆ. ಮರವು ವಿಶೇಷವಾಗಿ ಅಗಲವಾಗಿದ್ದಾಗ ಅಥವಾ ಆನ್ಲೈನ್ನಲ್ಲಿ ವಿಸ್ತರಿಸಲ್ಪಟ್ಟಾಗ ಈ ವಿಧಾನವು ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಅದನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪೂರ್ವ-ಸಂಸ್ಕರಿಸಲಾಗುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ಸಂಗ್ರಹಣೆ ಮತ್ತು ಪ್ರವೇಶದ ಸಮಯವನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ಮಾರ್ಗದ ಉದ್ದದಿಂದ ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆ. ಜಂಪ್ ಪಾಯಿಂಟರ್ ಅಲ್ಗಾರಿದಮ್ ಜಂಪ್ ಪಾಯಿಂಟರ್ ಅಲ್ಗಾರಿದಮ್ ಓ (ಎನ್ ಲಾಗ್ ಎನ್) ಸಮಯದಲ್ಲಿ ಮರವನ್ನು ಪೂರ್ವ-ಪ್ರಕ್ರಿಯೆಗೊಳಿಸುತ್ತದೆ ಮತ್ತು ಓ (ಲಾಗ್ ಎನ್) ಸಮಯದಲ್ಲಿ ಮಟ್ಟದ ಪೂರ್ವಜರ ಪ್ರಶ್ನೆಗಳಿಗೆ ಉತ್ತರಿಸುತ್ತದೆ. ಜಂಪ್ ಪಾಯಿಂಟರ್ ಅಲ್ಗಾರಿದಮ್ ಮರದ ಪ್ರತಿಯೊಂದು ಶೃಂಗಕ್ಕೂ ಲಾಗ್ ಎನ್ ಪಾಯಿಂಟರ್ಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ. ಈ ಪಾಯಿಂಟರ್ಗಳನ್ನು ಜಂಪ್ ಪಾಯಿಂಟರ್ಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಅವು ಮರವನ್ನು ಮರದ ಬೇರಿನ ಕಡೆಗೆ ಜಿಗಿಯುತ್ತವೆ. ಮರದ ನಿರ್ದಿಷ್ಟ ನೋಡ್ v ಗೆ, ಅಲ್ಗಾರಿದಮ್ ಉದ್ದ ಜಿಗಿತಗಾರರ ಶ್ರೇಣಿಯನ್ನು ಎಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಈ ಶ್ರೇಣಿಯ ith ಅಂಶವು v ನ 2 ನೇ ಪೂರ್ವಜರನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಅಂತಹ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಬಳಸುವುದು ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ನೋಡ್ನಿಂದ ಅರ್ಧದಾರಿಯಲ್ಲೇ ಮರವನ್ನು ಮೇಲಕ್ಕೆ ಜಿಗಿಯಲು ನಮಗೆ ಸಹಾಯ ಮಾಡುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಶ್ನೆಯನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಲು ಕೇಳಿದಾಗ, ನಾವು ಪದೇ ಪದೇ ಈ ಪಾಯಿಂಟರ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಮರವನ್ನು ಮೇಲಕ್ಕೆ ಜಿಗಿಯುತ್ತೇವೆ. ಜಿಗಿತಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ ಲಾಗ್ ಎನ್ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಪ್ರಶ್ನೆಗಳಿಗೆ ಲಾಗ್ ಎನ್ ಸಮಯದಲ್ಲಿ ಉತ್ತರಿಸಬಹುದು. ಲ್ಯಾಡರ್ ಅಲ್ಗಾರಿದಮ್ ಲ್ಯಾಡರ್ ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಮರವನ್ನು ಮಾರ್ಗಗಳ ಸಂಗ್ರಹವಾಗಿ ಸರಳಗೊಳಿಸುವ ಕಲ್ಪನೆಯನ್ನು ಆಧರಿಸಿದೆ. ಇದಕ್ಕೆ ಕಾರಣವೆಂದರೆ ಪೂರ್ವಜರ ಪ್ರಶ್ನೆಗಳನ್ನು ಮಟ್ಟಕ್ಕೆ ತರುವಾಗ ಮಾರ್ಗಗಳನ್ನು ಪ್ರಶ್ನಿಸುವುದು ಸುಲಭ. ನೋಡ್ r ನಲ್ಲಿ ಬೇರೂರಿರುವ n ನೋಡ್ಗಳನ್ನು ಒಳಗೊಂಡಿರುವ P ಮಾರ್ಗವನ್ನು ಪರಿಗಣಿಸಿ. ನಾವು ಮಾರ್ಗವನ್ನು ಲ್ಯಾಡರ್ ಎಂದು ಕರೆಯಲಾಗುವ ಗಾತ್ರದ n ಶ್ರೇಣಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಬಹುದು ಮತ್ತು ಆಳ (v) ≤ d ಆಗಿದ್ದರೆ ಲ್ಯಾಡರ್ [d] ಅನ್ನು ಹಿಂದಿರುಗಿಸುವ ಮೂಲಕ ನಾವು ಎಲ್ಎ (v, d) ಯ ಮಟ್ಟದ ಪೂರ್ವಜರ ಪ್ರಶ್ನೆಗೆ ತ್ವರಿತವಾಗಿ ಉತ್ತರಿಸಬಹುದು. ಇದು ಓ (1) ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಕೊಟ್ಟಿರುವ ಮರವು ಒಂದು ಮಾರ್ಗವಾಗಿದ್ದರೆ ಮಾತ್ರ ಇದು ಕೆಲಸ ಮಾಡುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, ನಾವು ಅದನ್ನು ಮಾರ್ಗಗಳಾಗಿ ವಿಭಜಿಸಬೇಕಾಗಿದೆ. ಇದನ್ನು ಎರಡು ಹಂತಗಳಲ್ಲಿ ಮಾಡಲಾಗುತ್ತದೆಃ ದೀರ್ಘ-ಮಾರ್ಗ ವಿಭಜನೆ ಮತ್ತು ದೀರ್ಘ ಮಾರ್ಗಗಳನ್ನು ಏಣಿಗಳಾಗಿ ವಿಸ್ತರಿಸುವುದು. ಹಂತ 1: ದೀರ್ಘ-ಮಾರ್ಗ ವಿಭಜನೆ ಇದು ನಿರ್ದಿಷ್ಟ ಮರವನ್ನು ಪಥಗಳಾಗಿ ವಿಭಜಿಸುವ ಪುನರಾವರ್ತಿತ ವಿಧಾನವಾಗಿದೆ. ಈ ಹಂತಗಳು ಮರದಲ್ಲಿ ಬೇರುಗಳಿಂದ ಎಲೆಯವರೆಗಿನ ಅತಿ ಉದ್ದದ ಮಾರ್ಗವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮೂಲಕ ಪ್ರಾರಂಭವಾಗುತ್ತವೆ. ನಂತರ ಅದು ಮರದಿಂದ ತನ್ನ ಸಂಬಂಧಗಳನ್ನು ಮುರಿಯುವ ಮೂಲಕ ಈ ಮಾರ್ಗವನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ, ಅದು ಉಳಿದ ಮರವನ್ನು ಉಪ-ಮರಗಳಾಗಿ ಒಡೆಯುತ್ತದೆ ಮತ್ತು ನಂತರ ಅದು ಪ್ರತಿ ಉಪ-ಮರವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಸಂಸ್ಕರಿಸುತ್ತದೆ. ಪ್ರತಿ ಬಾರಿ ಒಂದು ಮಾರ್ಗವು ಕೊಳೆಯುವಾಗ, ಮೂಲದಿಂದ ಎಲೆಯವರೆಗಿನ ಮಾರ್ಗದಲ್ಲಿರುವ ಅಂಶಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಮಾರ್ಗದ ಸಹಯೋಗದೊಂದಿಗೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ರಚಿಸಲಾಗುತ್ತದೆ. ಈ ಪುನರಾವರ್ತನೆಯ ಮೂಲ ಪ್ರಕರಣವೆಂದರೆ ಮರವು ಒಂದು ಮಾರ್ಗವಾಗಿದ್ದಾಗ ಅದರ ತೆಗೆದುಹಾಕುವಿಕೆಯು ಖಾಲಿ ಗ್ರಾಫ್ ಅನ್ನು ಬಿಡುತ್ತದೆ. ಪ್ರತಿ ಶೃಂಗವು ಒಂದು ವಿಶಿಷ್ಟವಾದ ಏಣಿಯೊಂದನ್ನು ಹೊಂದಿದೆ, ಅದು ಅದನ್ನು ಹೊಂದಿರುವ ಏಣಿಯಾಗಿದೆ ಮತ್ತು ನಾವು ಅದನ್ನು "ವಿ 'ಸ್ ಲೇಡರ್" ಎಂದು ಕರೆಯುತ್ತೇವೆ. ಆದಾಗ್ಯೂ, ಈ ಪೂರ್ವ-ಸಂಸ್ಕರಣಾ ಹಂತದ ನಂತರ, ಪ್ರಶ್ನೆಗಳಿಗೆ ತ್ವರಿತವಾಗಿ ಉತ್ತರಿಸಲಾಗುವುದಿಲ್ಲ. ವಾಸ್ತವವಾಗಿ, ಒಂದು ಮಟ್ಟದ ಪೂರ್ವಜರ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಲು, ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಮಾರ್ಗದಿಂದ ಇನ್ನೊಂದು ಮಾರ್ಗಕ್ಕೆ ಅದು ಮೂಲವನ್ನು ತಲುಪುವವರೆಗೆ ಜಿಗಿಯಬೇಕಾಗುತ್ತದೆ ಮತ್ತು ಲೀಫ್-ಟು-ರೂಟ್ ಮಾರ್ಗದಲ್ಲಿ ಅಂತಹ ಮಾರ್ಗಗಳ ≤ () ಇರಬಹುದು. ಇದು ಓ (ಎನ್) ಸಮಯದಲ್ಲಿ ಮರವನ್ನು ಪೂರ್ವ-ಸಂಸ್ಕರಿಸುವ ಮತ್ತು ಓ () ನಲ್ಲಿ ಪ್ರಶ್ನೆಗಳಿಗೆ ಉತ್ತರಿಸುವ ಅಲ್ಗಾರಿದಮ್ಗೆ ನಮ್ಮನ್ನು ಕರೆದೊಯ್ಯುತ್ತದೆ. ಸೂಕ್ತವಾದ ಪ್ರಶ್ನೆಯ ಸಮಯವನ್ನು ತಲುಪಲು, ನಾವು ಕೆಳಗೆ ವಿವರಿಸಿದ ಎರಡನೇ ಹಂತದಲ್ಲಿ ಫಲಿತಾಂಶಗಳನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಬೇಕಾಗಿದೆ. ಹಂತ 2: ಉದ್ದವಾದ ಹಾದಿಗಳನ್ನು ಏಣಿಗಳಾಗಿ ವಿಸ್ತರಿಸುವುದು ಅಲ್ಗಾರಿದಮ್ನ ಮೊದಲ ಹಂತವು ಮರವನ್ನು ಹಲವಾರು ವಿಭಿನ್ನ ಮಾರ್ಗಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ನ ಎರಡನೇ ಹಂತದಲ್ಲಿ, ಪ್ರತಿ ಮಾರ್ಗವನ್ನು ವಿಸ್ತರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಪರಿಣಾಮವಾಗಿ ಬರುವ ಮಾರ್ಗಗಳು ಪರಸ್ಪರ ಪ್ರತ್ಯೇಕವಾಗಿರುವುದಿಲ್ಲ. ಅಲ್ಗಾರಿದಮ್ನ ಮೊದಲ ಹಂತದಲ್ಲಿ, ಪ್ರತಿ ಮಾರ್ಗವು 'ಎಚ್' ಗಾತ್ರದ ಶ್ರೇಣಿಯೊಂದಿಗೆ ಸಂಬಂಧಿಸಿದೆ. ಅದೇ ಶ್ರೇಣಿಯಲ್ಲಿ ಮಾರ್ಗದ ಮೇಲ್ಭಾಗದಲ್ಲಿ ಎಚ್ 'ತಕ್ಷಣದ ಪೂರ್ವಜರನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ನಾವು ಈ ಮಾರ್ಗವನ್ನು ವಿಸ್ತರಿಸುತ್ತೇವೆ. ಇದು ಪ್ರತಿ ಶ್ರೇಣಿಯನ್ನು ಅದರ ಮೂಲ ಗಾತ್ರಕ್ಕಿಂತ ಎರಡು ಪಟ್ಟು ವಿಸ್ತರಿಸುತ್ತದೆ, ಇದು ಎಲ್ಲಾ ಏಣಿಗಳಲ್ಲಿ ಒಟ್ಟು 2n ಸಂಖ್ಯೆಯ ನೋಡ್ಗಳಿಗೆ ಕಾರಣವಾಗುತ್ತದೆ. ಏಣಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಬದಲಾಯಿಸಲಾಗಿಲ್ಲ ಮತ್ತು ಪ್ರತಿ ನೋಡ್ನ ಏಣಿಯೂ ಒಂದೇ ಆಗಿರುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ನೋಡ್ ವಿ ಅನ್ನು ಈಗ ಅನೇಕ ಮಾರ್ಗಗಳಲ್ಲಿ ಪಟ್ಟಿ ಮಾಡಬಹುದಾದರೂ, ಅದರ ಏಣಿ ಅಲ್ಗಾರಿದಮ್ನ ಮೊದಲ ಹಂತದಲ್ಲಿ ವಿ ಗೆ ಸಂಬಂಧಿಸಿದೆ. ಈ ಎರಡು ಹಂತಗಳು ಒ (ಎನ್) ನಲ್ಲಿ ಪ್ರಕ್ರಿಯೆಗಳಾಗಿರಬಹುದು ಆದರೆ ಪ್ರಶ್ನೆಯ ಸಮಯವು ಇನ್ನೂ ಸ್ಥಿರವಾಗಿಲ್ಲ. h ಎತ್ತರದ ಯು ನೋಡ್ನಲ್ಲಿ ಒಂದು ಮಟ್ಟದ ಪೂರ್ವಜರ ಪ್ರಶ್ನೆಯನ್ನು ಪರಿಗಣಿಸಿ. ಯು ಏಣಿಯ ಮೇಲ್ಭಾಗಕ್ಕೆ ಪ್ರಯಾಣಿಸುವ ಮೂಲಕ, ಕನಿಷ್ಠ 2h ಎತ್ತರದ ಶೃಂಗವನ್ನು ತಲುಪಲಾಗುತ್ತದೆ. ಎಲ್ಲಾ ನೋಡ್ಗಳು ಕನಿಷ್ಠ 1 ಎತ್ತರವನ್ನು ಹೊಂದಿವೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ ಮತ್ತು ಆದ್ದರಿಂದ ಇದನ್ನು i ಬಾರಿ ಮಾಡಿದ ನಂತರ, ನಾವು ಕನಿಷ್ಠ 2i ಎತ್ತರದ ನೋಡ್ ಅನ್ನು ತಲುಪುತ್ತೇವೆ ಮತ್ತು ಆದ್ದರಿಂದ ನಾವು ಇದನ್ನು ಗರಿಷ್ಠ ಲಾಗ್ n ಬಾರಿ ಮಾಡಬೇಕಾಗಿದೆ. ಇದು ನಮಗೆ ಒ (ಲಾಗ್ ಎನ್) ಪ್ರಶ್ನೆಯ ಸಮಯವನ್ನು ನೀಡುತ್ತದೆ. ಹಂತ 3: ಎರಡು ವಿಧಾನಗಳನ್ನು ಸಂಯೋಜಿಸುವುದು ಲ್ಯಾಡರ್ ಅಲ್ಗಾರಿದಮ್ ತನ್ನದೇ ಆದ ತಂತ್ರವನ್ನು ಮಾಡುವುದಿಲ್ಲ ಎಂದು ಅದು ತಿರುಗುತ್ತದೆ. ವಾಸ್ತವವಾಗಿ ಜಂಪ್ ಪಾಯಿಂಟರ್ ಅಲ್ಗಾರಿದಮ್ ಮತ್ತು ಲ್ಯಾಡರ್ ಅಲ್ಗಾರಿದಮ್ ಒಂದಕ್ಕೊಂದು ಪೂರಕವಾಗಿವೆ. ಎರಡು ಕ್ರಮಾವಳಿಗಳು ವಿರುದ್ಧ ದಿಕ್ಕುಗಳಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆಃ ಜಂಪ್ ಪಾಯಿಂಟರ್ ಕ್ರಮಾವಳಿಯು ಹಾಪ್ಗಳನ್ನು ಘಾತೀಯವಾಗಿ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ ಮತ್ತು ಲ್ಯಾಡರ್ ಕ್ರಮಾವಳಿಯು ಹಾಪ್ಗಳನ್ನು ಘಾತೀಯವಾಗಿ ಹೆಚ್ಚಿಸುತ್ತದೆ. ಎರಡು ಕ್ರಮಾವಳಿಗಳ ಸಂಯೋಜನೆಯು ಓ (1) ಸಮಯದಲ್ಲಿ ಪ್ರಶ್ನೆಗಳಿಗೆ ಉತ್ತರಿಸಬಹುದು. ಒಂದೇ ಜಂಪ್ ಪಾಯಿಂಟರ್ ಯಾವುದೇ ಪ್ರಶ್ನೆಯನ್ನು ಕನಿಷ್ಠ ಅರ್ಧದಾರಿಯಲ್ಲೇ ಮರದ ಮೇಲೆ ಕೊಂಡೊಯ್ಯುತ್ತದೆ ಮತ್ತು ನಂತರ ಕೇವಲ ಒಂದು ಏಣಿಯ ಮೇಲೆ ಹತ್ತುವುದು ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸುತ್ತದೆ. ಇದು ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಪೂರ್ವ-ಸಂಸ್ಕರಣಾ ಸಮಯ ಮತ್ತು ಒ (1) ಪ್ರಶ್ನೆಯ ಸಮಯಕ್ಕೆ ಕಾರಣವಾಗುತ್ತದೆ. ನಾಲ್ಕು ರಷ್ಯನ್ನರ ವಿಧಾನವನ್ನು ಅನ್ವಯಿಸುವ ಮೂಲಕ ಪೂರ್ವ-ಸಂಸ್ಕರಣೆಯನ್ನು ಓ (ಎನ್) ಸಮಯಕ್ಕೆ ಮತ್ತಷ್ಟು ಕಡಿಮೆ ಮಾಡಬಹುದು, ಇದರಲ್ಲಿ ಮರವನ್ನು ರೇಖೀಯ ಪೂರ್ವ ಸಂಸ್ಕರಣೆಯೊಂದಿಗೆ ಸಣ್ಣ ಮರಕ್ಕೆ ಇಳಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಸಣ್ಣ ಮರಗಳ ಸಂಗ್ರಹವು ಎಲ್ಲಾ ಮರಗಳ ಸಮಗ್ರ ಎಣಿಕೆ ಮತ್ತು ಆ ಮರಗಳ ಪೂರ್ವ ಸಂಸ್ಕರಣೆಯು ಇನ್ನೂ ಓ (ಎನ್) ಸಮಯವಾಗಿರುತ್ತದೆ. ಗಾತ್ರದ ಮರಗಳು (ಲಾಗ್ ಎನ್)/4 ಸಾಕು. ಬರ್ಕ್ಮನ್ ಮತ್ತು ವಿಶ್ಕಿನ್ ಅವರ ಪರಿಹಾರವು ಬರ್ಕ್ಮನ್ ಮತ್ತು ವಿಶ್ಕಿನ್ ಅವರ ಕಾರಣದಿಂದಾಗಿ ವಿಭಿನ್ನ ಪರಿಹಾರವಾಗಿದೆ. ಈ ಪರಿಹಾರವು ಮರಗಳನ್ನು ಸಂಸ್ಕರಿಸುವ ಯೂಲರ್ ಪ್ರವಾಸ ತಂತ್ರವನ್ನು ಆಧರಿಸಿದೆ. ಮುಖ್ಯ ಅವಲೋಕನವೆಂದರೆ ಎಲ್ಎ (ವಿ, ಡಿ) ಎಂಬುದು ವಿ ಕೊನೆಯ ಬಾರಿಗೆ ಕಾಣಿಸಿಕೊಂಡ ನಂತರ ಯೂಲರ್ ಪ್ರವಾಸದಲ್ಲಿ ಕಾಣಿಸಿಕೊಳ್ಳುವ ಡೆಪ್ತ್ ಡಿ ಯ ಮೊದಲ ನೋಡ್ ಆಗಿದೆ. ಹೀಗಾಗಿ, ಯೂಲರ್ ಪ್ರವಾಸ ಮತ್ತು ಆಳದ ಬಗ್ಗೆ ಸಂಬಂಧಿತ ಮಾಹಿತಿಯನ್ನು ನಿರ್ಮಿಸುವ ಮೂಲಕ, ಸಮಸ್ಯೆಯನ್ನು ಫೈಂಡ್ ಸ್ಮಾಲರ್ (ಎಫ್ಎಸ್) ಎಂಬ ಹೆಸರಿನ ಸರಣಿಗಳ ಮೇಲಿನ ಪ್ರಶ್ನೆಯಾಗಿ ಕಡಿಮೆ ಮಾಡಲಾಗುತ್ತದೆ. ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಎ, ಮತ್ತು ಮಾನ್ಯ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಐ, ಎಫ್ಎಸ್ (ಐ, ಎಕ್ಸ್) ಮೊದಲ ಸೂಚ್ಯಂಕ ಜೆ> ಐ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ, ಅಂದರೆ ಎ [ಐ] <ಎಕ್ಸ್ (ಇಲ್ಲಿ, ನಾವು ಎಕ್ಸ್ = ಡಿ + 1 ಅನ್ನು ಬಳಸುತ್ತೇವೆ). ಎಫ್ಎಸ್ ಸಮಸ್ಯೆಗೆ ಪರಿಣಾಮಕಾರಿ ಪರಿಹಾರವು ಸಾಮಾನ್ಯವಾಗಿ ಕಠಿಣವಾಗಿದೆ, ಆದರೆ ಯೂಲರ್ ಪ್ರವಾಸಗಳಿಂದ ಉದ್ಭವಿಸುವ ವಿಶೇಷ ಪ್ರಕರಣಕ್ಕೆ ಸುಲಭವಾಗಿದೆ; ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಪಕ್ಕದ ಅಂಶಗಳು ±1 ರಿಂದ ಭಿನ್ನವಾಗಿರುತ್ತವೆ. ಈ ಕಲ್ಪನೆಯು ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಸಂಕೀರ್ಣತೆಯ ಪೂರ್ವ ಸಂಸ್ಕರಣ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಒ (1) ಪ್ರಶ್ನೆಯ ಸಮಯವನ್ನು ನೀಡುತ್ತದೆ. ನಾಲ್ಕು ರಷ್ಯನ್ನರ ವಿಧಾನದ ಅನ್ವಯದಿಂದ ಪೂರ್ವ ಸಂಸ್ಕರಣಾ ಸಮಯವನ್ನು ಒ (ಎನ್) ಗೆ ಸುಧಾರಿಸಲಾಗಿದೆ. ಶ್ರೇಣಿ ಪ್ರಶ್ನೆ (ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನ) ಕಡಿಮೆ ಸಾಮಾನ್ಯ ಪೂರ್ವಜ ಉಲ್ಲೇಖಗಳು ಸೈದ್ಧಾಂತಿಕ ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನ ಮರಗಳು (ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ) ಅನ್ನು ಸಹ ನೋಡಿ.