ஜாவாஸ்கிரிப்ட் வரிசையிலிருந்து பைனரி தேடல் மரத்தை உருவாக்குதல்

வரிசைகளுடன் பைனரி தேடல் மரம் கட்டுமானம்

பைனரி தேடல் மரங்கள் (BSTs) என்பது கணினி அறிவியலில் ஒரு அடிப்படை தரவு கட்டமைப்பாகும், இது திறமையான தேடுதல், செருகுதல் மற்றும் உறுப்புகளை நீக்குதல் ஆகியவற்றை செயல்படுத்துகிறது. ஒரு அணிவரிசையிலிருந்து BSTயை உருவாக்கும்போது, ​​BST பண்புகளை பராமரிக்க வரிசையை எவ்வாறு பிரிப்பது என்பதைப் புரிந்துகொள்வதில் முக்கியமானது. தேர்ந்தெடுக்கப்பட்ட ரூட் மதிப்பின் அடிப்படையில் வரிசையை இடது மற்றும் வலது துணை அணிகளாகப் பிரிப்பதை இது உள்ளடக்குகிறது.

இந்த கட்டுரையில், ஜாவாஸ்கிரிப்டைப் பயன்படுத்தி ஒரு வரிசையில் இருந்து பிஎஸ்டியை உருவாக்கும் செயல்முறையை நாம் காண்போம். அணிவரிசையிலிருந்து ஒரு வேரைத் தேர்ந்தெடுத்து, உறுப்புகளை இடது மற்றும் வலது துணை மரங்களாகப் பிரித்து, மரத்தில் அனைத்து உறுப்புகளும் சரியான முறையில் அமைக்கப்படும் வரை ஒவ்வொரு துணை மரத்திற்கும் இந்த செயல்முறையை மீண்டும் மீண்டும் செய்வதே இதன் நோக்கம்.

அல்காரிதம் பிரித்தலை கவனமாக கையாள வேண்டும், குறிப்பாக இரண்டு கூறுகள் மட்டுமே எஞ்சியிருக்கும் போது, ​​குறைந்த மதிப்பு இடதுபுறமாகவும், அதிக மதிப்பு வலதுபுறமாகவும் செல்ல வேண்டும். கூடுதலாக, சுழல்நிலை தர்க்கம் வரிசையை சிறிய பகுதிகளாக உடைக்க உதவுகிறது, மரம் சரியாக கட்டமைக்கப்படுவதை உறுதி செய்கிறது.

இந்த அணுகுமுறையானது, வரிசை வரிசைப்படுத்தப்பட்டிருந்தால், சமச்சீர் BSTயை திறமையாக உருவாக்க அனுமதிக்கிறது. கோடிட்டுக் காட்டப்பட்டுள்ள படிகளைப் பின்பற்றுவதன் மூலம், ஜாவாஸ்கிரிப்டில் செயல்படும் பிஎஸ்டியை நீங்கள் செயல்படுத்த முடியும், தரவைத் திறமையாகத் தேடுவது அல்லது வரிசைப்படுத்தப்பட்ட தரவை மாறும் வகையில் பராமரிப்பது போன்ற பொதுவான சிக்கல்களைத் தீர்க்கலாம்.

கட்டளை	பயன்பாட்டின் உதாரணம்
Math.floor()	இந்த கட்டளையானது வரிசையின் நடுப்புள்ளியை வட்டமிடுவதன் மூலம் கணக்கிட பயன்படுகிறது. ஒரு துணை மரத்தின் வேரைக் கண்டுபிடிப்பது பைனரி தேடல் மர கட்டுமானத்தில் முக்கியமானது. எடுத்துக்காட்டு: லெட் மிட் = Math.floor(nums.length / 2);
Array.prototype.slice()	நடுப்புள்ளியின் அடிப்படையில் வரிசையை இடது மற்றும் வலது துணைப் பிரிவுகளாகப் பிரிக்க இந்த முறை பயன்படுத்தப்படுகிறது. இது சுழல்நிலை BST உருவாக்கத்திற்காக வரிசையை சிறிய பகுதிகளாகப் பிரிக்க உதவுகிறது. எடுத்துக்காட்டு: lSide = nums.slice(0, mid);
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()	ஒரு நிபந்தனை பூர்த்தியாகும் வரை உறுப்புகளின் மீது லூப்பிங் செய்யப் பயன்படுகிறது. மறுசெயல் அணுகுமுறையில், இந்த லூப் அனைத்து முனைகளும் வரிசையில் செயலாக்கப்படுவதை உறுதி செய்கிறது. எடுத்துக்காட்டு: போது (வரிசை. நீளம்) { ...}
try { ... } catch { ... }	இந்த அமைப்பு விதிவிலக்குகளைக் கையாளப் பயன்படுகிறது, பிழை ஏற்பட்டால், நிரல் செயலிழக்காமல் அதை நிர்வகிக்க முடியும் என்பதை உறுதிசெய்கிறது. எடுத்துக்காட்டு: {...} பிடிக்க முயற்சிக்கவும் (பிழை) { ...}

