Binārā meklēšanas koka izveide no JavaScript masīva

Binārās meklēšanas koka veidošana, izmantojot rekursiju

Šis risinājums veido bināro meklēšanas koku no masīva, izmantojot JavaScript rekursīvo pieeju.

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);

Binārais meklēšanas koks, izmantojot iterāciju un rindu

Šis risinājums konstruē bināro meklēšanas koku, izmantojot iteratīvu pieeju ar rindu.

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);

Līdzsvarots binārās meklēšanas koks ar kļūdu apstrādi un ievades validāciju

Šis risinājums uzlabo rekursīvo pieeju ar ievades validāciju un optimizētu kļūdu apstrādi.

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);
}

Bieži uzdotie jautājumi par bināro meklēšanas koku veidošanu JavaScript

1. Kā rekursija palīdz izveidot BST?
2. Rekursija sadala masīvu mazākos apakšblokos un piešķir vidējo elementu kā sakni, process tiek atkārtots, līdz tiek ievietoti visi elementi.
3. Kā rīkoties ar dublētām vērtībām binārā meklēšanas kokā?
4. Varat konsekventi ievietot dublikātus gan kreisajā, gan labajā apakškokā. Tas nodrošina BST īpašību saglabāšanu.
5. Kāda ir nozīme Math.floor() BST celtniecībā?
6. Math.floor() palīdz noteikt masīva vidējo elementu, kas kļūst par apakškoka sakni.
7. Kāpēc koku balansēšana ir svarīga BST?
8. Līdzsvarošana novērš koka sašķiebšanos, nodrošinot, ka tādas darbības kā meklēšana, ievietošana un dzēšana aizņem O(log n) laiku.
9. Kā var slice() uzlabot koku būvniecību?
10. slice() tiek izmantots, lai sadalītu masīvu kreisajā un labajā apakšmasīvā, ļaujot rekursīvi konstruēt koka apakškokus.
11. Kas ir jāpārbauda ievades validācijā?
12. Pārbaudiet, vai ievade ir derīgs, sakārtots masīvs. Tas nodrošina, ka koku var uzbūvēt pareizi, bez kļūdām.
13. Kāda loma kļūdu apstrādei ir BST konstrukcijā?
14. Kļūdu apstrāde, piemēram, lietošana throw new Error(), palīdz savlaicīgi identificēt problēmas un novērš lietojumprogrammas avāriju.
15. Kāpēc jūs varētu izvēlēties iteratīvu pieeju, nevis rekursiju?
16. Iterācija, izmantojot a queue, novērš iespējamās problēmas ar rekursijas dziļumu, īpaši lielās datu kopās, kur var rasties steka pārpilde.
17. Kā AVL un Red-Black koki var saglabāt līdzsvaru?
18. Šie algoritmi automātiski līdzsvaro koku pēc katras ievietošanas vai dzēšanas, lai nodrošinātu logaritmisko meklēšanas laiku.
19. Kāda nozīme ir vidējā elementa izvēlei kā saknei?
20. Vidējā elementa izvēle nodrošina, ka koks paliek līdzsvarots, novēršot neefektīvus meklēšanas ceļus.

Pēdējās domas par binārajiem meklēšanas kokiem

Binārā meklēšanas koka konstruēšana no masīva ietver masīva sadalīšanu apakšmasīvās un vidējā elementa piešķiršanu kā sakni. Šis process palīdz uzturēt efektīvu un līdzsvarotu koka struktūru. Līdzsvarots koks ir ļoti svarīgs, lai nodrošinātu ātras meklēšanas, ievietošanas un dzēšanas darbības.

Izmantojot gan rekursīvo, gan iteratīvo pieeju, jūs varat nodrošināt ieviešanas elastību. Kļūdu apstrādes un ievades validācijas ieviešana ir galvenais, lai novērstu izpildlaika kļūdas. Šīs stratēģijas noved pie veiksmīgas bināra meklēšanas koka izstrādes, kas ir gan funkcionāls, gan uzticams.