[Powered by Google Translate] ನೀವು ಕಂಪ್ಯೂಟರ್ ಎಲ್ಲಾ ನಿಮ್ಮ ಕುಟುಂಬದ ಸದಸ್ಯರು ಹೇಗೆ ಪ್ರತಿನಿಧಿಸುತ್ತದೆ? ನಾವು ಸರಳವಾಗಿ, ಪಟ್ಟಿಯನ್ನು ಬಳಸಬಹುದಿತ್ತು ಆದರೆ ಸ್ಪಷ್ಟ ವ್ಯವಸ್ಥೆ ಇಲ್ಲಿ ಇಲ್ಲ. 

ನಮಗೆ ನಿಮ್ಮ ಮುತ್ತಜ್ಜಿ, ಆಲಿಸ್ ಆರಂಭವಾಗಿ ನೀವು ಹೇಳಬಹುದು. ಆಕೆ 2 ಮಕ್ಕಳು, ಬಾಬ್ ಹೊಂದಿದೆ ಮತ್ತು ನಿಮ್ಮ ಅಜ್ಜ, ಚಾರ್ಲಿ. ಚಾರ್ಲಿ, 3 ಮಕ್ಕಳಿದ್ದಾರೆ ನಿಮ್ಮ ಚಿಕ್ಕಪ್ಪ, ಡೇವ್, ನಿಮ್ಮ ಚಿಕ್ಕಮ್ಮ, ಈವ್, ಮತ್ತು ನಿಮ್ಮ ತಂದೆ, ಫ್ರೆಡ್. ನೀವು ಫ್ರೆಡ್ ಒಬ್ಬಳೇ ಇವೆ. 

ಏಕೆ ಈ ರೀತಿ ನಿಮ್ಮ ಕುಟುಂಬ ಸದಸ್ಯರು ಸಂಘಟಿಸಲು ಎಂದು ಸರಳ ಪಟ್ಟಿ ಪ್ರಾತಿನಿಧ್ಯ ಉತ್ತಮ ಎಂದು? ಒಂದು ಕಾರಣವೆಂದರೆ ಈ ಕ್ರಮಾನುಗತ, ಒಂದು ಎಂಬ 'ಮರ' ಸರಳ ಪಟ್ಟಿಗಿಂತ ಹೆಚ್ಚು ಮಾಹಿತಿಯನ್ನು ಒಳಗೊಂಡಿದೆ. ನಾವು ಎಲ್ಲರೂ ನಡುವೆ ಕೌಟುಂಬಿಕ ಸಂಬಂಧಗಳು ತಿಳಿದಿದೆ ಕೇವಲ ಮರದ ಪರೀಕ್ಷಿಸುತ್ತವೆ. ಸಹ, ಇದು ವೇಗವನ್ನು ಮಾಡಬಹುದು ಲುಕ್ ಅಪ್ ಸಮಯ ಮಹತ್ತರವಾಗಿ, ಮರದ ಅಕ್ಷಾಂಶ ಪ್ರತ್ಯೇಕಿಸಲ್ಪಡುತ್ತವೆ ವೇಳೆ. 

ನಾವು ಇಲ್ಲಿ ಆ ಲಾಭ ಪಡೆಯಲು ಸಾಧ್ಯವಿಲ್ಲ, ಆದರೆ ನಾವು ಶೀಘ್ರದಲ್ಲೇ ಈ ಉದಾಹರಣೆ ನೋಡುತ್ತಾರೆ. ಪ್ರತಿ ವ್ಯಕ್ತಿಯ ಮರದ ಮೇಲೆ ಒಂದು ನೋಡ್ ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ನೋಡ್ ಚೈಲ್ಡ್ ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರಬಹುದು ಜೊತೆಗೆ ಪೋಷಕರು ನೋಡ್ ಮಾಹಿತಿ. ಈ, ತಾಂತ್ರಿಕ ಪದಗಳು ಕುಟುಂಬಗಳು ಜೊತೆಗೆ ವಿಷಯಗಳಿಗೆ ಮರಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಸಹ. ಆಲಿಸ್ಳ ನೋಡ್, 2 ಮಕ್ಕಳು ಮತ್ತು ಪೋಷಕರು ಹೊಂದಿದೆ ಚಾರ್ಲಿಯ ನೋಡ್ 3 ಮಕ್ಕಳು ಮತ್ತು 1 ಮೂಲ ಹೊಂದಿದೆ. 