ஜாவாஸ்கிரிப்டில் பைனரி தேடல் மரத்தின் கட்டுமானத்தைப் புரிந்துகொள்வது

நாங்கள் ஆராய்ந்த முதல் ஸ்கிரிப்ட் உருவாக்குகிறது a ஒரு சுழல்நிலை அணுகுமுறையைப் பயன்படுத்துகிறது. தரவை சிறிய துணைப் பிரச்சனைகளாகப் பிரிக்க வேண்டிய சிக்கல்களைத் தீர்க்க இந்த முறை பயனுள்ளதாக இருக்கும். வரிசையின் நடு உறுப்பைக் கண்டறிவதன் மூலம், அதை மரத்தின் வேர் முனையாகத் தேர்ந்தெடுக்கலாம். வரிசையின் இடது பக்கம், மூலத்தை விட சிறிய கூறுகளைக் கொண்டுள்ளது, இது இடது துணை மரமாக மாறும், அதே நேரத்தில் பெரிய உறுப்புகளுடன் வலது புறம் வலது துணை மரமாக மாறும். அனைத்து கூறுகளும் மரத்தில் செருகப்படும் வரை இந்த செயல்முறை மீண்டும் மீண்டும் செய்யப்படுகிறது.

மறுநிகழ்வு அல்காரிதத்தின் சுத்தமான மற்றும் தர்க்கரீதியான ஓட்டத்தை அனுமதிக்கிறது. இந்த ஸ்கிரிப்டில் ஒரு முக்கிய கட்டளை , இது வரிசையின் நடுப்புள்ளியைக் கணக்கிடப் பயன்படுகிறது மற்றும் மேலும் செயலாக்கத்திற்குப் பிரிக்க உதவுகிறது. மற்றொரு முக்கியமான கட்டளை , இது வரிசையை இரண்டு பகுதிகளாகப் பிரிக்கிறது, இது இடது மற்றும் வலது துணை மரங்களை மீண்டும் மீண்டும் உருவாக்க அனுமதிக்கிறது. இந்த மட்டு அணுகுமுறை BST ஆனது அதன் வரிசைப்படுத்தப்பட்ட கட்டமைப்பை பராமரிக்கும் போது சரியாக உருவாக்கப்படுவதை உறுதி செய்கிறது. இந்த சுழல்நிலை உத்தியானது, வரிசை வரிசைப்படுத்தப்பட்டால், மரம் சமநிலையில் இருப்பதை உறுதி செய்கிறது.

இரண்டாவது ஸ்கிரிப்ட்டில், ஒரு வரிசையைப் பயன்படுத்தி மீண்டும் செயல்படும் அணுகுமுறையை செயல்படுத்தினோம். நினைவகக் கட்டுப்பாடுகள் காரணமாக மறுநிகழ்வு மிகவும் சிக்கலானதாகவோ அல்லது விரும்பப்படாமலோ இருக்கும் போது இந்த முறை நன்மை பயக்கும். முக்கிய யோசனை அப்படியே உள்ளது: நடுப்புள்ளியைக் கண்டறிதல், முனையைச் செருகுதல் மற்றும் வரிசையை சிறிய பகுதிகளாகப் பிரித்தல். இருப்பினும், மறுநிகழ்வுக்குப் பதிலாக, செயலாக்கப்பட வேண்டிய முனைகளைச் சேமிக்க ஒரு வரிசையைப் பயன்படுத்துகிறோம். இந்த மறுசெயல் தீர்வு போன்ற கட்டளைகளைப் பயன்படுத்துகிறது , இது எதிர்கால செயலாக்கத்திற்கான வரிசையில் முனைகளைச் சேர்க்கிறது. அனைத்து முனைகளும் செயலாக்கப்படும் வரை அதே வளையம் தொடர்கிறது, இது முழு மரமும் கட்டமைக்கப்படுவதை உறுதி செய்கிறது.

