Особенность структуры двоичного дерева даёт хороший прирост к эффективности при поиске нужного значения. Для этого нужно, чтобы двоичное дерево было сбалансированным. То есть необходимо построить дерево так, чтобы общее количество узлов в левом и правом поддеревьях было примерно одинаковым для любого узла дерева.
src/Node.php
Реализуйте метод isBalanced()
, который проверяет дерево на сбалансированность. Он возвращает true
, если количество узлов в левом и правом поддеревьях каждого узла отличается не более, чем на 2. В ином случае метод должен вернуть false
.
Сбалансированное дерево
Несбалансированное дерево
В узле 5
количество узлов в левом поддереве равно 4, а в правом — 1. Разница составляет 3. Это больше, чем максимально допустимая разница по условию задачи (2).
Примеры
<?php
use App\Node;
$tree1 = new Node(
4,
new Node(
3,
new Node(2)
)
);
$tree1->isBalanced(); // true
$tree2 = new Node(
4,
new Node(
3,
new Node(
2,
new Node(1)
)
)
);
$tree2->isBalanced(); // false
Для полного доступа к испытанию нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.