Gradnja binarnega iskalnega drevesa iz matrike JavaScript

Konstrukcija binarnega iskalnega drevesa z uporabo rekurzije

Ta rešitev zgradi binarno iskalno drevo iz matrike z uporabo rekurzivnega pristopa v 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 iskalno drevo z uporabo iteracije in čakalne vrste

Ta rešitev sestavi binarno iskalno drevo z uporabo iterativnega pristopa s čakalno vrsto.

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

Uravnoteženo binarno iskalno drevo z obravnavanjem napak in preverjanjem vnosa

Ta rešitev izboljšuje rekurzivni pristop s preverjanjem vnosa in optimiziranim obravnavanjem napak.

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

Pogosta vprašanja o gradnji binarnih iskalnih dreves v JavaScriptu

1. Kako rekurzija pomaga pri konstruiranju BST?
2. Rekurzija razdeli matriko na manjše podnize in srednji element dodeli kot koren, postopek se ponavlja, dokler niso postavljeni vsi elementi.
3. Kako ravnate s podvojenimi vrednostmi v binarnem iskalnem drevesu?
4. Dvojnike lahko dosledno postavite v levo ali desno poddrevo. To zagotavlja ohranitev lastnosti BST.
5. Kakšen je pomen Math.floor() pri gradnji BST?
6. Math.floor() pomaga določiti srednji element matrike, ki postane koren poddrevesa.
7. Zakaj je drevesno uravnoteženje pomembno v BST?
8. Uravnoteženje preprečuje, da bi drevo postalo poševno, kar zagotavlja, da operacije, kot so iskanje, vstavljanje in brisanje, trajajo O(log n) časa.
9. Kako lahko slice() izboljšati konstrukcijo drevesa?
10. slice() se uporablja za razdelitev matrike na levo in desno podniz, kar omogoča rekurzivno konstrukcijo poddreves drevesa.
11. Kaj je treba preveriti pri preverjanju vnosa?
12. Preverite, ali je vnos veljavna, razvrščena matrika. To zagotavlja, da je drevo mogoče pravilno sestaviti brez napak.
13. Kakšno vlogo ima obravnavanje napak pri konstrukciji BST?
14. Odpravljanje napak, kot je uporaba throw new Error(), pomaga pri zgodnjem odkrivanju težav in preprečuje zrušitev aplikacije.
15. Zakaj bi morda izbrali iterativni pristop namesto rekurzije?
16. Ponovitev z uporabo a queue, se izogne ​​morebitnim težavam z globino rekurzije, zlasti v velikih naborih podatkov, kjer lahko pride do prelivanja sklada.
17. Kako lahko AVL in rdeče-črna drevesa vzdržujejo ravnovesje?
18. Ti algoritmi samodejno ponovno uravnotežijo drevo po vsakem vstavljanju ali brisanju, da zagotovijo logaritemske čase iskanja.
19. Kakšen je pomen izbire srednjega elementa kot korena?
20. Izbira srednjega elementa zagotavlja, da drevo ostane uravnoteženo, kar preprečuje neučinkovite iskalne poti.

Končne misli o binarnih iskalnih drevesih

Konstruiranje binarnega iskalnega drevesa iz matrike vključuje razdelitev matrike na podmatrike in dodelitev srednjega elementa kot korena. Ta postopek pomaga ohranjati učinkovito in uravnoteženo drevesno strukturo. Uravnoteženo drevo je ključnega pomena za zagotavljanje hitrih operacij iskanja, vstavljanja in brisanja.

Z uporabo rekurzivnih in iterativnih pristopov lahko zagotovite prožnost pri izvajanju. Implementacija obravnavanja napak in preverjanja vnosa je ključnega pomena za preprečevanje napak med izvajanjem. Te strategije vodijo k uspešnemu razvoju binarnega iskalnega drevesa, ki je funkcionalno in zanesljivo.