Найдите минимальную и максимальную высоту двоичного дерева поиска
В последнем вызове мы описали сценарий, в котором дерево может стать неуравновешенным. Чтобы понять концепцию баланса, давайте посмотрим на другое свойство дерева: height. Высота в дереве представляет собой расстояние от корневого узла до любого заданного листового узла. Различные пути в сильно разветвленной структуре дерева могут иметь разную высоту, но для данного дерева будет минимальная и максимальная высота. Если дерево сбалансировано, эти значения будут отличаться не более чем на один. Это означает, что в сбалансированном дереве все листовые узлы существуют на одном уровне, или если они не находятся на одном уровне, они не более одного уровня друг от друга. Свойство баланса важно для деревьев, потому что именно это определяет эффективность древовидных операций. Как мы объяснили в последнем задаче, мы сталкиваемся с худшей временной сложностью для сильно неуравновешенных деревьев. Самобалансирующиеся деревья обычно используются для учета этой проблемы в деревьях с динамическими наборами данных. К общим примерам относятся деревья AVL, красно-черные деревья и B-деревья. Эти деревья содержат дополнительную внутреннюю логику, которая перебалансирует дерево, когда вставки или удаления создают состояние дисбаланса. Примечание. Аналогичным свойством высоты является глубина, которая относится к тому, насколько далеко данный узел находится от корневого узла. Инструкции: Напишите два метода для нашего двоичного дерева: findMinHeight и findMaxHeight . Эти методы должны возвращать целочисленное значение для минимальной и максимальной высоты в заданном двоичном дереве, соответственно. Если узел пуст, назначим ему высоту -1 (это базовый случай). Наконец, добавьте третий метод isBalanced который возвращает true или false зависимости от того, сбалансировано ли дерево или нет. Вы можете использовать первые два метода, которые вы только что написали, чтобы определить это.
Write two methods for our binary tree: findMinHeight and findMaxHeight. These methods should return an integer value for the minimum and maximum height within a given binary tree, respectively. If the node is empty let's assign it a height of -1 (that's the base case). Finally, add a third method isBalanced which returns true or false depending on whether the tree is balanced or not. You can use the first two methods you just wrote to determine this.