Wyszukiwanie wartości z użyciem struktur danych (drzewa BST, hashtable)

Założenie: Pokażemy, jak wykorzystać drzewa BST i tablice haszujące do efektywnego wyszukiwania wartości w dużych zbiorach danych.

Krok po kroku:

1. Implementacja prostego drzewa BST:

data = $data;
    $this->left = null;
    $this->right = null;
  }
}

class BST {
  public $root;

  public function __construct() {
    $this->root = null;
  }

  public function insert($data) {
    $this->root = $this->insertRecursive($this->root, $data);
  }

  private function insertRecursive($node, $data) {
    if ($node == null) {
      return new Node($data);
    }

    if ($data < $node->data) {
      $node->left = $this->insertRecursive($node->left, $data);
    } else {
      $node->right = $this->insertRecursive($node->right, $data);
    }

    return $node;
  }

  public function search($data) {
    return $this->searchRecursive($this->root, $data);
  }

  private function searchRecursive($node, $data) {
    if ($node == null || $node->data == $data) {
      return $node;
    }

    if ($data < $node->data) {
      return $this->searchRecursive($node->left, $data);
    } else {
      return $this->searchRecursive($node->right, $data);
    }
  }
}

$bst = new BST();
$bst->insert(5);
$bst->insert(3);
$bst->insert(7);
$bst->insert(1);
$bst->insert(4);

$found = $bst->search(4);
if ($found) {
  echo "Znaleziono wartość: " . $found->data;
} else {
  echo "Wartość nie znaleziona.";
}
?>
				

Ten kod implementuje proste drzewo BST z metodami wstawiania i wyszukiwania. Wyszukiwanie jest rekurencyjne i przechodzi przez drzewo, porównując wartość z węzłami.

2. Implementacja tablicy haszującej (używając tablicy asocjacyjnej PHP):

PHP oferuje wbudowane tablice asocjacyjne, które działają jak proste tablice haszujące. Kluczem jest nazwa owocu, a wartością – jego identyfikator. Sprawdzanie istnienia klucza jest bardzo szybkie.

Podsumowanie: Ten przykład pokazuje podstawy wyszukiwania w zaawansowanych strukturach danych. Drzewa BST są efektywne dla posortowanych danych, a tablice haszujące dla szybkiego dostępu do elementów po kluczu. Zachęcamy do dalszego zgłębiania tematu!