Сбалансированное бинарное дерево java

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Урок 4. Структуры данных дерево и хэш-таблица

ShumAhd/Lesson-4.-Data-structures-tree-and-hash-table

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Алгоритмы и структуры данных (лекции)

Урок 4. Структуры данных дерево и хэш-таблица

1. Хэш-таблица. Внутреннее устройство. Оценка сложности поиска.
2. Дерево. Особенности структуры. Сбалансированные деревья. Оценка сложности поиска.
3. Алгоритм обхода (поиска) по дереву сбалансированному и несбалансированному

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

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

Код бинарного дерева Binary.java == null

Бинарным деревом называют частный случай дерева, где все элементы обязательно строго уникальны, каждый родитель имеет не более 2 детей, при этом левый ребенок всегда меньше родителя, а правый – больше. Благодаря своим свойствам, бинарные деревья позволяют эффективно выстраивать поисковые алгоритмы. Находясь на любом из узлов мы всегда точно знаем куда именно нам нужно пойти – налево или направо – чтобы найти искомый элемент. Алгоритм обхода бинарного дерева происходит в глубину и очень напоминает алгоритм бинарного поиска

Код сбалансированного дерева Balanced.java == null

Сбалансированным деревом называют частный случай бинарного дерева, у которого выполняется следующее требование: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Таким образом, сбалансированное дерево дает нам идеальную структуру для бинарного поиска – корень такого дерева — это его центральный элемент – количество элементов справа и слева от него различается не более чем на единицу, что характерно для выбора стартовой позиции в бинарном поиске. Таким образом, сложность поиска по сбалансированному дереву составляет O(log n), что дает очень высокую производительность. Для поддержания свойства сбалансированности в процессе операций добавления или удаления элементов такие деревья должны проводить операции балансировки, чтобы не допустить разбалансированности и ухудшения сложности поиска. Существуют различные типы сбалансированных деревьев – АВЛ-дерево, красно-черное дерево, 2-3 дерево и т.д. Каждое из которых имеет собственные алгоритмы балансировки. Так, например, для балансировки АВЛ-дерева каждая нода помимо информации о значении и детях, так же хранит показатель глубины, на основе которого проводится балансировка по специальному алгоритму. А у красно-черного дерева вместо показателя глубины используется показатель цвета – ноды могут быть либо черными, либо красными. Использование сбалансированных деревьев позволяет создать динамическую самоддерживаемую структуру, имеющую очень высокую скорость поиска элементов.

Код не рисует дерево в терминале, это к сожалению очень нетривиальная задача, по этому при запуске кода ни чего не произойдёт ))

Источник

Как определить, сбалансировано ли двоичное дерево в 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 .

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

Источник

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

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

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

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

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

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

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

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

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

 public class Tree    private int value;   private Tree left;   private Tree right;    public Tree(int value, Tree left, Tree right)    this.value = value;   this.left = left;   this.right = right;   >   > 

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

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

 private class Result    private boolean isBalanced;   private int height;    private Result(boolean isBalanced, int height)    this.isBalanced = isBalanced;   this.height = height;   >   > 

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

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;   boolean subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced;   int height = Math.max(leftSubtreeResult.height, rightSubtreeResult.height) + 1;    return new Result(isBalanced && subtreesAreBalanced, height);   > 

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

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

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

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

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

 public boolean isBalanced(Tree tree)    return isBalancedRecursive(tree, -1).isBalanced;   > 

5. Резюме​

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

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

Источник