Binaarse otsingupuu loomine JavaScripti massiivist

Binaarne otsingupuu ehitamine rekursiooni abil

See lahendus loob massiivist binaarse otsingupuu, kasutades JavaScripti rekursiivset lähenemist.

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

Binaarne otsingupuu, kasutades iteratsiooni ja järjekorda

See lahendus konstrueerib binaarse otsingupuu, kasutades järjekorraga iteratiivset lähenemist.

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

Tasakaalustatud binaarne otsingupuu koos vigade käsitlemise ja sisendi kinnitamisega

See lahendus täiustab rekursiivset lähenemist sisendi valideerimise ja optimeeritud vigade käsitlemisega.

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

Levinud küsimused binaarsete otsingupuude loomise kohta JavaScriptis

1. Kuidas aitab rekursioon BST koostamisel?
2. Rekursioon jagab massiivi väiksemateks alammassiivideks ja määrab keskmise elemendi juureks, seda protsessi korratakse seni, kuni kõik elemendid on paigutatud.
3. Kuidas käsitlete binaarses otsingupuus dubleerivaid väärtusi?
4. Saate paigutada duplikaate järjepidevalt kas vasakusse või paremasse alampuusse. See tagab BST omaduste säilimise.
5. Mis tähtsus on Math.floor() BST ehituses?
6. Math.floor() aitab määrata massiivi keskmist elementi, millest saab alampuu juur.
7. Miks on puude tasakaalustamine BST-s oluline?
8. Tasakaalustamine väldib puu kaldumist, tagades, et toimingud, nagu otsimine, sisestamine ja kustutamine, võtavad O(log n) aega.
9. Kuidas saab slice() parandada puuehitust?
10. slice() kasutatakse massiivi jagamiseks vasak- ja parempoolseteks alamkihtideks, võimaldades puu alampuude rekursiivset konstrueerimist.
11. Mida tuleks sisendi kontrollimisel kontrollida?
12. Kontrollige, kas sisend on kehtiv sorteeritud massiiv. See tagab, et puu saab õigesti ja vigadeta üles ehitada.
13. Millist rolli mängib veakäsitlus BST ehitamisel?
14. Vigade käsitlemine, näiteks kasutamine throw new Error(), aitab probleeme varakult tuvastada ja takistab rakenduse kokkujooksmist.
15. Miks võiksite valida iteratiivse lähenemisviisi rekursiooni asemel?
16. Iteratsioon, kasutades a queue, väldib võimalikke probleeme rekursiooni sügavusega, eriti suurtes andmekogumites, kus võib tekkida virna ülevool.
17. Kuidas suudavad AVL ja puna-must puud säilitada tasakaalu?
18. Need algoritmid tasakaalustavad puu automaatselt pärast iga sisestamist või kustutamist, et tagada logaritmilised otsinguajad.
19. Mis tähtsus on keskmise elemendi juureks valimisel?
20. Keskmise elemendi valimine tagab, et puu püsib tasakaalus, vältides ebaefektiivseid otsinguteid.

Viimased mõtted binaarsete otsingupuude kohta

Binaarse otsingupuu koostamine massiivist hõlmab massiivi jagamist alammassiivideks ja keskmise elemendi määramist juureks. See protsess aitab säilitada tõhusat ja tasakaalustatud puustruktuuri. Tasakaalustatud puu on kiire otsingu-, sisestamis- ja kustutamistoimingute tagamiseks ülioluline.

Kasutades nii rekursiivset kui ka iteratiivset lähenemist, saate tagada oma rakendamisel paindlikkuse. Veakäsitluse ja sisendi valideerimise rakendamine on käitusvigade vältimise võti. Need strateegiad viivad binaarse otsingupuu eduka väljatöötamiseni, mis on nii funktsionaalne kui ka usaldusväärne.