Java максимальная глубина несбалансированного бинарного дерева

Русские Блоги

104. Самая большая глубина бинарного дерева создает полное двоичное дерево и самую большую глубину Java

1) Может ли массив может построить только полное двоичное дерево? Можете ли вы использовать , чтобы построить ненадолго бинарное дерево

Часть кода 104. Самая большая глубина бинарного дерева

import java.util.ArrayList; import java.util.List; public class BinTree < private int array[] = ; private static List nodeLIst = new ArrayList(); private static class Node < Node left; Node right; int data; Node(int data) < this.data = data; >> public void createBintree() < for (int i = 0; i < array.length; i++) < nodeLIst.add(new Node(array[i])); >if (nodeLIst.size() > 0) < for (int y = 0; y < array.length / 2 - 1; y++) < //leftChild if (null != nodeLIst.get(2 * y + 1)) < nodeLIst.get(y).left = nodeLIst.get(2 * y + 1); >//rightChild if (null != nodeLIst.get(2 * y + 2)) < nodeLIst.get(y).right = nodeLIst.get(2 * y + 2); >> // Последний родительский узел не имеет детей int lastParentIndex = array.length / 2 - 1; // Левый ребенок nodeLIst.get(lastParentIndex).left = nodeLIst .get(lastParentIndex * 2 + 1); // нечетное время имеет правильный ребенок if (array.length % 2 == 1) < nodeLIst.get(lastParentIndex).right = nodeLIst .get(lastParentIndex * 2 + 2); >> > /** * Предисловие прохождения * * @param node */ /* public static void preOrderTraver(Node node) < if (null != node) < System.out.println("node:" + node.data); preOrderTraver(node.leftChild); preOrderTraver(node.rightChidl); >else < return; >>*/ public static void main(String[] args) < BinTree tree = new BinTree(); tree.createBintree(); System.out.println(maxDepth(nodeLIst.get(0))); //preOrderTraver(nodeLIst.get(0)); >static int maxDepth(Node node) < if(node==null)< return 0; >else if(node.left==null&& node.right==null) < return 1; >else< int left=maxDepth(node.left); int right= maxDepth(node.right); return (left>right? left+1:right+1); > > > 

Интеллектуальная рекомендация

Фабричный метод режим

Значимость режима фабрики метода заключается в определении заводского интерфейса, который создает объект продукта, и задержать фактическую работу создания на подкласс. Основная категория фабрики больш.

Эта функция указателя/постоянной, нормальный объект

Этот указатель представляет Переменные элемента объекта в классе и функции элемента хранятся отдельно. Sizeof (пустой класс) = 1. Кроме того, вопрос о выравнивании байта участвует в примере. INT также.

JavaScript садоводство

Тип преобразования JavaScript этоСлабый типЯзык, так будетЛюбыеГде возможноТип преобразования。 Советы ES5:С0Числовые литералы в начале будут интерпретироваться как восьмеричные цифры. В строгом режиме.

Чтение заметок «Microsoft Sql server 2008 Internals» — глава 6 «Индексы и управление» (1)

Директория индекса «Microsoft Sql server 2008 Internals»: «Microsoft Sql server 2008 Internals», читающий указатель к каталогу заметок В пятой главе я в основном изучал внутрен.

Источник

Как определить, сбалансировано ли двоичное дерево в Java

Узнайте, как определить, сбалансировано ли двоичное дерево в Java.

1. Обзор

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

2. Определения

Во-первых, давайте введем несколько определений, чтобы убедиться, что мы находимся на той же странице:

• Двоичное дерево – своего рода дерево, где каждый узел имеет ноль, один или два ребенка
• Высота дерева – максимальное расстояние от корня до листа (так же, как глубина самого глубокого листа)
• Сбалансированное дерево – это своего рода дерево, на котором для каждого подтрибного максимальное расстояние от корня до любого листа не более чем на один больше, чем минимальное расстояние от корня до любого листа

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

3. Объекты домена

Итак, давайте начнем с класса для нашего дерева:

Ради простоты, скажем так, каждый узел имеет более интегративное значение . Обратите внимание, что если левые и правые деревья нулевой, то это означает, что наш узел .

Прежде чем мы введем наш основной метод давайте посмотрим, что он должен вернуться:

Таким образом, для каждого вызова, мы будем иметь информацию о высоте и балансе.

4. Алгоритм

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

Теперь наш рекурсивный метод будет вызываться для каждого узла. Кроме того, он будет отслеживать текущую глубину. Каждый звонок будет возвращать информацию о высоте и балансе.

Теперь давайте посмотрим на наш метод глубины-первых:

private Result isBalancedRecursive(Tree tree, int depth) < if (tree == null) < return new Result(true, -1); >Result leftSubtreeResult = isBalancedRecursive(tree.left(), depth + 1); Result rightSubtreeResult = isBalancedRecursive(tree.right(), depth + 1); boolean isBalanced = Math.abs(leftSubtreeResult.height — rightSubtreeResult.height)

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

Затем, мы делаем два рекурсивных звонка для левого и правого подтри, сохраняя глубину в курсе .

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

• isBalanced переменная проверяет высоту для детей, и
• substreesAreBalanced указывает, если подтрири оба сбалансированы, а также

Наконец, мы можем вернуть информацию о балансе и высоте. Это также может быть хорошей идеей, чтобы упростить первый рекурсивный вызов с методом фасада:

public boolean isBalanced(Tree tree)

5. Резюме

