В чем разница между бинарным поиском и поиском через дерево?

Бинарный поиск vs поиск через дерево

Бинарный поиск — это алгоритм поиска в отсортированном массиве. Поиск через дерево — это поиск в структуре данных дерево (BST).

Бинарный поиск

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = intval(($left + $right) / 2);
        
        if ($arr[$mid] === $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    return -1;  // Не найдено
}

$sorted_array = [1, 3, 5, 7, 9, 11, 15];
binarySearch($sorted_array, 7);  // O(log n)

Требование: массив должен быть отсортирован! Сложность: O(log n) — очень быстро

Поиск в Binary Search Tree

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

function searchBST($node, $target) {
    if ($node === null) {
        return false;
    }
    
    if ($node->value === $target) {
        return true;
    } elseif ($node->value < $target) {
        return searchBST($node->right, $target);
    } else {
        return searchBST($node->left, $target);
    }
}

// Tree structure:
//       5
//      / \
//     3   7
//    / \ / \
//   1  4 6  9

$root = new TreeNode(5);
$root->left = new TreeNode(3);
$root->right = new TreeNode(7);
searchBST($root, 4);  // true

Требование: значения слева < родитель < значения справа Сложность: O(log n) в среднем, O(n) в худшем (вырождение)

Сравнение

Когда использовать

Бинарный поиск:

• Статические данные (не часто меняются)
• Большой отсортированный массив
• Нужен быстрый поиск

BST:

• Данные часто меняются (добавление/удаление)
• Нужен sorted порядок
• Нужна балансировка (AVL, Red-Black дерево)

Практический пример

// Используем бинарный поиск
$user_ids = [1, 5, 10, 15, 20, 25, 30];  // Отсортирован
$found_id = binarySearch($user_ids, 15);  // O(log n)

// Используем BST для частых изменений
class UserTree {
    private $root;
    
    public function insert($id) {
        $this->root = $this->insertNode($this->root, $id);
    }
    
    public function search($id) {
        return searchBST($this->root, $id);
    }
    
    private function insertNode($node, $value) {
        if ($node === null) {
            return new TreeNode($value);
        }
        if ($value < $node->value) {
            $node->left = $this->insertNode($node->left, $value);
        } elseif ($value > $node->value) {
            $node->right = $this->insertNode($node->right, $value);
        }
        return $node;
    }
}

Вывод

Бинарный поиск лучше для статических отсортированных данных. BST лучше для динамических данных с частыми изменениями. Оба имеют O(log n) для поиска, но разные требования к структуре и операциям.