Php: Сбалансированное двоичное дерево

PHP: Введение в ООП 5 сообщений
Обновлено: 08 сент., 18:07
68
Студентов
89%
Завершения

Особенность структуры двоичного дерева даёт хороший прирост к эффективности при поиске нужного значения. Для этого нужно, чтобы двоичное дерево было сбалансированным. То есть необходимо построить дерево так, чтобы общее количество узлов в левом и правом поддеревьях было примерно одинаковым для любого узла дерева.

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

Для полного доступа к испытанию нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов