როგორ მუშაობს ბინარული ხე?

ორმხრივი ხე არის მონაცემთა სტრუქტურა, რომელიც ფორმის ხის სახით არის წარმოდგენილი, სადაც თითოეულ კვანძს აქვს მაქსიმუმ ორი შვილი: მარცხენა და მარჯვენა.

მოქმედების პრინციპები:

• მთავარი: ხის ზედა კვანძი.
• კვანძები: შეიცავს მონაცემებს და მითითებებს შვილკვანძებზე.
• ფოთლები: კვანძები, რომლებსაც არ აქვთ შვილკვანძები.
• კავშირები: მიმართულია მშობელკვანძიდან შვილკვანძებზე.

ძირითადი ოპერაციები:

• შეყვანა: ახალი კვანძები ემატება ხის გარკვეულ ადგილას, შენარჩუნებული მისი სტრუქტურა და წესები (მაგალითად, ორკუთხედის ძიების ხისათვის: ნაკლები მნიშვნელობები მარცხნივ, მეტი — მარჯვნივ).
• ძიება: კვანძების გავლით ძიება კონკრეტული ელემენტის დასაგენერირებლად. ორკუთხედის ძიების ხეში ძიება ეფექტურია მონაცემების წესრიგის გამო.
• წაშლა: კვანძის წაშლა და ხის სტრუქტურის გადახედვა.
• გავლა: ყველა კვანძის ვიზიტი გარკვეულ წესში:
  • წინასწარი (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;
    }
}