Afirmacja dnia: Pamiętaj, aby być dla siebie dobrym 🌟

Drzewo wyszukiwania binarnego to struktura danych posiadająca następujące właściwości:

O. Każdy węzeł drzewa ma maksymalnie dwoje dzieci

B. Wszystkie węzły w prawym poddrzewie są większe niż korzeń

C. Wszystkie węzły w lewym poddrzewie są mniejsze niż korzeń

Uwaga: korzeń jest pierwszym węzłem w drzewie

Najlepszy możliwy scenariusz drzewa wyszukiwania binarnego to 0 (log n). Dzieje się tak, ponieważ aby wyszukać(), tj. znaleźć lub usunąć węzeł, musielibyśmy iterować po węźle, a następnie dzielić drzewo przy każdej iteracji. Dzięki temu funkcje wyszukiwania() i usuwania() przy użyciu drzewa wyszukiwania binarnego są znacznie szybsze niż przy użyciu listy połączonej (zobaczymy dlaczego poniżej).

Najgorszy możliwy scenariusz drzewa wyszukiwania binarnego to 0(n). Dlatego duże 0 drzewa wyszukiwania binarnego to 0 (n). Najgorszy scenariusz drzewa wyszukiwania binarnego może wystąpić, gdy w prawym poddrzewie drzewa znajdują się tylko węzły (lewe poddrzewo jest puste) lub w lewym poddrzewie drzewa znajdują się tylko węzły (prawe poddrzewo jest puste). Tutaj nie mamy korzyści z dzielenia naszych problemów na pół {0(log n), czas logarytmiczny}, ponieważ działamy w linii prostej. Działa to podobnie do list połączonych.

Binarne drzewa wyszukiwania a listy połączone

Jak wspomniano powyżej, działamy w linii prostej na liście połączonej. Zatem jeśli szukamy węzła lub próbujemy go usunąć, musielibyśmy iterować po połączonej liście. Są to operacje 0(n).

Jednakże wstawienie elementu na koniec połączonej listy, tj. push wynosi 0(1). Zatem metoda Insert() jest lepsza w przypadku listy połączonej niż drzewa wyszukiwania binarnego, ponieważ 0(1) jest bardziej wydajne niż 0(log n).

W podsumowaniu:

Zaimplementujmy drzewo wyszukiwania binarnego (BST)!

BST: Wstaw()

W przypadku tej metody:

  1. Utwórz nowy węzeł.
  2. Utwórz instrukcję warunkową, jeśli drzewo jest puste.
  3. Użyj instrukcji warunkowej, jeśli wstawiany węzeł ma tę samą wartość, co węzeł, który jest już w drzewie.
  4. Porównaj węzeł, który chcemy wstawić z pierwszym węzłem, jeśli jest od niego mniejszy lub mniejszy od poprzedniego węzła, przesuwa się w lewo, a jeśli jest od niego większy lub większy od poprzedniego węzła, przesuwa się w prawo.
  5. Jeśli jest null (pusta przestrzeń) wstawiamy nowy węzeł do tej przestrzeni, w przeciwnym razie przechodzimy do następnego węzła i porównujemy (jak w kroku 4).
  6. Zrób sobie pętlę while, ponieważ nie wiemy, ile razy wykonamy pętlę przez drzewo. Oznacza to, że nie wiemy, ile razy wykonamy kroki 4 i 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: Zawiera()

Tutaj szukamy węzła znajdującego się wewnątrz drzewa.

Zaczynamy od korzenia drzewa i albo a) mamy pełne drzewo, po którym możemy iterować, albo b) mamy puste drzewo, zatem korzeń będzie równy zero.

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: Wartość minimalna()

Chcemy zwrócić węzeł zawierający minimalną wartość (najmniejszą liczbę) w drzewie. Jeśli lewe poddrzewo nie jest puste, uruchamiamy pętlę while, aż otrzymamy minimalną wartość. Jeśli jest pusty, wychodzimy z pętli while i zwracamy bieżący węzeł, który ma wartość minimalną.

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