Hogyan működik egy bináris fa?

Egy bináris fa olyan adatstruktúra, amely fa alakú, ahol minden csomópontnak legfeljebb két gyermekcsomópontja van: bal és jobb.

Működési alapelvek:

• Gyökér: A fa legfelső csomópontja.
• Csomópontok: Adatokat tartalmaznak és hivatkozásokat a gyermekcsomópontokra.
• Levél: Gyermekcsomópont nélküli csomópont.
• Kapcsolatok: A szülőcsomópontból a gyermekcsomópontok felé irányulnak.

Fő műveletek:

• Beszúrás: Új csomópontokat adunk hozzá a fa meghatározott helyére, megőrizve szerkezetét és szabályait (például, bináris keresőfa esetén: kisebb értékek balra, nagyobbak jobbra).
• Keresés: A csomópontokon való végigjárás a konkrét elem megtalálásához. A bináris keresőfában a keresés hatékony a rendezett adatok miatt.
• Törlés: Egy csomópont törlése a fa szerkezetének újraépítésével.
• Bejárás: A fa összes csomópontjának meglátogatása meghatározott sorrendben:
  • Pre-order: Gyökér, bal alfa, jobb alfa.
  • Post-order: Bal alfa, jobb alfa, gyökér.
  • In-order: Bal alfa, gyökér, jobb alfa (rendezett listát ad az elemekről).

Előnyök:

• Hatékony keresés, beszúrás és törlés (kiegyensúlyozott fák esetén).
• Hierarchikus adatok ábrázolására használják.

PHP példakód egy csomópont szerkezetére:

<?php

class Node {
    public $data; // Csomópont adatai
    public $left; // Bal gyermek
    public $right; // Jobb gyermek

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