Икмдүү дарак кандай иштейт?

Икки тараптуу дарак — бул дарак формасындагы маалымат структурасы, анда ар бир түйүндө эң көп эки балдар түйүнү болот: сол жана оң.

Иштөө принциптери:

• Тамыр: Дарактын жогорку түйүнү.
• Түйүндөр: Маалыматтарды камтыйт жана балдар түйүндөрүнө шилтемелерди камтыйт.
• Жапайылар: Балдар түйүндөрү жок түйүндөр.
• Байланыштар: Ата түйүндөн балдар түйүндөрүнө багытталган.

Негизги операциялар:

• Кошуу: Жаңы түйүндөр дарактын белгилүү бир жерине кошулат, анын структурасы жана эрежелери сакталат (мисалы, эки тараптуу издөө дарагында: кичүү маанилер сол жакка, чоңу оң жакка).
• Издөө: Түйүндөр аркылуу өтүү белгилүү бир элементти табуу үчүн. Эки тараптуу издөө дарагында издөө эффективдүү, маалыматтардын тартиби менен.
• Өчүрүү: Түйүндү өчүрүү жана дарактын структурасын кайра түзүү.
• Өткөрүү: Дарактын бардык түйүндөрүнө белгилүү бир тартипте барыш:
  • Алдын ала (Pre-order): Тамыр, сол алдындагы дарак, оң алдындагы дарак.
  • Пост-тартип (Post-order): Сол алдындагы дарак, оң алдындагы дарак, тамыр.
  • Ичке-тартип (In-order): Сол алдындагы дарак, тамыр, оң алдындагы дарак (эки тараптуу издөө дарагында, элементтердин сорттолгон тизмегин берет).

Артыкчылыктары:

• Эффективдүү издөө, кошуу жана өчүрүү (балансалган дарактарда).
• Иерархиялык маалыматтарды көрсөтүү үчүн колдонулат.

PHPда түйүн структурасынын мисалы:

<?php

class Node {
    public $data; // Түйүндүн маалыматтары
    public $left; // Сол балдар
    public $right; // Оң балдар

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