ಒಂದು ಲೀಫ್ ನೋಡ್ ಯಾವುದೇ ಮಕ್ಕಳನ್ನು ಹೊಂದಿರದ ಒಂದು ಮರದ ಹೊರಗೆ ತುದಿಯಲ್ಲಿ. ಮರದ ತುತ್ತತುದಿಯ ನೋಡ್, ರೂಟ್ ನೋಡ್ ಯಾವುದೇ ಮೂಲ ಹೊಂದಿದೆ. 

ಒಂದು ಅವಳಿ ಮರ, ಮರದ ನಿರ್ದಿಷ್ಟ ಪ್ರಕಾರದ ಇದರಲ್ಲಿ ಪ್ರತಿ ನೋಡ್, ಹೆಚ್ಚೆಂದರೆ, 2 ಮಕ್ಕಳಿದ್ದಾರೆ. ಇಲ್ಲಿ ಸಿ ಒಂದು ಬೈನರಿ ಮರದ ಒಂದು ನೋಡ್ ಆಫ್ struct ಆಗಿದೆ ಪ್ರತಿ ನೋಡ್ ಇದಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ಕೆಲವು ಮಾಹಿತಿ ಹೊಂದಿದೆ ಇತರ ಗ್ರಂಥಿಗಳು ಮತ್ತು 2 ಪಾಯಿಂಟರ್ಸ್. 

ನಮ್ಮ ವಂಶವೃಕ್ಷ ರಲ್ಲಿ, ಸಂಬಂಧಿಸಿದ ಡೇಟಾವನ್ನು ಪ್ರತಿ ವ್ಯಕ್ತಿಯ ಹೆಸರು. ಇದು ಏನು ಮಾಡಬಹುದು ಆದರೂ ಇಲ್ಲಿ, ಒಂದು int ಹೊಂದಿದೆ. ಇದನ್ನು ತಿರುಗುತ್ತದೆ ಎಂದು, ಅವಳಿ ಮರ, ಒಂದು ಕುಟುಂಬಕ್ಕೆ ಉತ್ತಮ ಪ್ರಾತಿನಿಧ್ಯ ನೆರವೇರಿಸಲಾಯಿತು ಜನರು ಆಗಾಗ್ಗೆ ಹೆಚ್ಚು 2 ಮಕ್ಕಳನ್ನು ರಿಂದ. 

ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ ಅವಳಿ ಮರದ ಒಂದು ವಿಶೇಷ, ಆದೇಶಿತ ವಿಧ ಎಂದು ನಮಗೆ ಬೇಗನೆ ಮೌಲ್ಯಗಳನ್ನು ನೋಡಲು ಅನುಮತಿಸುತ್ತದೆ. ನೀವು ಗಮನಿಸಬಹುದು ಒಂದು ಮರದ ಕೆಳಗೆ ಮೂಲ ಪ್ರತಿ ನೋಡ್ ಮತ್ತೊಂದು ವೃಕ್ಷದ ಮೂಲ, ಒಂದು 'ಸಬ್ಟ್ರೀಯ.' ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಇಲ್ಲಿ, ಮರದ ಬೇರು, 6 ಮತ್ತು ತನ್ನ ಮಗುವಿಗೆ, 2, ಒಂದು ಸಬ್ಟ್ರೀಯ ಮೂಲ ಬೇರಾಗಿದೆ. 

ಒಂದು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ ಒಂದು ನೋಡ್ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳನ್ನು ಬಲ ಸಬ್ಟ್ರೀಯ ಇಲ್ಲಿದೆ ನೋಡ್ ಮೌಲ್ಯದ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಇಲ್ಲಿ: 6. ಅಲ್ಲದೆ, ಒಂದು ನೋಡ್ ನ ಎಡ ಸಬ್ಟ್ರೀಯ ಮೌಲ್ಯಗಳನ್ನು ನೋಡ್ನ ಮೌಲ್ಯವನ್ನು ಕಡಿಮೆ. ನಾವು ನಕಲಿ ಮೌಲ್ಯಗಳನ್ನು ನಿರ್ವಹಿಸಲು ಬಯಸಿದಲ್ಲಿ, ನಾವು, ಸಡಿಲವಾದ ಅಸಮಾನತೆ ಎರಡೂ ಆ ಬದಲಾಯಿಸಬಹುದು ಒಂದೇ ಮೌಲ್ಯಗಳನ್ನು ಎಡ ಅಥವಾ ಬಲಭಾಗದಲ್ಲಿ ಎರಡೂ ನಡೆಯುತ್ತದೆ ಅಂದರೆ, ಎಲ್ಲಿಯವರೆಗೆ ನಾವು ಉದ್ದಕ್ಕೂ ಇದು ಸುಮಾರು ಇವೆ ಎಂದು. ಈ ಮರದ ಒಂದು ಬೈನರಿ ಸರ್ಚ್ ಮರವಾಗಿದೆ ಈ ನಿಯಮಗಳನ್ನು ಅನುಸರಿಸುತ್ತದೆ ಕಾರಣ. 

