Интервью с PHP: Расскажите мне о бинарном дереве, которое вы понимаете

интервью задняя часть PHP алгоритм

Понимание и реализация деревьев

До сих пор наше исследование структур данных касалось только линейной части. Независимо от того, используем ли мы массивы, связанные списки, стеки или очереди, все они представляют собой линейные структуры данных. Мы видели сложность операций над линейными структурами данных, в большинстве случаев сложность вставки и удаления может быть выражена в O (1). Поиск немного сложен и требует сложности O (n). Единственным исключением являются массивы PHP, которые на самом деле являются хэш-таблицами, которые могут достигать сложности O(1), если индексы или ключи управляются таким образом. Чтобы решить эту проблему, мы можем использовать иерархические структуры данных вместо линейных структур данных. Иерархические данные хорошо подходят для многих задач, которые трудно решить с помощью линейных структур данных.

Всякий раз, когда мы говорим о генеалогических деревьях, организационных структурах и графах сетевых подключений, мы на самом деле говорим об иерархических данных. Дерево — это специальный абстрактный тип данных (ADT). отличается отсвязанный список, дерево иерархическое.

Определение и характеристики деревьев

Дерево — это иерархический набор узлов или вершин, соединенных ребрами. Деревья не могут иметь циклов, и между узлом и его нисходящими узлами или дочерними элементами существуют только ребра. Два дочерних узла одного и того же родителя не могут иметь между собой никакого ребра. У каждого узла может быть родитель, если только он не является верхним узлом, также известным как корневой узел. Каждое дерево может иметь только один корневой узел. Каждый узел может иметь ноль или более дочерних узлов. На приведенной ниже диаграмме A является корневым узлом, а B, C и D — его дочерними элементами. Мы также можем сказать, что A является родительским узлом B, C, D. B, C и D называются братьями и сестрами, потому что они принадлежат одному и тому же родительскому узлу A.

Узел без дочерних элементов называется листом. На предыдущей диаграмме K, L, F, G, M, I и J являются листовыми узлами. Листовые узлы также называются внешними узлами или конечными узлами. Узлы, отличные от корня, имеют по крайней мере один дочерний узел и называются внутренними узлами. Здесь B, C, D, E и H — внутренние узлы. Вот некоторые другие общие термины, используемые для описания структуры данных дерева:

Потомок: это узел, к которому можно получить доступ из родительского узла с помощью повторяющихся процедур. Например, M является потомком C на предыдущем рисунке.

Предок: это узел, который может быть достигнут от дочернего узла к родительскому узлу повторяющимся образом. Например, B является предком L.

Из: общее количество дочерних узлов конкретного родительского узла относится к его степени. В нашем примере А — это 3 степени, В — это степень, С — это 3 степени, D — 2 степени.

Путь: последовательность узлов и ребер от исходного узла к узлу назначения называется путем между двумя узлами. Длина пути — это количество узлов в пути. Путь от А до М равен А-С-Н-М, а длина пути равна 4.

Высота узла: высота узла определяется количеством ребер между узлом и самым глубоким узлом. Например, узел B имеет высоту 2.

Иерархия: Иерархия представляет собой генерацию узлов. Если родительский узел находится на уровне N, его дочерние узлы будут на уровне N+1. Следовательно, иерархия определяется количеством ребер между узлом и корнем.

А находится на 0-м этаже

B, C и D - 1 этаж

E, F, G, H, I, J - 2 слоя

К, Л, М находится на 3 этаже.

Высота дерева: высота дерева определяется высотой его корневого узла. Высота дерева выше равна 3.

Поддерево: в древовидной структуре каждый потомок рекурсивно формирует поддерево. Другими словами, дерево состоит из множества поддеревьев. Например, B и E, K и L образуют поддерево, а E, K и L образуют поддерево, и они идентифицируются в каждом отдельном оттенке.

Глубина: глубина узла определяется количеством ребер между узлом и корневым узлом. Например, глубина H равна 2, а глубина L равна 3.

Лес: Лес — это набор или несколько непересекающихся деревьев.

Обход: представляет собой процесс посещения узлов в определенном порядке.

ключ: используется для поиска, представляющего значение узла.

Реализация дерева с использованием PHP

До сих пор мы видели различные свойства деревьев. Если мы сравним деревья с примерами из реального мира, мы обнаружим, что организационные структуры или генеалогические деревья могут быть представлены числами. Для организационной структуры существует корневой узел, которым может быть генеральный директор компании, за которым следуют сотрудники на уровне CXO, а затем сотрудники на других уровнях. Здесь мы не ограничиваем какую-либо степень конкретного узла. Это означает, что узел может иметь несколько дочерних элементов. Итак, вот структура узла, в которой мы можем определить свойства узла, его родителя и его дочерние элементы:

