Kā darbojas binārais koks?

Divkāršais koks ir datu struktūra, kas ir koka formā, kur katrs mezgls var saturēt ne vairāk kā divus bērnus: kreiso un labo.

Darbības principi:

• Koks: Augšējais mezgls.
• Mezgli: Satur datus un atsauces uz bērnu mezgliem.
• Lapas: Mezgli bez bērniem.
• Saites: Virzītas no vecāku mezgla uz bērniem.

Galvenās operācijas:

• Ievietošana: Jauni mezgli tiek pievienoti noteiktā vietā kokā, saglabājot tā struktūru un noteikumus (piemēram, divkāršā meklēšanas kokā: mazākas vērtības pa kreisi, lielākas pa labi).
• Meklēšana: Pārlūkošana pa mezgliem, lai atrastu konkrētu elementu. Divkāršā meklēšanas kokā meklēšana ir efektīva datu sakārtotības dēļ.
• Dzēšana: Mezglu dzēšana ar kokas struktūras pārkārtošanu.
• Apmeklējums: Visu koka mezglu apmeklējums noteiktā secībā:
  • Pre-order: Koks, kreisais apakškoks, labais apakškoks.
  • Post-order: Kreisais apakškoks, labais apakškoks, koks.
  • In-order: Kreisais apakškoks, koks, labais apakškoks (sniedz sakārtotu elementu sarakstu).

Priekšrocības:

• Efektīva meklēšana, ievietošana un dzēšana (līdzsvarotos kokos).
• Tiek izmantots hierarhisku datu attēlošanai.

PHP piemērs mezgla struktūrai:

<?php

class Node {
    public $data; // Mezglu dati
    public $left; // Kreisais bērns
    public $right; // Labais bērns

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