Jak działa drzewo binarne?

Drzewo binarne to struktura danych w kształcie drzewa, w której każdy węzeł ma nie więcej niż dwa węzły potomne: lewy i prawy.

Zasady działania:

• Korzeń: Górny węzeł drzewa.
• Węzły: Zawierają dane i odwołania do węzłów potomnych.
• Liście: Węzły bez węzłów potomnych.
• Połączenia: skierowane od węzła rodzica do potomnych.

Główne operacje:

• Wstawianie: Nowe węzły są dodawane w określonym miejscu w drzewie, zachowując jego strukturę i zasady (np. dla drzewa binarnego wyszukiwania: mniejsze wartości po lewej, większe po prawej).
• Wyszukiwanie: Przeglądanie węzłów w celu znalezienia konkretnego elementu. W drzewie binarnym wyszukiwania wyszukiwanie jest efektywne dzięki uporządkowaniu danych.
• Usuwanie: Usunięcie węzła z przebudową struktury drzewa.
• Przeglądanie: Odwiedzanie wszystkich węzłów drzewa w określonym porządku:
  • Pre-order: Korzeń, poddrzewo lewe, poddrzewo prawe.
  • Post-order: Poddrzewo lewe, poddrzewo prawe, korzeń.
  • In-order: Poddrzewo lewe, korzeń, poddrzewo prawe (daje posortowaną listę elementów).

Zalety:

• Efektywne wyszukiwanie, wstawianie i usuwanie (w zrównoważonych drzewach).
• Służy do reprezentowania danych hierarchicznych.

Przykład struktury węzła w PHP:

<?php

class Node {
    public $data; // Dane węzła
    public $left; // Węzeł lewy
    public $right; // Węzeł prawy

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