В этой статье мы обсудили, как определить, сбалансировано ли двоичное дерево. Мы объяснили подход к поиску в первую очередь.

Как обычно, исходный код с тестами доступен более на GitHub .

Читайте ещё по теме:

Источник

Максимальная глубина бинарного дерева

Возвращает ограничение по времени. Интересно, знаю, почему это происходит, что не так с моим кодом?

2 ответа

Ты действительно близко. Я думаю, что вы стремились к этому:

int maxHeight(TreeNode p) < if (p == null) return 0; int leftHeight = maxHeight(p.left); int rightHeight = maxHeight(p.right); return (leftHeight >rightHeight) ? leftHeight + 1 : rightHeight + 1; > 

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

Трудно представить, что вы столкнетесь с проблемой большинства бинарных деревьев, если только:

• это действительно большое (и / или вырожденное) двоичное дерево; или же
• он не структурирован правильно (например, имеет круговую петлю в структуре); или же
• ваш лимит времени очень маленький.

Так что это будет первое, что я проверю.

Однако в вашем случае это возможно потому, что вы вызываете функцию рекурсивно гораздо чаще, чем вам нужно.

Имея два вызова функции глубины в вашем коде для каждого поддерева (один для сравнения глубин и один для возврата самого глубокого поддерева), вы значительно увеличиваете рабочую нагрузку. Было бы лучше кэшировать длины, чтобы вы могли их повторно использовать, что-то вроде (псевдокод):

def maxDepth(nd): if nd == null: # Empty-sub-tree depth is zero. return 0 deepest = maxdepth(nd.left) # Initially assume left is deepest. dright = maxdepth(nd.right) # Or use right if deeper. if dright > deepest: deepest = dright return 1 + deepest # Depth: this node plus deepest sub-tree. 

Источник

Максимальная глубина бинарного дерева

Он возвращает превышение лимита времени. Интересно, знаю, почему это происходит, что не так с моим кодом?

Используя основную теорему и предполагая, что дерево сбалансировано, время работы составляет Omega(n^1.58) , но вы можете достичь O(n) (если я не пропустил какую-то другую ошибку)

2 ответа

Вы действительно близки. Я думаю, вы стремились к этому:

int maxHeight(TreeNode p) < if (p == null) return 0; int leftHeight = maxHeight(p.left); int rightHeight = maxHeight(p.right); return (leftHeight >rightHeight) ? leftHeight + 1 : rightHeight + 1; > 

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

Большое спасибо! Теперь я знаю, что использовал рекурсию больше раз. Я должен использовать его дважды каждый раз!

Трудно представить, что у вас возникнут проблемы с большинством бинарных деревьев, если только:

• это очень большое (и/или вырожденное) бинарное дерево; или
• он неправильно структурирован (например, в структуре есть круговая петля); или
• ваш лимит времени очень мал.

Так что это были бы первые вещи, которые я бы проверил.

Однако в вашем случае это, возможно, потому, что вы вызываете функцию рекурсивно гораздо чаще, чем вам нужно.

Имея в своем коде два вызова функции depth для каждого поддерева (один для сравнения глубины и один для возврата самого глубокого поддерева), вы значительно увеличиваете рабочую нагрузку. Было бы лучше кэшировать длины, чтобы вы могли их повторно использовать, что-то вроде (псевдокод):

def maxDepth(nd): if nd == null: # Empty-sub-tree depth is zero. return 0 deepest = maxdepth(nd.left) # Initially assume left is deepest. dright = maxdepth(nd.right) # Or use right if deeper. if dright > deepest: deepest = dright return 1 + deepest # Depth: this node plus deepest sub-tree. 

@wadda_wadda, это не совпадение. Если вы держитесь подальше от более эзотерических частей Python, это идеальный язык для обучения и псевдокодирования. Прелесть в том, что вы часто можете тестировать свой псевдокод и на реальной системе 🙂

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

Источник

Русские Блоги

Учитывая бинарное дерево, найдите его максимальную глубину.

Глубина двоичного дерева — это число узлов на самом длинном пути от корневого узла до самого дальнего конечного узла.

Объяснение: Конечный узел относится к узлу, у которого нет дочерних узлов.

Рекурсивно найти дерево с самой высокой высотой среди левого и правого поддеревьев

class Solution  public int maxDepth(TreeNode root)  if(root == null)  return 0; > return 1+Math.max(maxDepth(root.right),maxDepth(root.left)); > > 

Сложность по времени: мы посещаем каждый узел только один раз, поэтому сложность по времени составляет O (N), где N — количество узлов.

Сложность пространства: в худшем случае дерево является полностью несбалансированным, например, у каждого узла есть только оставленные дочерние узлы, и рекурсия будет вызываться N раз (высота дерева), поэтому сохраняется стек вызовов Это будет O (N). Но в лучшем случае (дерево полностью сбалансировано), высота дерева будет log (N). Следовательно, сложность пространства в этом случае будет O (log (N)).

Второй leecode использует очередь, чтобы сделать

class Solution  public int maxDepth(TreeNode root)  QueuePairTreeNode, Integer>> stack = new LinkedList>(); if (root != null)  stack.add(new Pair(root, 1)); > int depth = 0; while (!stack.isEmpty())  PairTreeNode, Integer> current = stack.poll(); root = current.getKey(); int current_depth = current.getValue(); if (root != null)  depth = Math.max(depth, current_depth); stack.add(new Pair(root.left, current_depth + 1)); stack.add(new Pair(root.right, current_depth + 1)); > > return depth; > > 

Пространственная сложность: O (N).

Источник