Kaip veikia dvejetainis medis?

Dvigubas medis yra duomenų struktūra, kuri yra medžio formos, kur kiekvienas mazgas turi ne daugiau kaip du vaikus: kairį ir dešinį.

Veikimo principai:

• Šaknis: Aukščiausias medis mazgas.
• Mazgai: Laiko duomenis ir nuorodas į vaikus.
• Gėlės: Mazgai be vaikų.
• Ryšiai: Nukreipti nuo tėvo mazgo į vaikus.

Pagrindinės operacijos:

• Įterpimas: Nauji mazgai pridedami į tam tikrą vietą medyje, išlaikant jo struktūrą ir taisykles (pavyzdžiui, dvigubo paieškos medžio atveju: mažesnės reikšmės kairėje, didesnės dešinėje).
• Paieška: Mazgų peržiūra, siekiant rasti konkretų elementą. Dvigubo paieškos medyje paieška yra efektyvi dėl duomenų tvarkos.
• Šalinimas: Mazgo šalinimas su struktūros pertvarkymu.
• Aplankymas: Visų medžio mazgų lankymas tam tikru tvarkymu:
  • Pre-order: Šaknis, kairysis pogrupis, dešinysis pogrupis.
  • Post-order: Kairysis pogrupis, dešinysis pogrupis, šaknis.
  • In-order: Kairysis pogrupis, šaknis, dešinysis pogrupis (suteikia surūšiuotą elementų sąrašą).

Privalumai:

• Efektyvus paieška, įterpimas ir šalinimas (subalansuotuose medžiuose).
• Naudojamas hierarchinių duomenų atvaizdavimui.

PHP pavyzdys mazgo struktūrai:

<?php

class Node {
    public $data; // Mazgo duomenys
    public $left; // Kairysis vaikas
    public $right; // Dešinysis vaikas

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