Binaarihakupuun rakentaminen JavaScript-taulukosta

Binäärihakupuun rakentaminen rekursiolla

Tämä ratkaisu rakentaa binaarihakupuun taulukosta käyttämällä JavaScriptin rekursiivista lähestymistapaa.

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äärihakupuu käyttäen iteraatiota ja jonoa

Tämä ratkaisu rakentaa binaarihakupuun käyttämällä iteratiivista lähestymistapaa jonon kanssa.

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

Tasapainoinen binäärihakupuu, jossa on virheiden käsittely ja syötteen validointi

Tämä ratkaisu parantaa rekursiivista lähestymistapaa syötteen validoinnilla ja optimoidulla virheenkäsittelyllä.

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

Yleisiä kysymyksiä binaarihakupuiden rakentamisesta JavaScriptissä

1. Miten rekursio auttaa BST:n rakentamisessa?
2. Rekursio jakaa taulukon pienempiin aliryhmiin ja määrittää keskimmäisen elementin juureksi, prosessia toistetaan, kunnes kaikki elementit on sijoitettu.
3. Kuinka käsittelet päällekkäisiä arvoja binäärihakupuussa?
4. Voit sijoittaa kaksoiskappaleita johdonmukaisesti joko vasempaan tai oikeaan alipuuhun. Tämä varmistaa, että BST-ominaisuudet säilyvät.
5. Mikä merkitys on Math.floor() BST rakentamisessa?
6. Math.floor() auttaa määrittämään taulukon keskielementin, josta tulee alipuun juuri.
7. Miksi puiden tasapainottaminen on tärkeää BST:ssä?
8. Tasapainotus estää puuta vääristymästä ja varmistaa, että toiminnot, kuten etsiminen, lisääminen ja poistaminen, vievät O(log n) aikaa.
9. Miten voi slice() parantaa puun rakentamista?
10. slice() käytetään taulukon jakamiseen vasempaan ja oikeaan aliryhmään, mikä mahdollistaa puun alipuiden rekursiivisen rakentamisen.
11. Mitä tulee tarkistaa syötteen validoinnissa?
12. Tarkista, onko syöte kelvollinen lajiteltu matriisi. Tämä varmistaa, että puu voidaan rakentaa oikein ilman virheitä.
13. Mikä rooli virheiden käsittelyllä on BST-rakentamisessa?
14. Virheiden käsittely, kuten käyttö throw new Error(), auttaa tunnistamaan ongelmat varhaisessa vaiheessa ja estää sovellusta kaatumasta.
15. Miksi voit valita iteratiivisen lähestymistavan rekursion sijaan?
16. Iterointi käyttäen a queue, välttää mahdolliset rekursion syvyyteen liittyvät ongelmat, erityisesti suurissa tietojoukoissa, joissa pinon ylivuoto voi tapahtua.
17. Kuinka AVL- ja puna-mustat puut voivat säilyttää tasapainon?
18. Nämä algoritmit tasapainottavat puun automaattisesti uudelleen jokaisen lisäyksen tai poiston jälkeen logaritmisen hakuajan varmistamiseksi.
19. Mitä merkitystä on keskielementin valitsemisella juureksi?
20. Keskimmäisen elementin valinta varmistaa, että puu pysyy tasapainossa, mikä estää tehottomia hakupolkuja.

Viimeiset ajatukset binaarisista hakupuista

Binaarihakupuun rakentaminen taulukosta sisältää taulukon jakamisen aliryhmiksi ja keskimmäisen elementin määrittämisen juureksi. Tämä prosessi auttaa säilyttämään tehokkaan ja tasapainoisen puurakenteen. Tasapainotettu puu on ratkaisevan tärkeä nopean haku-, lisäys- ja poistotoimintojen varmistamiseksi.

Käyttämällä sekä rekursiivisia että iteratiivisia lähestymistapoja voit varmistaa toteutuksen joustavuuden. Virheiden käsittelyn ja syötteiden validoinnin toteuttaminen on avainasemassa ajonaikaisten virheiden estämisessä. Nämä strategiat johtavat onnistuneeseen binäärihakupuun kehittämiseen, joka on sekä toimiva että luotettava.