Изградња стабла бинарног претраживања из ЈаваСцрипт низа

Конструкција стабла бинарног претраживања коришћењем рекурзије

Ово решење гради бинарно стабло претраге из низа користећи рекурзивни приступ у ЈаваСцрипт-у.

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

Бинарно стабло претраге користећи итерацију и ред

Ово решење конструише бинарно стабло претраге користећи итеративни приступ са редом.

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

Уравнотежено стабло бинарне претраге са руковањем грешкама и валидацијом уноса

Ово решење побољшава рекурзивни приступ са валидацијом уноса и оптимизованим руковањем грешкама.

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

Уобичајена питања о изградњи стабала бинарног претраживања у ЈаваСцрипт-у

1. Како рекурзија помаже у конструисању БСТ-а?
2. Рекурзија дели низ на мање поднизе и додељује средњи елемент као корен, процес се понавља док се сви елементи не поставе.
3. Како поступате са дуплираним вредностима у бинарном стаблу претраге?
4. Дупликате можете постављати доследно у лево или десно подстабло. Ово осигурава да се БСТ својства одржавају.
5. У чему је важност Math.floor() у БСТ изградњи?
6. Math.floor() помаже у одређивању средњег елемента низа, који постаје корен подстабла.
7. Зашто је балансирање стабла важно у БСТ-у?
8. Балансирање спречава да дрво постане искошено, осигуравајући да операције као што су претраживање, уметање и брисање трају О(лог н) времена.
9. Како могу slice() побољшати конструкцију дрвета?
10. slice() се користи за поделу низа на леви и десни подниз, омогућавајући рекурзивну конструкцију подстабала дрвета.
11. Шта треба проверити у валидацији уноса?
12. Проверите да ли је унос исправан, сортиран низ. Ово осигурава да се дрво може правилно конструисати без грешака.
13. Какву улогу игра руковање грешкама у БСТ конструкцији?
14. Руковање грешкама, као што је коришћење throw new Error(), помаже рано идентификовање проблема и спречава пад апликације.
15. Зашто бисте могли да изаберете итеративни приступ уместо рекурзије?
16. Итерација, користећи а queue, избегава потенцијалне проблеме са дубином рекурзије, посебно у великим скуповима података где може доћи до преливања стека.
17. Како АВЛ и црвено-црно дрвеће могу одржати равнотежу?
18. Ови алгоритми аутоматски ребалансирају стабло након сваког уметања или брисања како би се осигурала логаритамска времена претраживања.
19. Какав је значај одабира средњег елемента као корена?
20. Избор средњег елемента осигурава да стабло остане уравнотежено, спречавајући неефикасне путеве претраживања.

Завршна размишљања о стаблима бинарног претраживања

Конструисање бинарног стабла претраге из низа укључује цепање низа на поднизе и додељивање средњег елемента као корена. Овај процес помаже у одржавању ефикасне и уравнотежене структуре дрвета. Уравнотежено стабло је кључно за обезбеђивање брзих операција претраживања, уметања и брисања.

Користећи и рекурзивни и итеративни приступ, можете осигурати флексибилност у својој имплементацији. Имплементација руковања грешкама и валидације уноса је кључна за спречавање грешака током извршавања. Ове стратегије доводе до успешног развоја бинарног стабла претраге које је и функционално и поуздано.