ಈ ನಾವು ಸಿ ಸ್ಟ್ರಕ್ಟ್ಸ್ಳ ಎಲ್ಲಾ ನೋಡ್ಗಳು ತಿರುಗಿ ಅದನ್ನು ನೋಡಲು ಹೇಗೆ ಆಗಿದೆ. ಗಮನಿಸಿ ಒಂದು ಮಗು ಕಾಣೆಯಾಗಿದೆ ವೇಳೆ, ಪಾಯಿಂಟರ್ ಶೂನ್ಯ ಆಗಿದೆ. ಹೇಗೆ ನಾವು 7 ವೃಕ್ಷದಲ್ಲಿ ವೇಳೆ ಪರೀಕ್ಷಿಸಿ ಇಲ್ಲ? ನಾವು ಮೂಲ ಆರಂಭವಾಗುವುದು. ಇದು ಮರದ ರ ವೇಳೆ ಏಳು 6 ಹೆಚ್ಚಾಗಿದೆ, ಆದ್ದರಿಂದ, ಇದು ಬಲ ಇರಬೇಕು. ನಂತರ, ಅದು 8 ಕಡಿಮೆ, ಆದ್ದರಿಂದ ಬಿಟ್ಟು ಮಾಡಬೇಕು. ಇಲ್ಲಿ, ನಾವು 7 ಕಂಡುಕೊಂಡಿವೆ. ಈಗ, ನಾವು 5 ಪರಿಶೀಲಿಸಿ ನೋಡುತ್ತಾರೆ. ಐದು 6 ಕಡಿಮೆ, ಆದ್ದರಿಂದ ಎಡ ಇರಬೇಕು. ಐದು, 2 ಹೆಚ್ಚಾಗಿದೆ ಆದ್ದರಿಂದ, ಸರಿಯಾದ ಇರಬೇಕು ಮತ್ತು ಇದು 4 ಹೆಚ್ಚು, ಆದ್ದರಿಂದ ಬಲ ಮತ್ತೆ ಬೇಕು. ಆದಾಗ್ಯೂ, ಯಾವುದೇ ಮಗು ಇಲ್ಲಿ ಇಲ್ಲ. ಪಾಯಿಂಟರ್ ಶೂನ್ಯ ಆಗಿದೆ. ಈ 5 ನಮ್ಮ ವೃಕ್ಷದಲ್ಲಿ ಅಲ್ಲ ಎಂದರ್ಥ. 

ನಾವು ಕೆಳಗಿನ ಕೋಡ್ ಅವಳಿ ಮರದ ಹುಡುಕಬಹುದು: ಪ್ರತಿ ನೋಡ್ ನಲ್ಲಿ, ನಾವು ಕಂಡು ನೀವು ಪರೀಕ್ಷಿಸಿ ನಾವು ಹುಡುಕುತ್ತಿರುವ ಮೌಲ್ಯ. ನಾವು ದೊರೆಯದಿದ್ದಲ್ಲಿ ಅದು ಎಂಬುದನ್ನು ನಾವು ನಿರ್ಧರಿಸಲು ಎಡ ಅಥವಾ ಬಲ ಮತ್ತು ಆ ಸಬ್ಟ್ರೀಯ ಪರಿಶೀಲಿಸಿ. ಈ ಕುಣಿಕೆ ಮರದ ಕೆಳಗೆ ಮುಂದುವರಿಯುತ್ತದೆ ಎಡ ಅಥವಾ ಬಲ ಎರಡೂ ಯಾವುದೇ ಮಗು ನೋಡ್ ಇಲ್ಲ ರವರೆಗೆ. 

5 ವೃಕ್ಷದಲ್ಲಿ ಎಂದು ನೆನಪಿಡಿ. ಹೇಗೆ ನಾವು ಸೇರಿಸಲು ಇಲ್ಲ? ಪ್ರಕ್ರಿಯೆ ಹುಡುಕಲು ಹೋಲುತ್ತದೆ. ನಾವು, 6 ರಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಮರವನ್ನು ತಿರುಗಿ 2 ಎಡಕ್ಕೆ, 4 ಹಕ್ಕು ಮತ್ತು ಬಲ ಮತ್ತೆ, ಆದರೆ 4 ಈ ಭಾಗದಲ್ಲಿ ಯಾವುದೇ ಮಗು ಹೊಂದಿದೆ. ಈ, 5 ಹೊಸ ಸ್ಥಾನ ಕಾಣಿಸುತ್ತದೆ ಮತ್ತು ಇದು ಯಾವುದೇ ಮಕ್ಕಳ ಆರಂಭವಾಗುತ್ತವೆ. 