இறுதியாக, மூன்றாவது ஸ்கிரிப்ட் பிழை கையாளுதல் மற்றும் உள்ளீடு சரிபார்ப்பு ஆகியவற்றை அறிமுகப்படுத்துகிறது. போன்ற கட்டளைகளைப் பயன்படுத்துவதன் மூலம் மற்றும் , மரக் கட்டுமானத்தைத் தொடர்வதற்கு முன், தவறான உள்ளீடுகளைச் சரிபார்ப்பதன் மூலம் குறியீட்டை மிகவும் வலுவானதாக ஆக்குகிறோம். உள்ளீடு சரியானதாக இருந்தால் மட்டுமே எங்கள் பைனரி தேடல் மரம் கட்டமைக்கப்படும் என்பதை இந்தச் சரிபார்ப்புகள் உறுதிசெய்து, இயக்க நேரப் பிழைகளைத் தடுக்கும். இந்த பதிப்பு விதிவிலக்குகளை அழகாக கையாள முயற்சி-பிடிப்பு பிளாக்கை செயல்படுத்துகிறது, இது நிரலை பிழைகளை நிர்வகிக்கவும் அவற்றை சரியாக பதிவு செய்யவும் அனுமதிக்கிறது. இது தீர்வின் நம்பகத்தன்மையை மேம்படுத்துவது மட்டுமல்லாமல், அதன் பாதுகாப்பு மற்றும் செயல்திறனை மேம்படுத்துகிறது, இது பல்வேறு சூழல்களில் சரியாக வேலை செய்வதை உறுதி செய்கிறது.

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 சமநிலையற்றதாக மாறினால், முனைகளைத் தேடுதல், செருகுதல் மற்றும் நீக்குதல் போன்ற சில செயல்பாடுகள் நேரியல் நேர சிக்கலுக்கு (O(n)) சிதைந்துவிடும், இது BSTயைப் பயன்படுத்துவதன் நோக்கத்தைத் தோற்கடிக்கும். AVL மரங்கள் மற்றும் சிவப்பு-கருப்பு மரங்கள் போன்ற அல்காரிதங்கள், முனைகளைச் செருகும்போது அல்லது நீக்கும்போது தானாகவே மரத்தை மறுசீரமைத்து, மரத்தின் உயரம் முனைகளின் எண்ணிக்கையுடன் ஒப்பிடும்போது எப்போதும் மடக்கையாக இருப்பதை உறுதிசெய்கிறது.

ஒரு பிஎஸ்டியை உருவாக்கும் போது மற்றொரு முக்கியமான கருத்தாகும், நகல் மதிப்புகளை எவ்வாறு கையாள்வது என்பது. பல சந்தர்ப்பங்களில், நகல்கள் அனுமதிக்கப்படுவதில்லை அல்லது இடது அல்லது வலது சப்ட்ரீயில் தொடர்ந்து வைப்பதன் மூலம் கையாளப்படுகின்றன. எடுத்துக்காட்டாக, பிஎஸ்டியின் ஒருமைப்பாட்டை பராமரிக்க ஒருவர் இயல்பாகவே வலது சப்ட்ரீயில் நகல்களை வைக்கலாம். நகல்களை சரியான முறையில் நிர்வகிப்பது, கட்டுமான கட்டம் மற்றும் அடுத்தடுத்த செயல்பாடுகள் ஆகிய இரண்டின் போது மரத்தின் செயல்திறன் மற்றும் செயல்திறனை பாதிக்கலாம்.

மேலும், பிழை கையாளுதல் மற்றும் உள்ளீடு சரிபார்ப்பு ஆகியவை உங்கள் பிஎஸ்டி எல்லா சூழ்நிலைகளிலும் சரியாக செயல்படுவதை உறுதிசெய்ய மிகவும் அவசியம். உதாரணமாக, உள்ளீட்டு வரிசை வரிசைப்படுத்தப்பட்டுள்ளதா என்பதைச் சரிபார்ப்பது நேரத்தை மிச்சப்படுத்தலாம் மற்றும் தவறான மர அமைப்புகளைத் தடுக்கலாம். அர்த்தமுள்ள பிழை செய்திகளை எறிவது போன்ற வலுவான பிழை கையாளுதல், இயக்க நேர சிக்கல்களைத் தவிர்க்க உதவுகிறது மற்றும் டெவலப்பரை மிகவும் திறமையாக பிழைத்திருத்த அனுமதிக்கிறது. கூடுதலாக, தற்காப்பு நிரலாக்க நடைமுறைகளை இணைப்பது தவறான அல்லது எதிர்பாராத உள்ளீடு மரத்தை உருவாக்கும் செயல்முறையை தோல்வியடையச் செய்யாது என்பதை உறுதி செய்கிறது.

