Izrada stabla binarnog pretraživanja iz JavaScript polja

Konstrukcija stabla binarnog pretraživanja korištenjem rekurzije

Ovo rješenje gradi binarno stablo pretraživanja iz niza pomoću rekurzivnog pristupa u JavaScriptu.

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

Binarno stablo pretraživanja korištenjem iteracije i reda čekanja

Ovo rješenje konstruira binarno stablo pretraživanja koristeći iterativni pristup s redom čekanja.

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

Stablo uravnoteženog binarnog pretraživanja s rukovanjem pogreškama i provjerom valjanosti unosa

Ovo rješenje poboljšava rekurzivni pristup s provjerom valjanosti unosa i optimiziranim rukovanjem pogreškama.

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

Uobičajena pitanja o izgradnji stabala binarnog pretraživanja u JavaScriptu

1. Kako rekurzija pomaže u konstruiranju BST-a?
2. Rekurzija dijeli niz u manje podnizove i dodjeljuje srednji element kao korijen, proces se ponavlja dok se svi elementi ne postave.
3. Kako postupati s dupliciranim vrijednostima u stablu binarnog pretraživanja?
4. Duplikate možete dosljedno postavljati u lijevo ili desno podstablo. Ovo osigurava održavanje BST svojstava.
5. Koja je važnost Math.floor() u BST konstrukciji?
6. Math.floor() pomaže odrediti srednji element niza, koji postaje korijen podstabla.
7. Zašto je balansiranje stabla važno u BST-u?
8. Balansiranje sprječava da stablo postane iskrivljeno, osiguravajući da operacije kao što su pretraživanje, umetanje i brisanje traju O(log n) vremena.
9. Kako može slice() poboljšati konstrukciju stabla?
10. slice() koristi se za dijeljenje niza u lijeve i desne podnizove, dopuštajući rekurzivnu konstrukciju podstabala stabla.
11. Što treba provjeriti u validaciji unosa?
12. Provjerite je li unos važeći, sortirani niz. To osigurava da se stablo može pravilno konstruirati bez grešaka.
13. Kakvu ulogu igra rukovanje pogreškama u izgradnji BST-a?
14. Rješavanje pogrešaka, kao što je korištenje throw new Error(), pomaže u ranom prepoznavanju problema i sprječava pad aplikacije.
15. Zašto biste mogli odabrati iterativni pristup umjesto rekurzije?
16. Iteracija, koristeći a queue, izbjegava potencijalne probleme s dubinom rekurzije, posebno u velikim skupovima podataka gdje bi moglo doći do prekoračenja stogova.
17. Kako AVL i crveno-crno drveće mogu održati ravnotežu?
18. Ovi algoritmi automatski rebalansiraju stablo nakon svakog umetanja ili brisanja kako bi se osiguralo logaritamsko vrijeme pretraživanja.
19. Koje je značenje odabira srednjeg elementa kao korijena?
20. Odabir srednjeg elementa osigurava da stablo ostane uravnoteženo, sprječavajući neučinkovite putove pretraživanja.

Završne misli o stablima binarnog pretraživanja

Konstruiranje binarnog stabla pretraživanja iz niza uključuje dijeljenje niza u podnizove i dodjeljivanje srednjeg elementa kao korijena. Ovaj proces pomaže u održavanju učinkovite i uravnotežene strukture stabla. Uravnoteženo stablo ključno je za osiguravanje brzih operacija pretraživanja, umetanja i brisanja.

Korištenjem i rekurzivnog i iterativnog pristupa, možete osigurati fleksibilnost u svojoj implementaciji. Implementacija rukovanja pogreškama i provjere valjanosti unosa ključni su za sprječavanje pogrešaka tijekom izvođenja. Ove strategije dovode do uspješnog razvoja stabla binarnog pretraživanja koje je i funkcionalno i pouzdano.