Tango tree
ಟ್ಯಾಂಗೋ ಮರವು ಎರಿಕ್ ಡಿ. ಡೆಮೈನ್, ಡಿಯೋನ್ ಹಾರ್ಮನ್, ಜಾನ್ ಇಕಾನೊ ಮತ್ತು ಮಿಹೈ ಪಟ್ರಾಸ್ಕು ಅವರು 2004ರಲ್ಲಿ ಪ್ರಸ್ತಾಪಿಸಿದ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ ಒಂದು ವಿಧವಾಗಿದೆ. ಟ್ಯಾಂಗೋವು ಸಾಂಕೇತಿಕವಾಗಿರುವ ಬ್ಯೂನಸ್ ಐರಿಸ್ನ ಹೆಸರನ್ನು ಇದಕ್ಕೆ ಇಡಲಾಗಿದೆ. ಇದು ಆಫ್ಲೈನ್ ಆಪ್ಟಿಮಲ್ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಗೆ ಹೋಲಿಸಿದರೆ ಸ್ಪರ್ಧಾತ್ಮಕ ಅನುಪಾತವನ್ನು ಸಾಧಿಸುವ ಆನ್ಲೈನ್ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಆಗಿದ್ದು, ಪ್ರತಿ ನೋಡ್ಗೆ ಹೆಚ್ಚುವರಿ ಬಿಟ್ ಮೆಮೊರಿಯನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತದೆ. ಇದು ಹಿಂದಿನ ಅತ್ಯಂತ ಪ್ರಸಿದ್ಧವಾದ ಸ್ಪರ್ಧಾತ್ಮಕ ಅನುಪಾತಕ್ಕಿಂತ ಸುಧಾರಿಸಿದೆ. ಸ್ಟ್ರಕ್ಚರ್ ಟ್ಯಾಂಗೋ ಮರಗಳು ಬೈನರಿ ಸರ್ಚ್ ಮರವನ್ನು ಆದ್ಯತೆಯ ಮಾರ್ಗಗಳ ಗುಂಪಾಗಿ ವಿಭಜಿಸುವ ಮೂಲಕ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ, ಅವು ಸ್ವತಃ ಸಹಾಯಕ ಮರಗಳಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುತ್ತವೆ (ಆದ್ದರಿಂದ ಟ್ಯಾಂಗೋ ಮರವನ್ನು ಮರಗಳ ಮರವಾಗಿ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ). ಉಲ್ಲೇಖ ಮರ ಟ್ಯಾಂಗೋ ಮರವನ್ನು ನಿರ್ಮಿಸಲು, ನಾವು ಉಲ್ಲೇಖ ಮರ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಸಂಪೂರ್ಣ ಬೈನರಿ ಸರ್ಚ್ ಮರವನ್ನು ಅನುಕರಿಸುತ್ತೇವೆ, ಇದು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಸಾಂಪ್ರದಾಯಿಕ ಬೈನರಿ ಸರ್ಚ್ ಮರವಾಗಿದೆ. ಈ ಮರವು ನಿಜವಾದ ಅನುಷ್ಠಾನದಲ್ಲಿ ಎಂದಿಗೂ ಕಾಣಿಸುವುದಿಲ್ಲ, ಆದರೆ ಈ ಕೆಳಗಿನ ಟ್ಯಾಂಗೋ ಮರದ ತುಂಡುಗಳ ಹಿಂದಿನ ಪರಿಕಲ್ಪನಾ ಆಧಾರವಾಗಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಉಲ್ಲೇಖ ಮರದ ಎತ್ತರ. ಇದು ಉದ್ದವಾದ ಮಾರ್ಗದ ಉದ್ದಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಅತಿದೊಡ್ಡ ಸಹಾಯಕ ಮರದ ಗಾತ್ರಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಸಹಾಯಕ ಮರಗಳನ್ನು ಸಮಂಜಸವಾಗಿ ಸಮತೋಲನದಲ್ಲಿಡುವ ಮೂಲಕ, ಸಹಾಯಕ ಮರಗಳ ಎತ್ತರವನ್ನು ಇದಕ್ಕೆ ಸೀಮಿತಗೊಳಿಸಬಹುದು ಇದು ಅಲ್ಗಾರಿದಮ್ನ ಕಾರ್ಯಕ್ಷಮತೆಯ ಖಾತರಿಗಳ ಮೂಲವಾಗಿದೆ. ಆದ್ಯತೆಯ ಮಾರ್ಗಗಳು ಮೊದಲನೆಯದಾಗಿ, ನಾವು ಪ್ರತಿ ನೋಡ್ಗೆ ಅದರ ಆದ್ಯತೆಯ ಚೈಲ್ಡ್ ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ, ಇದು ಸಾಂಪ್ರದಾಯಿಕ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲುಕ್ಅಪ್ನಿಂದ ಅನೌಪಚಾರಿಕವಾಗಿ ಇತ್ತೀಚೆಗೆ ಭೇಟಿ ನೀಡಿದ ಚೈಲ್ಡ್ ಆಗಿದೆ. ಹೆಚ್ಚು ಔಪಚಾರಿಕವಾಗಿ, ಎಲ್ (ಎಡ) ಮತ್ತು ಆರ್ (ಬಲ) ಮಕ್ಕಳೊಂದಿಗೆ ಪಿ ನಲ್ಲಿ ಬೇರೂರಿರುವ ಸಬ್ಟ್ರೀ ಟಿ ಅನ್ನು ಪರಿಗಣಿಸಿ. ಟಿ ಯಲ್ಲಿ ಇತ್ತೀಚೆಗೆ ಪ್ರವೇಶಿಸಲಾದ ನೋಡ್ ಆರ್ ನಲ್ಲಿ ಬೇರೂರಿರುವ ಸಬ್ಟ್ರೀಯಲ್ಲಿದ್ದರೆ ನಾವು ಆರ್ ಅನ್ನು ಪಿ ಯ ಆದ್ಯತೆಯ ಚೈಲ್ಡ್ ಎಂದು ಹೊಂದಿಸುತ್ತೇವೆ ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಎಲ್ ಅನ್ನು ಆದ್ಯತೆಯ ಚೈಲ್ಡ್ ಎಂದು ಹೊಂದಿಸುತ್ತೇವೆ. ಇತ್ತೀಚೆಗೆ ಪ್ರವೇಶಿಸಲಾದ ಟಿ ಯ ನೋಡ್ ಸ್ವತಃ ಪಿ ಆಗಿದ್ದರೆ, ವ್ಯಾಖ್ಯಾನದ ಪ್ರಕಾರ ಎಲ್ ಆದ್ಯತೆಯ ಚೈಲ್ಡ್ ಆಗಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಆದ್ಯತೆಯ ಮಾರ್ಗವನ್ನು ಮೂಲದಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಎಲೆಯ ನೋಡ್ ಅನ್ನು ತಲುಪುವವರೆಗೆ ಆದ್ಯತೆಯ ಮಕ್ಕಳನ್ನು ಅನುಸರಿಸುವ ಮೂಲಕ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಈ ಮಾರ್ಗದಲ್ಲಿನ ನೋಡ್ಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದರಿಂದ ಮರದ ಉಳಿದ ಭಾಗವು ಹಲವಾರು ಸಬ್ಟ್ರೀಗಳಾಗಿ ವಿಭಜನೆಯಾಗುತ್ತದೆ, ಮತ್ತು ನಾವು ಪ್ರತಿ ಸಬ್ಟ್ರೀ ಮೇಲೆ ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ (ಅದರ ಮೂಲದಿಂದ ಆದ್ಯತೆಯ ಮಾರ್ಗವನ್ನು ರೂಪಿಸುತ್ತದೆ, ಇದು ಸಬ್ಟ್ರೀ ಅನ್ನು ಹೆಚ್ಚು ಸಬ್ಟ್ರೀಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ). ಸಹಾಯಕ ಮರಗಳು ಆದ್ಯತೆಯ ಮಾರ್ಗವನ್ನು ಪ್ರತಿನಿಧಿಸಲು, ನಾವು ಅದರ ನೋಡ್ಗಳನ್ನು ಸಮತೋಲಿತ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀನಲ್ಲಿ, ನಿರ್ದಿಷ್ಟವಾಗಿ ಕೆಂಪು-ಕಪ್ಪು ಮರದಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಆದ್ಯತೆಯ ಮಾರ್ಗ ಪಿ ನಲ್ಲಿರುವ ಪ್ರತಿ ಎಲೆ-ಅಲ್ಲದ ನೋಡ್ ಎನ್ ಗೆ, ಇದು ಆದ್ಯತೆಯಿಲ್ಲದ ಚೈಲ್ಡ್ ಸಿ ಅನ್ನು ಹೊಂದಿದೆ, ಇದು ಹೊಸ ಸಹಾಯಕ ಮರದ ಮೂಲವಾಗಿದೆ. ನಾವು ಈ ಇತರ ಸಹಾಯಕ ಮರದ ಮೂಲವನ್ನು (ಸಿ) ಪಿ ಯಲ್ಲಿ ಎನ್ ಗೆ ಜೋಡಿಸುತ್ತೇವೆ, ಹೀಗಾಗಿ ಸಹಾಯಕ ಮರಗಳನ್ನು ಒಟ್ಟಿಗೆ ಜೋಡಿಸುತ್ತೇವೆ. ನಾವು ಪ್ರತಿ ನೋಡ್ನಲ್ಲಿ ಆ ನೋಡ್ನ ಕೆಳಗಿರುವ ಸಬ್ಟ್ರೀಯಲ್ಲಿನ ನೋಡ್ಗಳ ಕನಿಷ್ಠ ಮತ್ತು ಗರಿಷ್ಠ ಆಳವನ್ನು (ರೆಫರೆನ್ಸ್ ಟ್ರೀಯಲ್ಲಿನ ಆಳ, ಅಂದರೆ) ಸಂಗ್ರಹಿಸುವ ಮೂಲಕ ಸಹಾಯಕ ಮರವನ್ನು ಹೆಚ್ಚಿಸುತ್ತೇವೆ. ಅಲ್ಗಾರಿದಮ್ ಸರ್ಚಿಂಗ್ ಟ್ಯಾಂಗೋ ಮರದಲ್ಲಿ ಒಂದು ಅಂಶವನ್ನು ಹುಡುಕಲು, ನಾವು ಕೇವಲ ಉಲ್ಲೇಖ ಮರವನ್ನು ಹುಡುಕುವುದನ್ನು ಅನುಕರಿಸುತ್ತೇವೆ. ನಾವು ಮೂಲಕ್ಕೆ ಸಂಪರ್ಕಿಸಲಾದ ಆದ್ಯತೆಯ ಮಾರ್ಗವನ್ನು ಹುಡುಕುವ ಮೂಲಕ ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ, ಇದನ್ನು ಆ ಆದ್ಯತೆಯ ಮಾರ್ಗಕ್ಕೆ ಅನುಗುಣವಾದ ಸಹಾಯಕ ಮರವನ್ನು ಹುಡುಕುವ ಮೂಲಕ ಅನುಕರಿಸಲಾಗುತ್ತದೆ. ಸಹಾಯಕ ಮರವು ಅಪೇಕ್ಷಿತ ಅಂಶವನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ, ಬಯಸಿದ ಅಂಶವನ್ನು ಹೊಂದಿರುವ ಉಪವೃಕ್ಷದ ಮೂಲದ ಮೂಲದಲ್ಲಿ ಹುಡುಕಾಟವು ಕೊನೆಗೊಳ್ಳುತ್ತದೆ (ಮತ್ತೊಂದು ಆದ್ಯತೆಯ ಮಾರ್ಗದ ಆರಂಭ), ಆದ್ದರಿಂದ ನಾವು ಆ ಆದ್ಯತೆಯ ಮಾರ್ಗಕ್ಕಾಗಿ ಸಹಾಯಕ ಮರವನ್ನು ಹುಡುಕುವ ಮೂಲಕ ಮುಂದುವರಿಯುತ್ತೇವೆ, ಇತ್ಯಾದಿ. ನವೀಕರಿಸುವುದು ಟ್ಯಾಂಗೋ ಮರದ ರಚನೆಯನ್ನು ಕಾಪಾಡಿಕೊಳ್ಳಲು (ಸಹಾಯಕ ಮರಗಳು ಆದ್ಯತೆಯ ಮಾರ್ಗಗಳಿಗೆ ಅನುಗುಣವಾಗಿರುತ್ತವೆ), ಹುಡುಕಾಟಗಳ ಪರಿಣಾಮವಾಗಿ ಆದ್ಯತೆಯ ಮಕ್ಕಳು ಬದಲಾದಾಗಲೆಲ್ಲಾ ನಾವು ಕೆಲವು ನವೀಕರಣ ಕಾರ್ಯಗಳನ್ನು ಮಾಡಬೇಕು. ಆದ್ಯತೆಯ ಮಗು ಬದಲಾದಾಗ, ಆದ್ಯತೆಯ ಮಾರ್ಗದ ಮೇಲಿನ ಭಾಗವು ಕೆಳಗಿನ ಭಾಗದಿಂದ ಬೇರ್ಪಡುತ್ತದೆ (ಇದು ತನ್ನದೇ ಆದ ಆದ್ಯತೆಯ ಮಾರ್ಗವಾಗುತ್ತದೆ) ಮತ್ತು ಮತ್ತೊಂದು ಆದ್ಯತೆಯ ಮಾರ್ಗಕ್ಕೆ ಮರುಹೊಂದಿಸಲಾಗುತ್ತದೆ (ಇದು ಹೊಸ ಕೆಳಗಿನ ಭಾಗವಾಗುತ್ತದೆ). ಇದನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡಲು, ನಾವು ನಮ್ಮ ಸಹಾಯಕ ಮರಗಳ ಮೇಲೆ ಕಟ್ ಮತ್ತು ಜಾಯಿನ್ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ. ನಮ್ಮ ಜಾಯಿನ್ ಕಾರ್ಯಾಚರಣೆಯಲ್ಲಿ ಸೇರಿಕೊಳ್ಳಿ ಒಂದರ ಮೇಲಿನ ನೋಡ್ (ಉಲ್ಲೇಖ ಮರದಲ್ಲಿ) ಇನ್ನೊಂದರ ಕೆಳಗಿನ ನೋಡ್ನ ಚೈಲ್ಡ್ (ಮೂಲಭೂತವಾಗಿ, ಅನುಗುಣವಾದ ಆದ್ಯತೆಯ ಮಾರ್ಗಗಳನ್ನು ಸಂಯೋಜಿಸಬಹುದು) ಎಂಬ ಗುಣಲಕ್ಷಣವನ್ನು ಹೊಂದಿರುವವರೆಗೆ ಎರಡು ಸಹಾಯಕ ಮರಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ. ಇದು ಕೆಂಪು-ಕಪ್ಪು ಮರಗಳ ಸಂಯೋಜಿತ ಕಾರ್ಯಾಚರಣೆಯ ಆಧಾರದ ಮೇಲೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ, ಇದು ಎರಡು ಮರಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ, ಅವು ಒಂದರ ಎಲ್ಲಾ ಅಂಶಗಳು ಇನ್ನೊಂದರ ಎಲ್ಲಾ ಅಂಶಗಳಿಗಿಂತ ಕಡಿಮೆಯಿರುವ ಗುಣವನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ವಿಭಜನೆಯಾಗುತ್ತವೆ, ಇದು ವ್ಯತಿರಿಕ್ತವಾಗಿದೆ. ರೆಫರೆನ್ಸ್ ಟ್ರೀಯಲ್ಲಿ, ಮೇಲಿನ ಮಾರ್ಗದಲ್ಲಿ ಎರಡು ನೋಡ್ಗಳಿವೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಅದರ ಕೀ-ಮೌಲ್ಯವು ಅವುಗಳ ನಡುವೆ ಇದ್ದರೆ ಮಾತ್ರ ನೋಡ್ ಕೆಳಭಾಗದಲ್ಲಿರುತ್ತದೆ. ಈಗ, ಮೇಲಿನ ಮಾರ್ಗಕ್ಕೆ ಕೆಳಗಿನ ಮಾರ್ಗವನ್ನು ಸೇರಲು, ನಾವು ಆ ಎರಡು ನೋಡ್ಗಳ ನಡುವೆ ಮೇಲಿನ ಮಾರ್ಗವನ್ನು ವಿಭಜಿಸುತ್ತೇವೆ, ನಂತರ ಕೆಳಗಿನ ಮಾರ್ಗದ ಸಹಾಯಕ ಮರದ ಎರಡೂ ಬದಿಗಳಲ್ಲಿ ಎರಡು ಸಹಾಯಕ ಮರಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತೇವೆ, ಮತ್ತು ನಾವು ನಮ್ಮ ಅಂತಿಮ, ಸಂಯೋಜಿತ ಸಹಾಯಕ ಮರವನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಕಟ್ ನಮ್ಮ ಕಟ್ ಕಾರ್ಯಾಚರಣೆಯು ಆದ್ಯತೆಯ ಮಾರ್ಗವನ್ನು ನಿರ್ದಿಷ್ಟ ನೋಡ್ನಲ್ಲಿ ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ, ಮೇಲಿನ ಭಾಗ ಮತ್ತು ಕೆಳಗಿನ ಭಾಗ. ಹೆಚ್ಚು ಔಪಚಾರಿಕವಾಗಿ, ಇದು ಸಹಾಯಕ ಮರವನ್ನು ಎರಡು ಸಹಾಯಕ ಮರಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ, ಅಂದರೆ ಒಂದು ಉಲ್ಲೇಖ ಮರದಲ್ಲಿ ಒಂದು ನಿರ್ದಿಷ್ಟ ಆಳದಲ್ಲಿ ಅಥವಾ ಅದಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಎಲ್ಲಾ ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಇನ್ನೊಂದು ಆ ಆಳಕ್ಕಿಂತ ಕೆಳಗಿರುವ ಎಲ್ಲಾ ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಜಾಯಿನ್ ನಲ್ಲಿರುವಂತೆ, ಮೇಲಿನ ಭಾಗವು ಕೆಳಗಿನ ಭಾಗವನ್ನು ಬ್ರಾಕೆಟ್ ಮಾಡುವ ಎರಡು ನೋಡ್ಗಳನ್ನು ಹೊಂದಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಹೀಗಾಗಿ, ನಾವು ಮಾರ್ಗವನ್ನು ಮೂರು ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಲು ಈ ಎರಡು ನೋಡ್ಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದನ್ನೂ ಸರಳವಾಗಿ ವಿಭಜಿಸಬಹುದು, ನಂತರ ಎರಡು ಹೊರಭಾಗಗಳನ್ನು ಸಂಯೋಜಿಸಬಹುದು, ಆದ್ದರಿಂದ ನಾವು ಬಯಸಿದಂತೆ ಮೇಲ್ಭಾಗ ಮತ್ತು ಕೆಳಭಾಗ ಎಂಬ ಎರಡು ಭಾಗಗಳೊಂದಿಗೆ ಕೊನೆಗೊಳ್ಳುತ್ತೇವೆ. ವಿಶ್ಲೇಷಣೆ ಟ್ಯಾಂಗೋ ಮರಗಳ ಸ್ಪರ್ಧಾತ್ಮಕ ಅನುಪಾತವನ್ನು ಬಂಧಿಸುವ ಸಲುವಾಗಿ, ನಾವು ಮಾನದಂಡವಾಗಿ ಬಳಸುವ ಅತ್ಯುತ್ತಮ ಆಫ್ಲೈನ್ ಮರದ ಕಾರ್ಯಕ್ಷಮತೆಯ ಮೇಲೆ ಕಡಿಮೆ ಮಿತಿಯನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು. ಒಮ್ಮೆ ನಾವು ಟ್ಯಾಂಗೋ ಮರದ ಕಾರ್ಯಕ್ಷಮತೆಯ ಮೇಲೆ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಕಂಡುಕೊಂಡರೆ, ನಾವು ಅವುಗಳನ್ನು ಸ್ಪರ್ಧಾತ್ಮಕ ಅನುಪಾತಕ್ಕೆ ಬದ್ಧವಾಗಿ ವಿಂಗಡಿಸಬಹುದು. ಆಪ್ಟಿಮಲ್ ಆಫ್ಲೈನ್ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಮಾಡಿದ ಕೆಲಸದ ಮೇಲೆ ಕಡಿಮೆ ಮಿತಿಯನ್ನು ಕಂಡುಹಿಡಿಯಲು, ನಾವು ಮತ್ತೆ ಆದ್ಯತೆಯ ಮಕ್ಕಳ ಕಲ್ಪನೆಯನ್ನು ಬಳಸುತ್ತೇವೆ. ಪ್ರವೇಶ ಅನುಕ್ರಮವನ್ನು (ಹುಡುಕಾಟಗಳ ಅನುಕ್ರಮ) ಪರಿಗಣಿಸುವಾಗ, ರೆಫರೆನ್ಸ್ ಟ್ರೀ ನೋಡ್ನ ಆದ್ಯತೆಯ ಚೈಲ್ಡ್ ಸ್ವಿಚ್ಗಳು ಎಷ್ಟು ಬಾರಿ ಬದಲಾಗುತ್ತವೆ ಎಂಬುದನ್ನು ನಾವು ಗಮನಿಸುತ್ತೇವೆ. ಸ್ವಿಚ್ಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆಯು (ಎಲ್ಲಾ ನೋಡ್ಗಳ ಮೇಲೆ ಸಂಕ್ಷೇಪಿಸಲಾಗಿದೆ) ನೀಡಲಾದ ಪ್ರವೇಶ ಅನುಕ್ರಮದಲ್ಲಿ ಯಾವುದೇ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಅಲ್ಗಾರಿದಮ್ ಮಾಡಿದ ಕೆಲಸದ ಮೇಲೆ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಲೋವರ್ ಬೌಂಡ್ ಅನ್ನು ನೀಡುತ್ತದೆ. ಇದನ್ನು ಇಂಟರ್ಲೀವ್ ಲೋವರ್ ಬೌಂಡ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಟ್ಯಾಂಗೋ ಮರ ಇದನ್ನು ಟ್ಯಾಂಗೋ ಮರಗಳಿಗೆ ಸಂಪರ್ಕಿಸುವ ಸಲುವಾಗಿ, ನಿರ್ದಿಷ್ಟ ಪ್ರವೇಶ ಅನುಕ್ರಮಕ್ಕಾಗಿ ಟ್ಯಾಂಗೋ ಮರವು ಮಾಡಿದ ಕೆಲಸದ ಮೇಲೆ ನಾವು ಮೇಲಿನ ಮಿತಿಯನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ. ನಮ್ಮ ಮೇಲಿನ ಮಿತಿಯು ಇರುತ್ತದೆ, ಅಲ್ಲಿ k ಎಂಬುದು ಇಂಟರ್ಲೀವ್ಗಳ ಸಂಖ್ಯೆ. ಒಟ್ಟು ವೆಚ್ಚವನ್ನು ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ, ಅಂಶವನ್ನು ಹುಡುಕುವುದು ಮತ್ತು ಸರಿಯಾದ ಬದಲಾವಣೆಗಳನ್ನು ನಿರ್ವಹಿಸಲು ಟ್ಯಾಂಗೋ ಮರದ ರಚನೆಯನ್ನು ನವೀಕರಿಸುವುದು (ಆದ್ಯತೆಯ ಮಕ್ಕಳನ್ನು ಬದಲಾಯಿಸುವುದು ಮತ್ತು ಆದ್ಯತೆಯ ಮಾರ್ಗಗಳನ್ನು ಮರು-ವ್ಯವಸ್ಥೆಗೊಳಿಸುವುದು). ಹುಡುಕಾಟವು ಈ ಮಿತಿಯಲ್ಲಿ ಸರಿಹೊಂದುತ್ತದೆ ಎಂಬುದನ್ನು ನೋಡಲು, ಪ್ರತಿ ಬಾರಿ ಸಹಾಯಕ ಮರದ ಹುಡುಕಾಟವು ವಿಫಲವಾದಾಗ ಮತ್ತು ನಾವು ಮುಂದಿನ ಸಹಾಯಕ ಮರಕ್ಕೆ ಹೋಗಬೇಕಾದಾಗ, ಅದು ಆದ್ಯತೆಯ ಚೈಲ್ಡ್ ಸ್ವಿಚ್ಗೆ ಕಾರಣವಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಸರಳವಾಗಿ ಗಮನಿಸಿ (ಪೋಷಕರು ಆದ್ಯತೆ ನೀಡಿದ ಮಾರ್ಗವು ಈಗ ಮಗುವಿನ ಆದ್ಯತೆಯ ಮಾರ್ಗವನ್ನು ಸೇರಲು ನಿರ್ದೇಶನಗಳನ್ನು ಬದಲಾಯಿಸುತ್ತದೆ). ಕೊನೆಯದನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಸಹಾಯಕ ಮರಗಳ ಹುಡುಕಾಟಗಳು ವಿಫಲವಾಗುವುದರಿಂದ (ಹುಡುಕಾಟವು ಯಶಸ್ವಿಯಾದ ನಂತರ ನಾವು ನಿಲ್ಲುತ್ತೇವೆ, ಸ್ವಾಭಾವಿಕವಾಗಿ), ನಾವು ಸಹಾಯಕ ಮರಗಳನ್ನು ಹುಡುಕುತ್ತೇವೆ. ಪ್ರತಿ ಹುಡುಕಾಟವು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಏಕೆಂದರೆ ಸಹಾಯಕ ಮರದ ಗಾತ್ರವು ಉಲ್ಲೇಖ ಮರದ ಎತ್ತರದಿಂದ ಸುತ್ತುವರಿಯಲ್ಪಟ್ಟಿದೆ. ನವೀಕರಣ ವೆಚ್ಚವು ಈ ಮಿತಿಯೊಳಗೆ ಸರಿಹೊಂದುತ್ತದೆ, ಏಕೆಂದರೆ ನಾವು ಭೇಟಿ ನೀಡಿದ ಪ್ರತಿ ಸಹಾಯಕ ಮರಕ್ಕೆ ಕೇವಲ ಒಂದು ಕಟ್ ಮತ್ತು ಒಂದು ಜಾಯಿನ್ ಅನ್ನು ಮಾತ್ರ ಮಾಡಬೇಕಾಗುತ್ತದೆ. ಒಂದೇ ಕಟ್ ಅಥವಾ ಜಾಯಿನ್ ಕಾರ್ಯಾಚರಣೆಯು ನಿರಂತರ ಸಂಖ್ಯೆಯ ಹುಡುಕಾಟಗಳು, ಸ್ಪ್ಲಿಟ್ಗಳು ಮತ್ತು ಕಾಂಕ್ಯಾಟೆನೇಟ್ಗಳನ್ನು ಮಾತ್ರ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಪ್ರತಿಯೊಂದೂ ಸಹಾಯಕ ಮರದ ಗಾತ್ರದಲ್ಲಿ ಲಾಗರಿಥಮಿಕ್ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಆದ್ದರಿಂದ ನಮ್ಮ ನವೀಕರಣ ವೆಚ್ಚವು. ಸ್ಪರ್ಧಾತ್ಮಕ ಅನುಪಾತದ ಟ್ಯಾಂಗೋ ಮರಗಳು-ಸ್ಪರ್ಧಾತ್ಮಕವಾಗಿವೆ, ಏಕೆಂದರೆ ಆಪ್ಟಿಮಲ್ ಆಫ್ಲೈನ್ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಮಾಡಿದ ಕೆಲಸವು ಕನಿಷ್ಠ k ನಲ್ಲಿ ರೇಖೀಯವಾಗಿರುತ್ತದೆ (ಆದ್ಯತೆಯ ಚೈಲ್ಡ್ ಸ್ವಿಚ್ಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆ), ಮತ್ತು ಟ್ಯಾಂಗೋ ಮರವು ಮಾಡಿದ ಕೆಲಸವು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಪ್ಲೇ ಟ್ರೀ ಆಪ್ಟಿಮಲ್ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಕೆಂಪು-ಕಪ್ಪು ಮರ ಮರ (ದತ್ತಾಂಶ ರಚನೆ) ಉಲ್ಲೇಖಗಳು ಬೈನರಿ ಮರಗಳು ಹುಡುಕಾಟ ಮರಗಳು