ಅರೇಗಳೊಂದಿಗೆ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ನಿರ್ಮಾಣ
ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಗಳು (BST ಗಳು) ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಮೂಲಭೂತ ಡೇಟಾ ರಚನೆಯಾಗಿದ್ದು, ಸಮರ್ಥ ಹುಡುಕಾಟ, ಅಳವಡಿಕೆ ಮತ್ತು ಅಂಶಗಳ ಅಳಿಸುವಿಕೆಯನ್ನು ಸಕ್ರಿಯಗೊಳಿಸುತ್ತದೆ. ಒಂದು ಶ್ರೇಣಿಯಿಂದ BST ಅನ್ನು ನಿರ್ಮಿಸುವಾಗ, BST ಗುಣಲಕ್ಷಣಗಳನ್ನು ನಿರ್ವಹಿಸಲು ಶ್ರೇಣಿಯನ್ನು ಹೇಗೆ ವಿಭಜಿಸುವುದು ಎಂಬುದನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು ಕೀಲಿಯಾಗಿದೆ. ಆಯ್ದ ಮೂಲ ಮೌಲ್ಯದ ಆಧಾರದ ಮೇಲೆ ಸರಣಿಯನ್ನು ಎಡ ಮತ್ತು ಬಲ ಸಬ್ಅರೇಗಳಾಗಿ ಪುನರಾವರ್ತಿತವಾಗಿ ವಿಭಜಿಸುವುದನ್ನು ಇದು ಒಳಗೊಂಡಿರುತ್ತದೆ.
ಈ ಲೇಖನದಲ್ಲಿ, ನಾವು ಜಾವಾಸ್ಕ್ರಿಪ್ಟ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಒಂದು ಶ್ರೇಣಿಯಿಂದ BST ಅನ್ನು ನಿರ್ಮಿಸುವ ಪ್ರಕ್ರಿಯೆಯ ಮೂಲಕ ನಡೆಯುತ್ತೇವೆ. ವ್ಯೂಹದಿಂದ ಮೂಲವನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು, ಅಂಶಗಳನ್ನು ಎಡ ಮತ್ತು ಬಲ ಉಪವೃಕ್ಷಗಳಾಗಿ ವಿಭಜಿಸುವುದು ಮತ್ತು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಮರದಲ್ಲಿ ಸೂಕ್ತವಾಗಿ ಜೋಡಿಸುವವರೆಗೆ ಪ್ರತಿ ಉಪಟ್ರೀಗೆ ಪುನರಾವರ್ತಿತವಾಗಿ ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸುವುದು ಉದ್ದೇಶವಾಗಿದೆ.
ಅಲ್ಗಾರಿದಮ್ಗೆ ವಿಭಜನೆಯನ್ನು ಎಚ್ಚರಿಕೆಯಿಂದ ನಿರ್ವಹಿಸುವ ಅಗತ್ಯವಿರುತ್ತದೆ, ವಿಶೇಷವಾಗಿ ಕೇವಲ ಎರಡು ಅಂಶಗಳು ಉಳಿದಿರುವಾಗ, ಕಡಿಮೆ ಮೌಲ್ಯವು ಎಡಕ್ಕೆ ಮತ್ತು ಹೆಚ್ಚಿನ ಮೌಲ್ಯವು ಬಲಕ್ಕೆ ಹೋಗಬೇಕು. ಹೆಚ್ಚುವರಿಯಾಗಿ, ಪುನರಾವರ್ತಿತ ತರ್ಕವು ರಚನೆಯನ್ನು ಸಣ್ಣ ಭಾಗಗಳಾಗಿ ವಿಭಜಿಸಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ, ಮರವನ್ನು ಸರಿಯಾಗಿ ನಿರ್ಮಿಸಲಾಗಿದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ.
ಈ ವಿಧಾನವು ಸಮತೋಲಿತ BST ಅನ್ನು ಸಮರ್ಥವಾಗಿ ನಿರ್ಮಿಸಲು ನಮಗೆ ಅವಕಾಶ ನೀಡುತ್ತದೆ, ಅರೇ ಅನ್ನು ವಿಂಗಡಿಸಲಾಗಿದೆ. ವಿವರಿಸಿದ ಹಂತಗಳನ್ನು ಅನುಸರಿಸುವ ಮೂಲಕ, ನೀವು ಜಾವಾಸ್ಕ್ರಿಪ್ಟ್ನಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವ BST ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಸಾಧ್ಯವಾಗುತ್ತದೆ, ಡೇಟಾದ ಮೂಲಕ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಹುಡುಕುವುದು ಅಥವಾ ಕ್ರಿಯಾತ್ಮಕವಾಗಿ ವಿಂಗಡಿಸಲಾದ ಡೇಟಾವನ್ನು ನಿರ್ವಹಿಸುವಂತಹ ಸಾಮಾನ್ಯ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವುದು.
ಆಜ್ಞೆ | ಬಳಕೆಯ ಉದಾಹರಣೆ |
---|---|
Math.floor() | ಈ ಆಜ್ಞೆಯನ್ನು ರೌಂಡ್ ಡೌನ್ ಮಾಡುವ ಮೂಲಕ ರಚನೆಯ ಮಧ್ಯಬಿಂದುವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಬಳಸಲಾಗುತ್ತದೆ. ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ನಿರ್ಮಾಣದಲ್ಲಿ ಸಬ್ಟ್ರೀಯ ಮೂಲವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಇದು ನಿರ್ಣಾಯಕವಾಗಿದೆ. ಉದಾಹರಣೆ: ಮಧ್ಯ = Math.floor(nums.length / 2); |
Array.prototype.slice() | ಮಧ್ಯಬಿಂದುವಿನ ಆಧಾರದ ಮೇಲೆ ಅರೇಯನ್ನು ಎಡ ಮತ್ತು ಬಲ ಸಬ್ಅರೇಗಳಾಗಿ ವಿಭಜಿಸಲು ಈ ವಿಧಾನವನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಪುನರಾವರ್ತಿತ BST ರಚನೆಗಾಗಿ ರಚನೆಯನ್ನು ಸಣ್ಣ ಭಾಗಗಳಾಗಿ ವಿಭಜಿಸಲು ಇದು ಸಹಾಯ ಮಾಡುತ್ತದೆ. ಉದಾಹರಣೆ: lSide = nums.ಸ್ಲೈಸ್ (0, ಮಧ್ಯ) ಬಿಡಿ; |
Array.prototype.push() | ಹೊಸ ನೋಡ್ಗಳನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಲು ಸೇರಿಸುವಾಗ ಪುನರಾವರ್ತಿತ ವಿಧಾನಕ್ಕೆ ಅತ್ಯಗತ್ಯವಾಗಿರುವ ಒಂದು ಶ್ರೇಣಿ ಅಥವಾ ಸರತಿಗೆ ಅಂಶಗಳನ್ನು ತಳ್ಳುತ್ತದೆ. ಉದಾಹರಣೆ: queue.push({ನೋಡ್: node.left, range: leftSide }); |
throw new Error() | ದೋಷ ನಿರ್ವಹಣೆಗಾಗಿ ಈ ಆಜ್ಞೆಯನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಅಮಾನ್ಯ ಇನ್ಪುಟ್ಗಳೊಂದಿಗೆ ಪ್ರೋಗ್ರಾಂ ಮುಂದುವರಿಯುವುದಿಲ್ಲ ಎಂದು ಇದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಉದಾಹರಣೆ: ಹೊಸ ದೋಷವನ್ನು ಎಸೆಯಿರಿ("ಅಮಾನ್ಯವಾದ ಇನ್ಪುಟ್: ಸಂಖ್ಯೆಗಳು ಖಾಲಿ ಅಲ್ಲದ ರಚನೆಯಾಗಿರಬೇಕು."); |
Array.isArray() | ಇನ್ಪುಟ್ ಮಾನ್ಯವಾದ ಶ್ರೇಣಿಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತದೆ. ಮರದ ನಿರ್ಮಾಣದ ಸಮಯದಲ್ಲಿ ಸಂಭವನೀಯ ದೋಷಗಳನ್ನು ತಪ್ಪಿಸಲು ಈ ಆಜ್ಞೆಯು ಇನ್ಪುಟ್ ಮೌಲ್ಯೀಕರಣಕ್ಕೆ ಉಪಯುಕ್ತವಾಗಿದೆ. ಉದಾಹರಣೆ: ವೇಳೆ (!Array.isArray(nums)) |
console.error() | ಡೀಬಗ್ ಮಾಡುವ ಉದ್ದೇಶಗಳಿಗಾಗಿ ಕನ್ಸೋಲ್ಗೆ ದೋಷ ಸಂದೇಶಗಳನ್ನು ಲಾಗ್ ಮಾಡುತ್ತದೆ. ಕಾರ್ಯಕ್ರಮದ ಅನುಷ್ಠಾನದ ಸಮಯದಲ್ಲಿ ಸಮಸ್ಯೆಗಳನ್ನು ಪತ್ತೆಹಚ್ಚಲು ಇದು ಸಹಾಯ ಮಾಡುತ್ತದೆ. ಉದಾಹರಣೆ: console.error(error.message); |
Node() | ಈ ಕನ್ಸ್ಟ್ರಕ್ಟರ್ ಕಾರ್ಯವು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯಲ್ಲಿ ಕೊಟ್ಟಿರುವ ಮೌಲ್ಯದೊಂದಿಗೆ ಹೊಸ ನೋಡ್ ಅನ್ನು ರಚಿಸುತ್ತದೆ. ಮರದ ರಚನೆಯನ್ನು ನಿರ್ಮಿಸಲು ಇದು ಅಡಿಪಾಯವಾಗಿದೆ. ಉದಾಹರಣೆ: ನೋಡ್ = ಹೊಸ ನೋಡ್ (ಸಂಖ್ಯೆಗಳು[ಮಧ್ಯ]); |
while() | ಷರತ್ತುಗಳನ್ನು ಪೂರೈಸುವವರೆಗೆ ಅಂಶಗಳ ಮೇಲೆ ಲೂಪ್ ಮಾಡಲು ಬಳಸಲಾಗುತ್ತದೆ. ಪುನರಾವರ್ತನೆಯ ವಿಧಾನದಲ್ಲಿ, ಈ ಲೂಪ್ ಎಲ್ಲಾ ನೋಡ್ಗಳನ್ನು ಸರದಿಯಲ್ಲಿ ಸಂಸ್ಕರಿಸಲಾಗುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಉದಾಹರಣೆ: ಹಾಗೆಯೇ (queue.length) { ...} |
try { ... } catch { ... } | ಈ ರಚನೆಯನ್ನು ವಿನಾಯಿತಿಗಳನ್ನು ನಿರ್ವಹಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ, ದೋಷ ಸಂಭವಿಸಿದಲ್ಲಿ, ಪ್ರೋಗ್ರಾಂ ಅದನ್ನು ಕ್ರ್ಯಾಶ್ ಮಾಡದೆಯೇ ನಿರ್ವಹಿಸಬಹುದು ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಉದಾಹರಣೆ: {...} ಹಿಡಿಯಲು ಪ್ರಯತ್ನಿಸಿ (ದೋಷ) { ...} |
ಜಾವಾಸ್ಕ್ರಿಪ್ಟ್ನಲ್ಲಿ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ನಿರ್ಮಾಣವನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು
ನಾವು ಅನ್ವೇಷಿಸಿದ ಮೊದಲ ಸ್ಕ್ರಿಪ್ಟ್ ನಿರ್ಮಿಸುತ್ತದೆ a ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (BST) ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಬಳಸುವುದು. ಡೇಟಾವನ್ನು ಸಣ್ಣ ಉಪಸಮಸ್ಯೆಗಳಾಗಿ ವಿಭಜಿಸಬೇಕಾದ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಈ ವಿಧಾನವು ಉಪಯುಕ್ತವಾಗಿದೆ. ರಚನೆಯ ಮಧ್ಯದ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮೂಲಕ, ನಾವು ಅದನ್ನು ಮರದ ಮೂಲ ನೋಡ್ ಆಗಿ ಆಯ್ಕೆ ಮಾಡಬಹುದು. ಮೂಲಕ್ಕಿಂತ ಚಿಕ್ಕದಾದ ಅಂಶಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ರಚನೆಯ ಎಡಭಾಗವು ಎಡ ಉಪಟ್ರೀ ಆಗುತ್ತದೆ, ಆದರೆ ಬಲಭಾಗವು ದೊಡ್ಡ ಅಂಶಗಳೊಂದಿಗೆ ಬಲ ಉಪಟ್ರೀ ಆಗುತ್ತದೆ. ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಮರದೊಳಗೆ ಸೇರಿಸುವವರೆಗೆ ಈ ಪ್ರಕ್ರಿಯೆಯು ಪುನರಾವರ್ತಿತವಾಗಿ ಪುನರಾವರ್ತನೆಯಾಗುತ್ತದೆ.
ಪುನರಾವರ್ತನೆಯು ಅಲ್ಗಾರಿದಮ್ನ ಶುದ್ಧ ಮತ್ತು ತಾರ್ಕಿಕ ಹರಿವನ್ನು ಅನುಮತಿಸುತ್ತದೆ. ಈ ಸ್ಕ್ರಿಪ್ಟ್ನಲ್ಲಿ ಪ್ರಮುಖ ಆಜ್ಞೆಯಾಗಿದೆ Math.floor(), ಇದು ರಚನೆಯ ಮಧ್ಯಬಿಂದುವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಬಳಸಲಾಗುತ್ತದೆ ಮತ್ತು ಮುಂದಿನ ಪ್ರಕ್ರಿಯೆಗಾಗಿ ಅದನ್ನು ವಿಭಜಿಸಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ. ಮತ್ತೊಂದು ಪ್ರಮುಖ ಆಜ್ಞೆಯಾಗಿದೆ ಸ್ಲೈಸ್ (), ಇದು ರಚನೆಯನ್ನು ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ, ಇದು ಎಡ ಮತ್ತು ಬಲ ಉಪಟ್ರೀಗಳನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ರಚಿಸಲು ಅನುಮತಿಸುತ್ತದೆ. ಈ ಮಾಡ್ಯುಲರ್ ವಿಧಾನವು ಅದರ ವಿಂಗಡಿಸಲಾದ ರಚನೆಯನ್ನು ನಿರ್ವಹಿಸುವಾಗ BST ಸರಿಯಾಗಿ ರೂಪುಗೊಂಡಿದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಈ ಪುನರಾವರ್ತಿತ ತಂತ್ರವು ರಚನೆಯನ್ನು ವಿಂಗಡಿಸಿದರೆ, ಮರವು ಸಮತೋಲಿತವಾಗಿದೆ ಎಂದು ಖಾತರಿಪಡಿಸುತ್ತದೆ.
ಎರಡನೇ ಸ್ಕ್ರಿಪ್ಟ್ನಲ್ಲಿ, ನಾವು ಸರದಿಯನ್ನು ಬಳಸಿಕೊಂಡು ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಅಳವಡಿಸಿದ್ದೇವೆ. ಪುನರಾವರ್ತನೆಯು ತುಂಬಾ ಸಂಕೀರ್ಣವಾದಾಗ ಅಥವಾ ಮೆಮೊರಿ ನಿರ್ಬಂಧಗಳ ಕಾರಣದಿಂದಾಗಿ ಆದ್ಯತೆ ನೀಡದಿದ್ದಾಗ ಈ ವಿಧಾನವು ಪ್ರಯೋಜನಕಾರಿಯಾಗಿದೆ. ಮುಖ್ಯ ಕಲ್ಪನೆಯು ಒಂದೇ ಆಗಿರುತ್ತದೆ: ಮಧ್ಯಬಿಂದುವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ನೋಡ್ ಅನ್ನು ಸೇರಿಸುವುದು ಮತ್ತು ರಚನೆಯನ್ನು ಸಣ್ಣ ಭಾಗಗಳಾಗಿ ವಿಭಜಿಸುವುದು. ಆದಾಗ್ಯೂ, ಪುನರಾವರ್ತನೆಯ ಬದಲಿಗೆ, ನಾವು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಬೇಕಾದ ನೋಡ್ಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಕ್ಯೂ ಅನ್ನು ಬಳಸುತ್ತೇವೆ. ಈ ಪುನರಾವರ್ತಿತ ಪರಿಹಾರವು ಆಜ್ಞೆಗಳನ್ನು ಬಳಸುತ್ತದೆ ತಳ್ಳು(), ಇದು ಭವಿಷ್ಯದ ಪ್ರಕ್ರಿಯೆಗಾಗಿ ಕ್ಯೂಗೆ ನೋಡ್ಗಳನ್ನು ಸೇರಿಸುತ್ತದೆ. ಎಲ್ಲಾ ನೋಡ್ಗಳನ್ನು ಸಂಸ್ಕರಿಸುವವರೆಗೆ ಲೂಪ್ ಮುಂದುವರಿಯುತ್ತದೆ, ಸಂಪೂರ್ಣ ಮರವನ್ನು ನಿರ್ಮಿಸಲಾಗಿದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ.
ಅಂತಿಮವಾಗಿ, ಮೂರನೇ ಸ್ಕ್ರಿಪ್ಟ್ ದೋಷ ನಿರ್ವಹಣೆ ಮತ್ತು ಇನ್ಪುಟ್ ಮೌಲ್ಯೀಕರಣವನ್ನು ಪರಿಚಯಿಸುತ್ತದೆ. ಮುಂತಾದ ಆಜ್ಞೆಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ ಹೊಸ ದೋಷವನ್ನು ಎಸೆಯಿರಿ() ಮತ್ತು Array.isArray(), ಮರದ ನಿರ್ಮಾಣದೊಂದಿಗೆ ಮುಂದುವರಿಯುವ ಮೊದಲು ಅಮಾನ್ಯ ಇನ್ಪುಟ್ಗಳನ್ನು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ನಾವು ಕೋಡ್ ಅನ್ನು ಹೆಚ್ಚು ದೃಢಗೊಳಿಸುತ್ತೇವೆ. ಈ ಪರಿಶೀಲನೆಗಳು ನಮ್ಮ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಅನ್ನು ಇನ್ಪುಟ್ ಮಾನ್ಯವಾಗಿದ್ದರೆ ಮಾತ್ರ ನಿರ್ಮಿಸಲಾಗಿದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ, ರನ್ಟೈಮ್ ದೋಷಗಳನ್ನು ತಡೆಯುತ್ತದೆ. ಈ ಆವೃತ್ತಿಯು ವಿನಾಯಿತಿಗಳನ್ನು ಆಕರ್ಷಕವಾಗಿ ನಿರ್ವಹಿಸಲು ಪ್ರಯತ್ನಿಸಿ-ಕ್ಯಾಚ್ ಬ್ಲಾಕ್ ಅನ್ನು ಸಹ ಕಾರ್ಯಗತಗೊಳಿಸುತ್ತದೆ, ಪ್ರೋಗ್ರಾಂ ದೋಷಗಳನ್ನು ನಿರ್ವಹಿಸಲು ಮತ್ತು ಅವುಗಳನ್ನು ಸರಿಯಾಗಿ ಲಾಗ್ ಮಾಡಲು ಅನುಮತಿಸುತ್ತದೆ. ಇದು ಪರಿಹಾರದ ವಿಶ್ವಾಸಾರ್ಹತೆಯನ್ನು ಸುಧಾರಿಸುವುದಲ್ಲದೆ ಅದರ ಸುರಕ್ಷತೆ ಮತ್ತು ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ, ಇದು ವಿವಿಧ ಪರಿಸರದಲ್ಲಿ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ.
ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಬೈನರಿ ಹುಡುಕಾಟ ಮರದ ನಿರ್ಮಾಣ
ಈ ಪರಿಹಾರವು ಜಾವಾಸ್ಕ್ರಿಪ್ಟ್ನಲ್ಲಿ ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಸರಣಿಯಿಂದ ಬೈನರಿ ಹುಡುಕಾಟ ಮರವನ್ನು ನಿರ್ಮಿಸುತ್ತದೆ.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
buildTree(nums) {
if (nums.length === 0) return null;
let mid = Math.floor(nums.length / 2);
let node = new Node(nums[mid]);
node.left = this.buildTree(nums.slice(0, mid));
node.right = this.buildTree(nums.slice(mid + 1));
return node;
}
}
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree();
bst.root = bst.buildTree(nums);
console.log(bst.root);
ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಬಳಸಿ ಪುನರಾವರ್ತನೆ ಮತ್ತು ಸರತಿ
ಈ ಪರಿಹಾರವು ಕ್ಯೂನೊಂದಿಗೆ ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಬೈನರಿ ಹುಡುಕಾಟ ಮರವನ್ನು ನಿರ್ಮಿಸುತ್ತದೆ.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
buildTree(nums) {
if (nums.length === 0) return null;
let mid = Math.floor(nums.length / 2);
this.root = new Node(nums[mid]);
let queue = [{ node: this.root, range: nums }];
while (queue.length) {
let { node, range } = queue.shift();
let midIndex = Math.floor(range.length / 2);
let leftSide = range.slice(0, midIndex);
let rightSide = range.slice(midIndex + 1);
if (leftSide.length) {
node.left = new Node(leftSide[Math.floor(leftSide.length / 2)]);
queue.push({ node: node.left, range: leftSide });
}
if (rightSide.length) {
node.right = new Node(rightSide[Math.floor(rightSide.length / 2)]);
queue.push({ node: node.right, range: rightSide });
}
}
}
}
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree();
bst.buildTree(nums);
console.log(bst.root);
ದೋಷ ನಿರ್ವಹಣೆ ಮತ್ತು ಇನ್ಪುಟ್ ಮೌಲ್ಯೀಕರಣದೊಂದಿಗೆ ಸಮತೋಲಿತ ಬೈನರಿ ಹುಡುಕಾಟ ಮರ
ಈ ಪರಿಹಾರವು ಇನ್ಪುಟ್ ಮೌಲ್ಯೀಕರಣ ಮತ್ತು ಆಪ್ಟಿಮೈಸ್ ಮಾಡಿದ ದೋಷ ನಿರ್ವಹಣೆಯೊಂದಿಗೆ ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಸುಧಾರಿಸುತ್ತದೆ.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
buildTree(nums) {
if (!Array.isArray(nums) || nums.length === 0) {
throw new Error("Invalid input: nums must be a non-empty array.");
}
return this._buildRecursive(nums);
}
_buildRecursive(nums) {
if (nums.length === 0) return null;
let mid = Math.floor(nums.length / 2);
let node = new Node(nums[mid]);
node.left = this._buildRecursive(nums.slice(0, mid));
node.right = this._buildRecursive(nums.slice(mid + 1));
return node;
}
}
try {
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree();
bst.root = bst.buildTree(nums);
console.log(bst.root);
} catch (error) {
console.error(error.message);
}
ಸಮರ್ಥ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಅಲ್ಗಾರಿದಮ್ಗಳು
ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (BST) ಅಲ್ಗಾರಿದಮ್ಗಳ ಒಂದು ಪ್ರಮುಖ ಅಂಶವಾಗಿದೆ ಮರದ ಸಮತೋಲನ. ಮರವು ಅತ್ಯುತ್ತಮ ಹುಡುಕಾಟ ಸಮಯವನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಸಮತೋಲನವು ನಿರ್ಣಾಯಕವಾಗಿದೆ. ಒಂದು BST ಅಸಮತೋಲನಗೊಂಡರೆ, ನೋಡ್ಗಳನ್ನು ಹುಡುಕುವುದು, ಸೇರಿಸುವುದು ಮತ್ತು ಅಳಿಸುವಂತಹ ಕೆಲವು ಕಾರ್ಯಾಚರಣೆಗಳು ರೇಖೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಗೆ (O(n)) ಕುಸಿಯಬಹುದು, ಇದು BST ಅನ್ನು ಬಳಸುವ ಉದ್ದೇಶವನ್ನು ಸೋಲಿಸುತ್ತದೆ. AVL ಮರಗಳು ಮತ್ತು ಕೆಂಪು-ಕಪ್ಪು ಮರಗಳಂತಹ ಅಲ್ಗಾರಿದಮ್ಗಳು ನೋಡ್ಗಳ ಅಳವಡಿಕೆ ಅಥವಾ ಅಳಿಸುವಿಕೆಯ ಮೇಲೆ ಸ್ವಯಂಚಾಲಿತವಾಗಿ ಮರವನ್ನು ಮರುಸಮತೋಲನಗೊಳಿಸುತ್ತದೆ, ಮರದ ಎತ್ತರವು ನೋಡ್ಗಳ ಸಂಖ್ಯೆಗೆ ಯಾವಾಗಲೂ ಲಾಗರಿಥಮಿಕ್ ಆಗಿರುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ.
BST ಅನ್ನು ನಿರ್ಮಿಸುವಾಗ ಮತ್ತೊಂದು ನಿರ್ಣಾಯಕ ಪರಿಗಣನೆಯು ನಕಲಿ ಮೌಲ್ಯಗಳನ್ನು ಹೇಗೆ ನಿರ್ವಹಿಸುವುದು. ಅನೇಕ ಸಂದರ್ಭಗಳಲ್ಲಿ, ನಕಲುಗಳನ್ನು ಎಡ ಅಥವಾ ಬಲ ಸಬ್ಟ್ರೀಯಲ್ಲಿ ಸ್ಥಿರವಾಗಿ ಇರಿಸುವ ಮೂಲಕ ಅನುಮತಿಸಲಾಗುವುದಿಲ್ಲ ಅಥವಾ ನಿರ್ವಹಿಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಬಿಎಸ್ಟಿಯ ಸಮಗ್ರತೆಯನ್ನು ಕಾಪಾಡಿಕೊಳ್ಳಲು ಪೂರ್ವನಿಯೋಜಿತವಾಗಿ ಬಲ ಸಬ್ಟ್ರೀಯಲ್ಲಿ ನಕಲುಗಳನ್ನು ಇರಿಸಬಹುದು. ನಕಲುಗಳನ್ನು ಸೂಕ್ತವಾಗಿ ನಿರ್ವಹಿಸುವುದು ನಿರ್ಮಾಣ ಹಂತ ಮತ್ತು ನಂತರದ ಕಾರ್ಯಾಚರಣೆಗಳೆರಡರಲ್ಲೂ ಮರದ ದಕ್ಷತೆ ಮತ್ತು ಕಾರ್ಯಕ್ಷಮತೆಯ ಮೇಲೆ ಪರಿಣಾಮ ಬೀರಬಹುದು.
ಇದಲ್ಲದೆ, ನಿಮ್ಮ BST ಎಲ್ಲಾ ಸಂದರ್ಭಗಳಲ್ಲಿ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ದೋಷ ನಿರ್ವಹಣೆ ಮತ್ತು ಇನ್ಪುಟ್ ಮೌಲ್ಯೀಕರಣವು ಅತ್ಯಗತ್ಯವಾಗಿರುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಇನ್ಪುಟ್ ಅರೇ ಅನ್ನು ವಿಂಗಡಿಸಲಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವುದರಿಂದ ಸಮಯವನ್ನು ಉಳಿಸಬಹುದು ಮತ್ತು ತಪ್ಪಾದ ಮರದ ರಚನೆಗಳನ್ನು ತಡೆಯಬಹುದು. ಅರ್ಥಪೂರ್ಣ ದೋಷ ಸಂದೇಶಗಳನ್ನು ಎಸೆಯುವಂತಹ ದೃಢವಾದ ದೋಷ ನಿರ್ವಹಣೆಯು ರನ್ಟೈಮ್ ಸಮಸ್ಯೆಗಳನ್ನು ತಪ್ಪಿಸಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ ಮತ್ತು ಡೆವಲಪರ್ ಅನ್ನು ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಡೀಬಗ್ ಮಾಡಲು ಅನುಮತಿಸುತ್ತದೆ. ಹೆಚ್ಚುವರಿಯಾಗಿ, ರಕ್ಷಣಾತ್ಮಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅಭ್ಯಾಸಗಳನ್ನು ಸಂಯೋಜಿಸುವುದು ಅಮಾನ್ಯ ಅಥವಾ ಅನಿರೀಕ್ಷಿತ ಇನ್ಪುಟ್ ಮರ-ನಿರ್ಮಾಣ ಪ್ರಕ್ರಿಯೆಯು ವಿಫಲಗೊಳ್ಳಲು ಕಾರಣವಾಗುವುದಿಲ್ಲ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ.
ಜಾವಾಸ್ಕ್ರಿಪ್ಟ್ನಲ್ಲಿ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಗಳನ್ನು ನಿರ್ಮಿಸುವ ಕುರಿತು ಸಾಮಾನ್ಯ ಪ್ರಶ್ನೆಗಳು
- BST ಅನ್ನು ನಿರ್ಮಿಸಲು ಪುನರಾವರ್ತನೆಯು ಹೇಗೆ ಸಹಾಯ ಮಾಡುತ್ತದೆ?
- ಪುನರಾವರ್ತನೆಯು ವ್ಯೂಹವನ್ನು ಸಣ್ಣ ಉಪವರ್ಗಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ ಮತ್ತು ಮಧ್ಯದ ಅಂಶವನ್ನು ಮೂಲವಾಗಿ ನಿಯೋಜಿಸುತ್ತದೆ, ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಇರಿಸುವವರೆಗೆ ಪ್ರಕ್ರಿಯೆಯು ಪುನರಾವರ್ತನೆಯಾಗುತ್ತದೆ.
- ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯಲ್ಲಿ ನೀವು ನಕಲಿ ಮೌಲ್ಯಗಳನ್ನು ಹೇಗೆ ನಿರ್ವಹಿಸುತ್ತೀರಿ?
- ನೀವು ಎಡ ಅಥವಾ ಬಲ ಸಬ್ಟ್ರೀಯಲ್ಲಿ ಸ್ಥಿರವಾಗಿ ನಕಲುಗಳನ್ನು ಇರಿಸಬಹುದು. ಇದು BST ಗುಣಲಕ್ಷಣಗಳನ್ನು ನಿರ್ವಹಿಸುವುದನ್ನು ಖಚಿತಪಡಿಸುತ್ತದೆ.
- ಪ್ರಾಮುಖ್ಯತೆ ಏನು Math.floor() BST ನಿರ್ಮಾಣದಲ್ಲಿ?
- Math.floor() ರಚನೆಯ ಮಧ್ಯದ ಅಂಶವನ್ನು ನಿರ್ಧರಿಸಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ, ಇದು ಉಪಟ್ರೀಯ ಮೂಲವಾಗುತ್ತದೆ.
- BST ಯಲ್ಲಿ ಮರದ ಸಮತೋಲನವು ಏಕೆ ಮುಖ್ಯವಾಗಿದೆ?
- ಸಮತೋಲನವು ಮರವನ್ನು ಓರೆಯಾಗದಂತೆ ತಡೆಯುತ್ತದೆ, ಹುಡುಕಾಟ, ಸೇರಿಸುವಿಕೆ ಮತ್ತು ಅಳಿಸುವಿಕೆಯಂತಹ ಕಾರ್ಯಾಚರಣೆಗಳು O(log n) ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ.
- ಹೇಗೆ ಸಾಧ್ಯ slice() ಮರದ ನಿರ್ಮಾಣವನ್ನು ಸುಧಾರಿಸುವುದೇ?
- slice() ವ್ಯೂಹವನ್ನು ಎಡ ಮತ್ತು ಬಲ ಸಬರೇಗಳಾಗಿ ವಿಭಜಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ, ಇದು ಮರದ ಉಪವೃಕ್ಷಗಳ ಪುನರಾವರ್ತಿತ ನಿರ್ಮಾಣವನ್ನು ಅನುಮತಿಸುತ್ತದೆ.
- ಇನ್ಪುಟ್ ಮೌಲ್ಯೀಕರಣದಲ್ಲಿ ಏನು ಪರಿಶೀಲಿಸಬೇಕು?
- ಇನ್ಪುಟ್ ಮಾನ್ಯ, ವಿಂಗಡಿಸಲಾದ ಶ್ರೇಣಿಯೇ ಎಂಬುದನ್ನು ಪರಿಶೀಲಿಸಿ. ದೋಷಗಳಿಲ್ಲದೆ ಮರವನ್ನು ಸರಿಯಾಗಿ ನಿರ್ಮಿಸಬಹುದು ಎಂದು ಇದು ಖಚಿತಪಡಿಸುತ್ತದೆ.
- BST ನಿರ್ಮಾಣದಲ್ಲಿ ದೋಷ ನಿರ್ವಹಣೆ ಯಾವ ಪಾತ್ರವನ್ನು ವಹಿಸುತ್ತದೆ?
- ಬಳಕೆಯಂತಹ ದೋಷ ನಿರ್ವಹಣೆ throw new Error(), ಸಮಸ್ಯೆಗಳನ್ನು ಮೊದಲೇ ಗುರುತಿಸಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ ಮತ್ತು ಅಪ್ಲಿಕೇಶನ್ ಕ್ರ್ಯಾಶ್ ಆಗುವುದನ್ನು ತಡೆಯುತ್ತದೆ.
- ಪುನರಾವರ್ತನೆಯ ಮೇಲೆ ನೀವು ಪುನರಾವರ್ತನೆಯ ವಿಧಾನವನ್ನು ಏಕೆ ಆಯ್ಕೆ ಮಾಡಬಹುದು?
- ಪುನರಾವರ್ತನೆ, ಬಳಸಿ a queue, ರಿಕರ್ಶನ್ ಡೆಪ್ತ್ನೊಂದಿಗೆ ಸಂಭಾವ್ಯ ಸಮಸ್ಯೆಗಳನ್ನು ತಪ್ಪಿಸುತ್ತದೆ, ವಿಶೇಷವಾಗಿ ಸ್ಟಾಕ್ ಓವರ್ಫ್ಲೋ ಸಂಭವಿಸಬಹುದಾದ ದೊಡ್ಡ ಡೇಟಾಸೆಟ್ಗಳಲ್ಲಿ.
- AVL ಮತ್ತು ಕೆಂಪು-ಕಪ್ಪು ಮರಗಳು ಸಮತೋಲನವನ್ನು ಹೇಗೆ ಕಾಪಾಡಿಕೊಳ್ಳಬಹುದು?
- ಈ ಕ್ರಮಾವಳಿಗಳು ಲಾಗರಿಥಮಿಕ್ ಹುಡುಕಾಟ ಸಮಯವನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಪ್ರತಿ ಅಳವಡಿಕೆ ಅಥವಾ ಅಳಿಸುವಿಕೆಯ ನಂತರ ಮರವನ್ನು ಸ್ವಯಂಚಾಲಿತವಾಗಿ ಮರುಸಮತೋಲನಗೊಳಿಸುತ್ತವೆ.
- ಮಧ್ಯದ ಅಂಶವನ್ನು ಮೂಲವಾಗಿ ಆಯ್ಕೆಮಾಡುವುದರ ಮಹತ್ವವೇನು?
- ಮಧ್ಯದ ಅಂಶವನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದರಿಂದ ಮರವು ಸಮತೋಲಿತವಾಗಿ ಉಳಿಯುತ್ತದೆ, ಅಸಮರ್ಥ ಹುಡುಕಾಟ ಮಾರ್ಗಗಳನ್ನು ತಡೆಯುತ್ತದೆ.
ಬೈನರಿ ಹುಡುಕಾಟ ಮರಗಳ ಅಂತಿಮ ಆಲೋಚನೆಗಳು
ಅರೇಯಿಂದ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಅನ್ನು ನಿರ್ಮಿಸುವುದು ಅರೇ ಅನ್ನು ಉಪಬರೆಗಳಾಗಿ ವಿಭಜಿಸುವುದು ಮತ್ತು ಮಧ್ಯದ ಅಂಶವನ್ನು ಮೂಲವಾಗಿ ನಿಯೋಜಿಸುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಈ ಪ್ರಕ್ರಿಯೆಯು ಸಮರ್ಥ ಮತ್ತು ಸಮತೋಲಿತ ಮರದ ರಚನೆಯನ್ನು ನಿರ್ವಹಿಸಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ. ಸಮತೋಲಿತ ಮರವು ವೇಗದ ಹುಡುಕಾಟ, ಸೇರಿಸಲು ಮತ್ತು ಅಳಿಸುವ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ನಿರ್ಣಾಯಕವಾಗಿದೆ.
ಪುನರಾವರ್ತಿತ ಮತ್ತು ಪುನರಾವರ್ತಿತ ವಿಧಾನಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ, ನಿಮ್ಮ ಅನುಷ್ಠಾನದಲ್ಲಿ ನಮ್ಯತೆಯನ್ನು ನೀವು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಬಹುದು. ದೋಷ ನಿರ್ವಹಣೆ ಮತ್ತು ಇನ್ಪುಟ್ ಮೌಲ್ಯೀಕರಣವನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುವುದು ರನ್ಟೈಮ್ ದೋಷಗಳನ್ನು ತಡೆಯಲು ಪ್ರಮುಖವಾಗಿದೆ. ಈ ತಂತ್ರಗಳು ಕ್ರಿಯಾತ್ಮಕ ಮತ್ತು ವಿಶ್ವಾಸಾರ್ಹವಾದ ಬೈನರಿ ಹುಡುಕಾಟ ಮರದ ಯಶಸ್ವಿ ಅಭಿವೃದ್ಧಿಗೆ ಕಾರಣವಾಗುತ್ತವೆ.
ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಅಲ್ಗಾರಿದಮ್ಗಾಗಿ ಮೂಲಗಳು ಮತ್ತು ಉಲ್ಲೇಖಗಳು
- ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಗಳ ಸಿದ್ಧಾಂತ ಮತ್ತು ಅರೇಗಳಿಂದ ಅವುಗಳನ್ನು ಹೇಗೆ ನಿರ್ಮಿಸುವುದು ಎಂಬುದರ ಕುರಿತು ವಿವರಿಸುತ್ತದೆ. ಈ ಸಂಪನ್ಮೂಲವು ಸಮರ್ಥವಾದ ಮರಗಳ ರಚನೆಗಾಗಿ ಅರೇಗಳನ್ನು ನಿರ್ವಹಿಸುವ ವಿವರವಾದ ಒಳನೋಟಗಳನ್ನು ಒದಗಿಸುತ್ತದೆ. GeeksforGeeks - ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ
- ಜಾವಾಸ್ಕ್ರಿಪ್ಟ್ ರಚನೆಯ ವಿಧಾನಗಳನ್ನು ಒಳಗೊಂಡಿದೆ ಸ್ಲೈಸ್ () ಮತ್ತು ಟ್ರೀ ಡೇಟಾ ರಚನೆಗಳನ್ನು ನಿರ್ಮಿಸುವಾಗ ಪುನರಾವರ್ತಿತ ತರ್ಕವನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸುವುದು ಹೇಗೆ. MDN ವೆಬ್ ಡಾಕ್ಸ್ - ಅರೇ ಸ್ಲೈಸ್()
- ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಗಳಂತಹ ಡೇಟಾ ರಚನೆಗಳನ್ನು ನಿರ್ಮಿಸುವಲ್ಲಿ ಪುನರಾವರ್ತನೆ ಮತ್ತು ಪುನರಾವರ್ತಿತ ವಿಧಾನಗಳ ಪರಿಕಲ್ಪನೆಗಳನ್ನು ಚರ್ಚಿಸುತ್ತದೆ, ಅಲ್ಗಾರಿದಮ್ ದಕ್ಷತೆಯನ್ನು ಸುಧಾರಿಸುವುದರ ಮೇಲೆ ಕೇಂದ್ರೀಕರಿಸುತ್ತದೆ. JavaScript ಟ್ಯುಟೋರಿಯಲ್ - ಪುನರಾವರ್ತನೆ