ಎಷ್ಟು ವೇಗವಾಗಿ ಒಂದು ಬೈನರಿ ಸರ್ಚ್ ಮರದ ಮೇಲೆ ಕಾರ್ಯಗಳು ನಡೆಯುತ್ತವೆ? Bigohnotation ಒಂದು ಮೇಲಿನ ನಿರ್ಬಂಧಿತ ಒದಗಿಸಲು ಯತ್ನಿಸುತ್ತದೆ ಎಂಬುದನ್ನು ನೆನಪಿನಲ್ಲಿಡಿ. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ನಮ್ಮ ಮರ ಕೇವಲ ಒಂದು ಲಿಂಕ್ ಪಟ್ಟಿ ಮಾಡಬಹುದು ಆ ಅಳವಡಿಕೆ, ಅಳಿಸಿದ, ಮತ್ತು ಹುಡುಕಾಟ ಅರ್ಥ ಮರದ ನೋಡ್ ಸಂಖ್ಯೆಗೆ ಪ್ರಮಾಣಾನುಗುಣವಾಗಿದೆ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಈ ಒ (n ಆಗಿದೆ). 

ಉದಾಹರಣೆಗೆ, ಈ ಕೆಳಗಿನ ಒಂದು ಮಾನ್ಯ ಬೈನರಿ ಸರ್ಚ್ ಮರವಾಗಿದೆ. ಆದರೆ, ನಾವು 9 ಹುಡುಕಲು ಪ್ರಯತ್ನಿಸಿದರೆ, ನಾವು ಪ್ರತಿ ನೋಡ್ ಹಾದುಹೋಗಬೇಕಾದರೆ ಹೊಂದಿರುತ್ತವೆ. ಇದು ಒಂದು ಲಿಂಕ್ ಪಟ್ಟಿ ಗಿಂತ ಉತ್ತಮ. ಆದ್ದರಿಂದ ನಾವು ಪ್ರತಿಯೊಂದು ನೋಡ್ ಬಯಸುತ್ತೇನೆ ನಮ್ಮ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ 2 ಮಕ್ಕಳನ್ನು. ಈ ರೀತಿಯಲ್ಲಿ, ಅಳವಡಿಕೆ, ತೆಗೆದುಹಾಕುವುದು ಮತ್ತು ಹುಡುಕಾಟ , ಕೆಟ್ಟ, ಒ (ಲಾಗ್ N) ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಮೊದಲು ಮರ, ಹೆಚ್ಚು ಸಮತೋಲಿತ ಆಗಿರಬಹುದು ಈ ರೀತಿಯ. ಈಗ ಯಾವುದೇ ಮೌಲ್ಯವನ್ನು ಹುಡುಕುತ್ತಿರುವಾಗ 3 ಹಂತಗಳನ್ನು, ಹೆಚ್ಚೆಂದರೆ, ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಈ ಮರ, ಸಮತೋಲನ ಹೊಂದಿದೆ ಎಂದು ಅರ್ಥ ಕನಿಷ್ಠ ಆಳ ಹೊಂದಿದೆ ನೋಡ್ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹೋಲಿಸಿದರೆ. 

ಒಂದು ಸಮತೋಲಿತ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ ಒಂದು ಮೌಲ್ಯವನ್ನು ಇವರಿಗಾಗಿ ನೋಡುತ್ತಿರುವುದು ಸಾರ್ಟೆಡ್ ರಚನೆಯ ಮೇಲೆ ಬೈನರಿ ಸರ್ಚ್ ಹೋಲುತ್ತದೆ. ವಾಸ್ತವವಾಗಿ, ನಾವು ಐಟಂಗಳನ್ನು ಸೇರಿಸಲು ಅಥವಾ ಅಳಿಸಲು ಮಾಡಬೇಕಿಲ್ಲ ವೇಳೆ, ಅವರು ಒಂದೇ ರೀತಿಯಲ್ಲಿ ವರ್ತಿಸುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಒಂದು ಮರದ ರಚನೆ ಉತ್ತಮ ನಿರ್ವಹಣೆ ಅಳವಡಿಕೆಗಳು ಮತ್ತು ಅಳಿಸುವಿಕೆಗಳು ಫಾರ್ 

ನನ್ನ ಹೆಸರು Bannus ವ್ಯಾನ್ ಡೆರ್ Kloot ಹೊಂದಿದೆ. ಈ CS50 ಹೊಂದಿದೆ.