1. பிஎஸ்டியை உருவாக்க மறுநிகழ்வு எவ்வாறு உதவுகிறது?
2. மறுநிகழ்வு வரிசையை சிறிய துணைக்குழுக்களாகப் பிரிக்கிறது மற்றும் நடுத்தர உறுப்பை ரூட்டாக ஒதுக்குகிறது, இது அனைத்து உறுப்புகளும் வைக்கப்படும் வரை மீண்டும் மீண்டும் செய்யப்படும்.
3. பைனரி தேடல் மரத்தில் நகல் மதிப்புகளை எவ்வாறு கையாள்வது?
4. நீங்கள் இடது அல்லது வலது சப்ட்ரீயில் தொடர்ந்து நகல்களை வைக்கலாம். இது BST பண்புகள் பராமரிக்கப்படுவதை உறுதி செய்கிறது.
5. என்ன முக்கியத்துவம் BST கட்டுமானத்தில்?
6. வரிசையின் நடு உறுப்பைத் தீர்மானிக்க உதவுகிறது, இது துணை மரத்தின் வேராக மாறும்.
7. BST இல் மரத்தை சமநிலைப்படுத்துவது ஏன் முக்கியமானது?
8. சமநிலைப்படுத்துதல் மரத்தை வளைக்காமல் தடுக்கிறது, தேடுதல், செருகுதல் மற்றும் நீக்குதல் போன்ற செயல்பாடுகளுக்கு O(log n) நேரம் எடுக்கும்.
9. எப்படி முடியும் மரம் கட்டுமானத்தை மேம்படுத்தவா?
10. வரிசையை இடது மற்றும் வலது துணைப் பகுதிகளாகப் பிரிக்கப் பயன்படுகிறது, இது மரத்தின் துணை மரங்களை மீண்டும் மீண்டும் உருவாக்க அனுமதிக்கிறது.
11. உள்ளீடு சரிபார்ப்பில் என்ன சரிபார்க்க வேண்டும்?
12. உள்ளீடு சரியான, வரிசைப்படுத்தப்பட்ட வரிசையா என்பதைச் சரிபார்க்கவும். மரத்தை பிழைகள் இல்லாமல் சரியாகக் கட்ட முடியும் என்பதை இது உறுதி செய்கிறது.
13. பிஎஸ்டி கட்டுமானத்தில் பிழை கையாளுதல் என்ன பங்கு வகிக்கிறது?
14. பயன்படுத்துதல் போன்ற பிழை கையாளுதல் , சிக்கல்களை முன்கூட்டியே கண்டறிய உதவுகிறது மற்றும் பயன்பாடு செயலிழப்பதைத் தடுக்கிறது.
15. மறுநிகழ்வை விட மீண்டும் மீண்டும் செய்யும் அணுகுமுறையை நீங்கள் ஏன் தேர்வு செய்யலாம்?
16. மறு செய்கை, பயன்படுத்தி a , மறுநிகழ்வு ஆழத்தில் சாத்தியமான சிக்கல்களைத் தவிர்க்கிறது, குறிப்பாக ஸ்டாக் ஓவர்ஃப்ளோ ஏற்படக்கூடிய பெரிய தரவுத்தொகுப்புகளில்.
17. AVL மற்றும் சிவப்பு-கருப்பு மரங்கள் எவ்வாறு சமநிலையை பராமரிக்க முடியும்?
18. இந்த வழிமுறைகள், மடக்கைத் தேடல் நேரத்தை உறுதி செய்வதற்காக, ஒவ்வொரு செருகும் அல்லது நீக்குதலுக்கும் பிறகு தானாகவே மரத்தை மறுசமநிலைப்படுத்தும்.
19. நடு உறுப்பை வேராக தேர்ந்தெடுப்பதன் முக்கியத்துவம் என்ன?
20. நடுத்தர உறுப்பைத் தேர்ந்தெடுப்பது மரம் சமநிலையில் இருப்பதை உறுதிசெய்கிறது, திறமையற்ற தேடல் பாதைகளைத் தடுக்கிறது.

ஒரு வரிசையிலிருந்து பைனரி தேடல் மரத்தை உருவாக்குவது, வரிசையை துணை அணிகளாகப் பிரித்து, நடு உறுப்பை வேராக ஒதுக்குவதை உள்ளடக்குகிறது. இந்த செயல்முறை திறமையான மற்றும் சீரான மர அமைப்பை பராமரிக்க உதவுகிறது. விரைவான தேடுதல், செருகுதல் மற்றும் நீக்குதல் செயல்பாடுகளை உறுதி செய்வதற்கு ஒரு சமநிலை மரம் முக்கியமானது.

சுழல்நிலை மற்றும் மீண்டும் செயல்படும் அணுகுமுறைகளைப் பயன்படுத்துவதன் மூலம், உங்கள் செயலாக்கத்தில் நெகிழ்வுத்தன்மையை உறுதிசெய்யலாம். பிழை கையாளுதல் மற்றும் உள்ளீடு சரிபார்த்தல் ஆகியவை இயக்க நேரப் பிழைகளைத் தடுப்பதற்கு முக்கியமாகும். இந்த உத்திகள் பைனரி தேடல் மரத்தின் வெற்றிகரமான வளர்ச்சிக்கு வழிவகுக்கும், அது செயல்பாட்டு மற்றும் நம்பகமானது.