ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ)

ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ( ಬಿಎಸ್‌ಟಿ ), ಆರ್ಡರ್ ಮಾಡಿದ ಅಥವಾ ವಿಂಗಡಿಸಲಾದ ಬೈನರಿ ಟ್ರೀ ಎಂದೂ ಕರೆಯಲ್ಪಡುತ್ತದೆ, ಇದು ಬೇರೂರಿರುವ ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆ (ಡೇಟಾ ಸ್ಟ್ರಕ್ಚರ್) ಯಾಗಿದ್ದು, ಪ್ರತಿ ಆಂತರಿಕ ನೋಡ್‌ನ ಕೀ ಆಯಾ ನೋಡ್‌ನ ಎಡ ಸಬ್‌ಟ್ರೀಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಕೀಗಳಿಗಿಂತ ದೊಡ್ಡದಾಗಿರುತ್ತದೆ ಮತ್ತು ಅದರ ಬಲ ಸಬ್ ಟ್ರೀಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಕೀಗಳಿಗಿಂತ ಚಿಕ್ಕದಾಗಿರುತ್ತದೆ. ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀನಲ್ಲಿನ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಟ್ರೀ ನ ಎತ್ತರಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ರೇಖೀಯವಾಗಿರುತ್ತದೆ ಅಂದರೆ ಲೀನಿಯರ್ ಆಗಿರುತ್ತದೆ.

ಚಿತ್ರ 1: ಗಾತ್ರ 9 ಮತ್ತು ಆಳ 3 ರ ಬೈನರಿ ಹುಡುಕಾಟ ಮರ, ಮೂಲದಲ್ಲಿ 8. ಎಲೆಗಳನ್ನು ಎಳೆಯಲಾಗಿಲ್ಲ.

ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ವೇಗದ ಹುಡುಕಾಟ, ಸೇರ್ಪಡೆ ಮತ್ತು ಡೇಟಾ ಐಟಂಗಳನ್ನು ತೆಗೆದುಹಾಕಲು ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಅನುಮತಿಸುತ್ತದೆ. BST ಯಲ್ಲಿನ ನೋಡ್‌ಗಳನ್ನು ಹಾಕಿರುವುದರಿಂದ ಪ್ರತಿ ಹೋಲಿಕೆಯು ಉಳಿದಿರುವ ಟ್ರೀ ನ ಅರ್ಧದಷ್ಟು ಭಾಗವನ್ನು ಬಿಟ್ಟುಬಿಡುತ್ತದೆ, ಲುಕಪ್ ಕಾರ್ಯಕ್ಷಮತೆಯು ಬೈನರಿ ಲಾಗರಿಥಮ್‌ಗೆ ಅನುಪಾತದಲ್ಲಿರುತ್ತದೆ. ಲೇಬಲ್ ಮಾಡಲಾದ ಡೇಟಾದ ಸಮರ್ಥ ಸಂಗ್ರಹಣೆಯ ಸಮಸ್ಯೆಗಾಗಿ 1960 ರ ದಶಕದಲ್ಲಿ BST ಗಳನ್ನು ರೂಪಿಸಲಾಯಿತು ಮತ್ತು ಕಾನ್ವೇ ಬರ್ನರ್ಸ್-ಲೀ ಮತ್ತು ಡೇವಿಡ್ ವೀಲರ್‌ಗೆ ಅರ್ಪಿಸಲಾಯಿತು.

ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ ಕಾರ್ಯಕ್ಷಮತೆಯು ಟ್ರೀಯೊಳಗೆ ನೋಡ್‌ಗಳ ಅಳವಡಿಕೆಯ ಕ್ರಮವನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ. ಏಕೆಂದರೆ ಅನಿಯಂತ್ರಿತ ಅಳವಡಿಕೆಗಳು ಅವನತಿಗೆ ಕಾರಣವಾಗಬಹುದು; ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ ಹಲವಾರು ಮಾರ್ಪಾಡುಗಳನ್ನು ಖಾತರಿಪಡಿಸಿದ ಕಡಿಮೆ ಕಾರ್ಯಕ್ಷಮತೆಯೊಂದಿಗೆ ನಿರ್ಮಿಸಬಹುದು. ಮೂಲ ಕಾರ್ಯಾಚರಣೆಗಳು ಇದರಲ್ಲಿ ಸೇರಿವೆ: ಹುಡುಕಾಟ, ಅಡ್ಡಹಾಯುವಿಕೆ, ಸೇರಿಸು ಮತ್ತು ಅಳಿಸಿ. ಖಾತರಿಪಡಿಸಿದ ಕಡಿಮೆ ಸಂಕೀರ್ಣತೆಗಳೊಂದಿಗೆ BST ಗಳು ವಿಂಗಡಿಸದ ರಚನೆಗಿಂತ ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ, ಇದು ಲೀನಿಯರ್ ಹುಡುಕಾಟ ಸಮಯದ ಅಗತ್ಯವಿರುತ್ತದೆ.