class TreeNode
{
    public $data = null;

    public $children = [];

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

    public function addChildren(TreeNode $treeNode)
    {
        $this->children[] = $treeNode;
    }
}

Мы видим, что мы объявили два общедоступных свойства как данные и дочерние. У нас также есть метод добавления дочерних элементов к определенному узлу. Здесь мы просто добавляем новые дочерние узлы в конец массива. Деревья — это рекурсивные структуры, которые помогут нам рекурсивно строить деревья и рекурсивно обходить деревья.

Теперь, когда у нас есть узлы, давайте построим древовидную структуру, которая будет определять корневой узел дерева, а также проходить по всему дереву. Итак, базовая древовидная структура будет такой:

class Tree
{
    public $root = null;

    public function __construct(TreeNode $treeNode)
    {
        $this->root = $treeNode;
    }

    public function traverse(TreeNode $treeNode, int $level = 0)
    {
        if ($treeNode) {
            echo str_repeat('-', $level) . $treeNode->data . PHP_EOL;

            foreach ($treeNode->children as $child) {
                $this->traverse($child, $level + 1);
            }
        }
    }
}

В приведенном выше коде показан простой класс дерева, в котором мы можем хранить ссылку на корневой узел, а также перемещаться по дереву из любого узла. В части обхода мы посещаем каждый дочерний узел и сразу же рекурсивно вызываем метод обхода, чтобы получить дочерние элементы текущего узла. Мы передаем уровень и печатаем тире (-) в начале имени узла, чтобы мы могли легко понять дочерние данные.

require './TreeNode.php';

$ceo = new TreeNode('ceo');

$tree = new Tree($ceo);

$cfo = new TreeNode('cfo');
$cto = new TreeNode('cto');
$cmo = new TreeNode('cmo');
$coo = new TreeNode('coo');

$ceo->addChildren($cfo);
$ceo->addChildren($cto);
$ceo->addChildren($cmo);
$ceo->addChildren($coo);

$seniorArchitect = new TreeNode("Senior Architect");
$softwareEngineer = new TreeNode("SoftwareEngineer");

$userInterfaceDesigner = new TreeNode("userInterface Designer");
$qualityAssuranceEngineer = new TreeNode("qualityAssurance Engineer");


$cto->addChildren($seniorArchitect);
$seniorArchitect->addChildren($softwareEngineer);

$cto->addChildren($userInterfaceDesigner);
$cto->addChildren($qualityAssuranceEngineer);

$tree->traverse($tree->root);

Окончательный вывод похож на этот, полный код можно найти вздесьВидеть

разные виды деревьев

В мире кода есть много разных типов деревьев, давайте посмотрим.

бинарное дерево

Бинарное дерево — это базовая древовидная структура, в которой каждый узел бинарного дерева имеет не более двух дочерних элементов.

бинарное дерево поиска

Бинарное дерево поиска (BST) — это особый тип двоичного дерева, в котором узлы хранятся в упорядоченном порядке, т. е. в любой заданной точке значение узла должно быть больше или равно значению левого дочернего элемента и меньше значения правого дочернего элемента. ценность. Каждый узел должен удовлетворять этому свойству, которое является бинарным деревом поиска. Алгоритм бинарного дерева поиска всегда лучше, чем линейный поиск, его временная сложность составляет O(n), мы подробно объясним это позже.

Самобалансирующееся бинарное дерево

Самобалансирующееся бинарное дерево поиска или сбалансированное по высоте бинарное дерево поиска — это особый тип бинарного дерева поиска, который пытается сохранить высоту или уровень дерева как можно меньше за счет автоматической корректировки. В левой части рисунка ниже показано бинарное дерево поиска, а в правой части — самобалансирующееся бинарное дерево поиска:

Хорошо сбалансированное двоичное дерево всегда является лучшим выбором, поскольку оно обеспечивает более быстрые операции поиска, чем обычные BST. Существуют различные реализации самобалансирующихся или хорошо сбалансированных бинарных деревьев поиска. Вот некоторые из них:

  • АА-дерево

  • АВЛ-дерево

  • красно-черное дерево

  • дерево козла отпущения

  • октодерево

  • 2-3 дерева

  • Treap

Мы представим их в последующих материалах, так что следите за обновлениями.

больше контента

Адрес каталога серии тем по базовой структуре данных PHP:github.com/...Он в основном использует синтаксис PHP для обобщения основных структур данных и алгоритмов. Есть также базовые знания, которые легко игнорировать в нашей повседневной разработке PHP, и некоторые практические предложения по спецификации, развертыванию и оптимизации в современной разработке PHP, а также углубленное исследование характеристик языка Javascript.

Категории