Аффирмация дня: не забывайте быть добрым к себе 🌟

Двоичное дерево поиска — это структура данных, обладающая следующими свойствами:

A. У каждого узла дерева может быть не более двух дочерних элементов.

B. Все узлы в правом поддереве больше корня

C. Все узлы в левом поддереве меньше корня

NB: корень — это первый узел в дереве.

Наилучший возможный сценарий бинарного дерева поиска — 0(log n). Это связано с тем, что для lookup(), т. е. найти или удалить узел, нам пришлось бы перебирать узел, а затем делить дерево на каждой итерации. Это делает lookup() и remove() намного быстрее при использовании бинарного дерева поиска, чем при использовании связанного списка (ниже мы увидим, почему).

Наихудший возможный сценарий бинарного дерева поиска — 0(n). Следовательно, Большой 0 бинарного дерева поиска равен 0(n). Наихудший сценарий бинарного дерева поиска может иметь место, когда в правом поддереве дерева есть только узлы (левое поддерево пусто) или есть только узлы в левом поддереве дерева (правое поддерево пусто). Здесь мы не получаем преимущества деления наших задач пополам {0(log n), логарифмическое время}, поскольку мы работаем по прямой. Это похоже на связанные списки.

Бинарные деревья поиска против связанных списков

Как упоминалось выше, мы работаем по прямой в связанном списке. Таким образом, если мы ищем узел или пытаемся удалить узел, нам придется перебирать связанный список. Это 0(n) операций.

Однако вставка элемента в конец связанного списка, т. е. push — это 0(1). Таким образом, метод insert() лучше работает со связанным списком, чем с бинарным деревом поиска, потому что 0(1) более эффективен, чем 0(log n).

В итоге:

Давайте реализуем бинарное дерево поиска (BST)!

BST: Вставить()

Для этого метода мы:

  1. Создайте новый узел.
  2. Условный оператор, если дерево пусто.
  3. Имейте условный оператор, если вставляемый узел имеет то же значение, что и узел, который уже находится в дереве.
  4. Сравните узел, который мы пытаемся вставить, с 1-м узлом, если он меньше или меньше предыдущего узла, он идет влево, а если он больше или больше предыдущего узла, он идет вправо.
  5. Если это null (пустое пространство), мы вставляем новый узел в это пространство, в противном случае мы переходим к следующему узлу и сравниваем (как на шаге 4).
  6. Используйте цикл while, потому что мы не знаем, сколько раз мы будем проходить по дереву. То есть мы не знаем, сколько раз будем делать шаги 4 и 5.
insert(value){
const newNode = new Node(value); //we create a new Node
if(this.root === null){
this.root = newNode;
return this; //if we have an empty tree, root is set equal to the new Node and is returned
  }
let temp = this.root //we create a temp variable to point to the parent element and we will use temp to iterate through the list
while(true){
if(newNode.value === temp.value) return undefined {
 if(newNode.value < temp.value) {
    if (temp.left === null){
    temp.left = newNode;
    return this; //returns the entire tree
        }
     temp = temp.left; //if the space isn't open on the left side of the tree
      } else {
      if (temp.right === null) {
      temp.right = newNode;
       return this;
        }
  temp = temp.right;
      }
    }
  }
}

BST: Содержит()

Здесь мы ищем узел внутри дерева.

Мы начинаем с корня дерева, и либо а) у нас есть полное дерево, по которому мы можем выполнить итерацию, либо б) у нас есть пустое дерево, поэтому корень будет равен нулю.

contains(value) {
  if(this.root === null) return false;
    let temp = this.root //if we have items in the tree, we create a variable temp and use it to iterate through the tree
      while(temp){
      if (value < temp.value){
          temp = temp.left; //if the number we're looking for is less than the parent, temp moves to the left and down
      } else if (value > temp.value){
      temp = temp.right; //if the number is greater than the parent, temp moves to the right
      } else{
         return true; //if the values are the same return true 
      }
      return false; //if temp is equal to null it'll return false and break out of the while loop. For instance if we're looking for a number that's not in the tree
    }
  }

BST: минимальное значение()

Мы хотим вернуть узел, содержащий минимальное значение (наименьшее число) в дереве. Если левое поддерево не пусто, мы запускаем цикл while, пока не получим минимальное значение. Если он пуст, мы выходим из цикла while и возвращаем текущий узел, который является минимальным значением.

minValueNode(currentNode) {
  while (currentNode.left != null){
    currentNode = currentNode.left
  }
  return currentNode
}