Kuidas töötab binaarne puu?

Binaarne puu on puustruktuur, kus iga sõlm omab mitte rohkem kui kahte järglast: vasakut ja paremat.

Tööpõhimõtted:

• Juure: puu ülaosas olev sõlm.
• Sõlmed: sisaldavad andmeid ja viiteid järglastele.
• Lehed: sõlmed ilma järglasteta.
• Seosed: suunatud vanem-sõlmelt järglastele.

Põhitegevused:

• Lisamine: uued sõlmed lisatakse kindlasse kohta puus, säilitades struktuuri ja reeglid (näiteks binaarse otsingupuu puhul: väiksemad väärtused vasakul, suuremad paremal).
• Otsing: sõlmede läbimine vajaliku elemendi leidmiseks. Binaarses otsingupuus on otsing tõhus andmete järjepidevuse tõttu.
• Kustutamine: sõlme eemaldamine ja puu struktuuri ümberkorraldamine.
• Käimine: kõigi sõlmede külastamine kindlas järjekorras:
  • Esmalt (Pre-order): juur, vasak alampuu, parem alampuu.
  • Tagurpidi (Post-order): vasak alampuu, parem alampuu, juur.
  • Sümboolne (In-order): vasak alampuu, juur, parem alampuu (binaarse otsingupuu puhul annab sorteeritud nimekirja).

Eelised:

• Tõhus otsing, lisamine ja kustutamine (tasakaalustatud puudel).
• Kasutatakse hierarhiliste andmete esitamiseks.

Näide sõlme struktuurist PHP-s:

<?php

class Node {
    public $data; // Sõlme andmed
    public $left; // Vasak järglane
    public $right; // Parem järglane

    public function __construct($data) {
        $this->data = $data;
        $this->left = null;
        $this->right = null;
    }
}