Ikki tarmoqli daraxt qanday ishlaydi?

Ikki tarmoqli daraxt — bu daraxt shaklidagi ma'lumotlar tuzilmasi bo'lib, har bir tugun maksimal ravishda ikki bolali tugunga ega: chap va o'ng.

Ishlash prinsiplari:

• O'sha: Daraxtning yuqori tuguni.
• Tugunlar: Ma'lumotlarni va bolalar tugunlariga havolalarni o'z ichiga oladi.
• Yumshoq tugunlar: Bolasiz tugunlar.
• Ulanishlar: ota tugundan bolalar tugunlariga yo'naltirilgan.

Asosiy operatsiyalar:

• Qo'shish: Yangi tugunlar daraxtning ma'lum bir joyiga qo'shiladi, uning tuzilmasi va qoidalarini saqlab qoladi (masalan, ikki tarmoqli qidiruv daraxti uchun: kichik qiymatlar chapga, katta qiymatlar o'ngga).
• Qidiruv: Tugunlar bo'ylab yurish orqali ma'lum bir element topiladi. Ikki tarmoqli qidiruv daraxtida qidiruv ma'lumotlarning tartiblanganligi tufayli samarali.
• O'chirish: Tugunni o'chirish va daraxt tuzilishini qayta qurish.
• Sayohat: Daraxtdagi barcha tugunlarni ma'lum bir tartibda tashrif buyurish:
  • Oldindan (Pre-order): Ota, chap bo'lim, o'ng bo'lim.
  • Orqadan (Post-order): Chap bo'lim, o'ng bo'lim, ota.
  • In-order: Chap bo'lim, ota, o'ng bo'lim (ikki tarmoqli qidiruv daraxti uchun, elementlarning tartiblangan ro'yxatini beradi).

Afzalliklar:

• Samarali qidiruv, qo'shish va o'chirish (balanslangan daraxtlarda).
• Hierarxik ma'lumotlarni ifodalash uchun ishlatiladi.

PHPda tugun tuzilmasining misoli:

<?php

class Node {
    public $data; // Tugunning ma'lumotlari
    public $left; // Chap bolali tugun
    public $right; // O'ng bolali tugun

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