Подумайте как можно построить дерево поиска из массива данных
Перейти к содержимому

Подумайте как можно построить дерево поиска из массива данных

Решаем задачи без самобалансирующихся деревьев в Python

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

Что касается Python, то в нём есть почти всё.

  • Динамический массив — встроенный тип list . Он же поддерживает и стековые операции: .append() и .pop() .
  • Хэш-таблица — встроенные типы set и dict , а также неизменяемый брат сета frozenset .
  • Куча — list со специальными операциями вставки и удаления, реализованными в модуле heapq .
  • Двусторонняя очередь — это описанный в модуле collections тип deque .

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

На что способно дерево поиска

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

  • Вставка элемента — стоит
  • Удаление элемента — стоит
  • Поиск элемента — стоит
  • Нахождение минимального и максимального элементов — стоит . При особой необходимости можно помнить указатели на них; тогда потребность в проходе по дереву отпадает и стоимость снижается до
  • Нахождение медианы, да и вообще любой k-й порядковой статистики — стоит При этом придётся в каждом узле дерева помнить размер соответствующего поддерева.
  • Нахождение количества элементов меньше/больше заданного — стоит Для этого тоже необходимо в каждом узле дерева помнить размер соответствующего поддерева.
  • Вставка монотонной последовательности элементов — может стоить амортизированное на каждый! (Знаете ли вы, что в C++ std::set можно наполнить из сортированного массива за ?)

Задача: небоскрёбы

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

Здания описаны как массив кортежей вида (координата левого края здания, координата правого края здания, высота). На выход нужно передать массив кортежей (x, y), описывающих общий силуэт зданий.

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

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

Необходимость быстро брать максимум, конечно, напоминает нам о куче. Но куча не предусматривает удаления произвольного элемента! Например, чтобы удалить элемент кучи с известным индексом в Python за приемлемое время, нужно залезть в нестандартизированные детали реализации модуля heapq (что, конечно, ненадёжно и не рекомендуется):

def heapremove(h, i): h[i] = h[-1] h.pop() if i < len(h): heapq._siftup(h, i) heapq._siftdown(h, 0, i)

Однако, есть возможность сделать надстройку над кучей, позволяющую удалять произвольный элемент за амортизированное . Алгоритм такой:

  1. Храним вместе с кучей множество удалённых элементов.
  2. Если требуется удалить элемент, не являющийся сейчас минимальным в куче, добавляем его в множество удалённых элементов.
  3. Если требуется удалить элемент, являющийся сейчас минимальным, удаляем его стандартным heappop . Если новый минимальным элемент содержится в множестве удалённых элементов, удаляем и его, и так далее.
class HeapWithRemoval(object): def __init__(self): self.heap = [] # Делаем не set, а словарь со счётчиком на случай повторов self.deleted = collections.defaultdict(int) def add(self, value): if self.deleted[value]: self.deleted[value] -= 1 else: heapq.heappush(self.heap, value) def remove(self, value): self.deleted[value] += 1 while self.heap and self.deleted[self.heap[0]]: self.deleted[self.heap[0]] -= 1 heapq.heappop(self.heap) def minimum(self): return self.heap[0] if self.heap else None

Задача: медиана в скользящем окне

Эта задача встречается в разных вариантах. Наиболее общо с учётом специфики Питона можно сформулировать так: на вход алгоритму подаётся итератор неизвестной (и, возможно, неограниченной) длины. Нужно вернуть итератор с медианами по всем окнам заранее заданной ширины .

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

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

Если подумать, элементы, нужные для нахождения медианы, в дереве могут лежать только в трёх местах:

  • в корне;
  • в наименьшем элементе правого поддерева;
  • в наибольшем элементе левого поддерева.

Действительно, давайте хранить две кучи, min-кучу и max-кучу, сбалансированного размера. При этом все элементы max-кучи должны быть меньше всех элементов min-кучи. При добавлении элемента нужно положить его в правильную кучу и сбалансировать их: это потребует конечного числа операций вида «извлеки экстремальное значение из одной кучи и положи в другую», стоящих . Получение медианы стоит , так как для этого нужен только максимум max-кучи и минимум min-кучи.

class MedianFinder(object): def __init__(self, k): self.k = k self.smaller_heap = HeapWithRemoval() self.larger_heap = HeapWithRemoval() # Нам нужно помнить порядок прибытия элементов, чтобы удалять старые: self.elements = deque([], k) def add(self, num): if len(self.elements) == self.k: # Элементов слишком много - время удалить старый из соотв. кучи. element_to_delete = self.elements[0] if self.smaller_heap and element_to_delete = self.larger_heap.minimum(): self.larger_heap.add(num) else: self.smaller_heap.add(-num) self.elements.append(num) self.balance() def balance(self): # Алгоритм построен так, что одна куча не может стать сильно больше другой. if len(self.larger_heap) > len(self.smaller_heap) + 1: num = self.larger_heap.pop() self.smaller_heap.add(-num) elif len(self.smaller_heap) > len(self.larger_heap) + 1: num = -self.smaller_heap.pop() self.larger_heap.add(num) def median(self): if len(self.larger_heap) > len(self.smaller_heap): return self.larger_heap.minimum() if len(self.larger_heap) < len(self.smaller_heap): return -self.smaller_heap.minimum() return (self.larger_heap.minimum() - self.smaller_heap.minimum()) / 2

(Для этого кода я добавил в HeapWithRemoval методы pop ,
__len__ и __nonzero__ .)

Решение задачи с такой структурой данных становится элементарным:

def median_over_sliding_window(input, k): finder = MedianFinder(k) for num in input: finder.add(num) if len(finder.elements) == k: yield finder.median()

Задача: количество инверсий

Дан массив чисел Нужно вычислить количество пар элементов массива, которые стоят в неправильном порядке, то есть при имеет место Если массив состоит из разных чисел от 1 до n, то чётность этого количества есть не что иное, как чётность перестановки, описываемой этим массивом.

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

В обоих случаях она решается за памяти и времени (кроме случая перестановки, в котором она решается за — но это уже совсем другая история). Элементарное решение с деревом выглядит примерно так: идём по массиву, на каждом шаге прибавляем к ответу количество элементов больше текущего (или текущего, умноженного на ) — дерево делает это за — и после этого добавляем в дерево текущий элемент.

Здесь уже одними кучами не обойтись!

Но и без дерева не обойтись тоже. Реализовать дерево несложно; но если его не балансировать, то в худшем случае асимптотика ухудшится до ! Что же делать?

Развернём задачу и пойдём с другого конца. Ведь можно сначала построить всё дерево целиком, на каждом шаге цикла удалять из него текущий элемент и прибавлять к ответу количество элементов меньше текущего. Построить сбалансированное дерево легко — достаточно изначально отсортировать массив и написать грамотную рекурсию:

import collections Node = collections.namedtuple("Node", "value left right") def make_tree(nums): nums = sorted(nums) return _make_tree(nums, 0, len(nums)) def _make_tree(nums, l, r): # На вход получаем отсортированный массив элементов. # Конвертируем в дерево подмассив с индексами в [l, r). if r - l 

А вот удаление из дерева — занятие муторное. Неудачный алгоритм удаления может испортить дерево и снова сделать его неприемлемой высоты! Поэтому давайте будем не удалять узлы из дерева, а лишь помечать их как удалённые. Тогда с высотой дерева за всё время работы алгоритма гарантированно ничего не произойдёт и мы получим вожделенное .

Правда, при таком подходе наличие узлов с повторяющимися элементами (особенно в большом количестве) может сильно испортить жизнь. Поэтому имеет смысл перед построением дерева произвести дедупликацию элементов с подсчётом кратности.

import collections class Node(object): def __init__(self, value, smaller, larger, total_count): self.smaller = smaller # левое поддерево self.larger = larger # правое поддерево self.value = value self.total_count = total_count # общее число узлов в этом поддереве def count_smaller(self, value): if not self.total_count: # Чего тянуть резину? return 0 if value 

Решение задачи, соответственно, снова элементарное:

def count_inversions(nums, coef=1.0): tree = make_tree(nums) result = 0 for num in nums: tree.remove(num) result += tree.count_smaller(num * coef) return result

Бонусная задача: корзина с шарами

Эта задача вообще не требует самобалансирующихся деревьев — привожу её в качестве бонуса, чтобы рассказать ещё чуть-чуть о деревьях в Питоне.

Есть виртуальная корзина с шарами k разных цветов. В корзину можно положить шар определённого цвета, а можно вытащить случайный шар. Задача — программно смоделировать такую корзину с максимально эффективными операциями.

Очевидное решение — операций на добавление шара и на выбор случайного: храним массив с количеством шаров каждого цвета и суммарное количество шаров N, при необходимости выбрать случайный шар генерируем случайное число от 0 до N — 1 и смотрим, куда оно попало. (Например, есть 2 шара нулевого цвета, 1 шар первого цвета и 4 шара второго. Если выпало 0 или 1, выбрался шар нулевого цвета; если 2, то первого цвета; если 3, 4, 5 или 6 — второго цвета.)

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

Поскольку k задано, мы заранее знаем, сколько в дереве будет листьев. Количество узлов тоже не может измениться. Итого мы имеем дерево константного размера; когда мы попробуем этот размер вычислить, мы заметим, что у него есть ещё одно особенное свойство.

Предположим, что мы знаем, сколько нам нужно узлов. Попробуем уложить всё дерево в массив, как это делает Питон в модуле heapq :

У каждого узла есть свой индекс в массиве. У корня этот индекс — 0, у детей узла с индексом i — индексы (2 * i + 1) у левого и (2 * i + 2) у правого; у родителя узла с индексом i индекс (i - 1) // 2 .

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

Но что, если k между двумя степенями двойки? Что ж, мы можем раскрыть несколько бутонов (обязательно с левого края!), чтобы число листьев стало таким, как нам надо:

Заметим, что при этом все листья по-прежнему расположены в памяти подряд! Это полезное свойство очень поможет нам при реализации.

Остаётся лишь вычислить, сколько нужно узлов для дерева с заданным количеством листьев k. Когда k — степень двойки, всё понятно: всего в дереве будет узлов. Удивительно, но и во всех остальных случаях тоже!

Доказательство

Мы ищем дерево минимальной высоты с k листьями и перекосом в сторону левого поддерева, если он необходим (то есть если k — не степень двойки).

Если , такое дерево состоит из одного (листового) узла и для него формула верна.

Если и степень двойки, формула снова верна.

Если и не степень двойки, нужно построить дерево с двумя поддеревьями, удовлетворяющими искомому свойству (и гарантированно непустыми!). Для них формула будет верна; в первом будет листьев, во втором — листьев (), и суммарно имеем число узлов

import random class Bucket(object): def __init__(self, k): self.k = k # Изначально у нас ноль шаров каждого цвета, # и все частичные суммы тоже нули. self.tree = [0] * (2 * k - 1) def add_ball(self, color): # Вычислить индекс в массиве по индексу цвета легко! node_index = self.k - 1 + color while node_index >= 0: # Увеличиваем количество шаров заданного цвета # и суммы во всех предках соответствующего узла. self.tree[node_index] += 1 node_index = (node_index - 1) // 2 def pick_ball(self): total_balls = self.tree[0] ball_index = random.randrange(total_balls) node_index = 0 # Определить, дошли ли мы до листа, легко - # индексы листьев начинаются с (k - 1). while node_index < self.k - 1: self.tree[node_index] -= 1 left_child_index = 2 * node_index + 1 right_child_index = 2 * node_index + 2 if ball_index < self.tree[left_child_index]: node_index = left_child_index else: ball_index -= self.tree[left_child_index] node_index = right_child_index self.tree[node_index] -= 1 return node_index - self.k + 1

P. S.

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

  • python
  • heapq
  • куча
  • двоичные деревья
  • никто не читает теги
  • но они не для чтения
  • а для индексации поиском
  • так что это нормально
  • Ненормальное программирование
  • Python
  • Программирование
  • Алгоритмы

Структуры данных: двоичное дерево в Java

Java-университет

Привет-привет! Сложно быть сильным программистом без базовых знаний. И здесь имеется в виду не только знание синтаксиса родного языка программирования, но и основ и концепций программирования в целом. Одними из таких основ являются алгоритмы и структуры данных. Как правило в данном вопросе кто-то осведомлен больше, кто-то меньше, но есть некоторая база, которую должны знать все. Среди баз для структур данных обязательно стоит разобраться с деревьями двоичного поиска. Структуры данных: двоичное дерево в Java - 1Собственно, сегодня мы рассмотрим саму структуру с её особенностями и узнаем, как можно реализовать двоичное дерево в Java . Для начала давайте же разберемся, что такое двоичное дерево. Двоичное де́рево — структура данных, в которой каждый узел (родительский) имеет не более двух потомков (правый и левый наследник).Структуры данных: двоичное дерево в Java - 2На практике обычно используются два вида двоичных деревьев — двоичное дерево поиска и пирамида (куча). Сегодня мы рассмотрим двоичное дерево поиска.

Преимущества двоичного дерева

  1. Делим справочник на две части, первая — от 1 до 50, вторая 51-100. Мы точно знаем, в которой из этих частей наша страница: если опять же брать 77 страницу — во второй части книги.
  2. Далее рассматриваем вторую часть и делим её на две — от 51 до 75, от 76 до 100. В этом случае наша страница будет опять во второй половине, в промежутке 76-100.
  3. Далее делим и этот промежуток на 2 и получаем 76-88 и 89-100. Страница входит в первый промежуток, поэтому второй отметаем.
  4. Далее промежутки: 76-81 и 82-88, берем первый.
  5. 76-78 и 79-81, берем первый.
  6. 76 и 77-78, берем второй.
  7. 77 и 78, берем первый и получаем нашу страницу — 77.

Правила построения дерева двоичного поиска

Структуры данных: двоичное дерево в Java - 3

Двоичное дерево поиска строится по определенным правилам:

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

К примеру, у нас есть ряд из чисел от 1 до 10. Давайте посмотрим, как будет выглядеть дерево двоичного поиска для этого ряда:Давайте подумаем, соблюдаются ли тут все условия бинарного дерева:

  • все узлы имеют не более двух наследников, первое условие соблюдается;
  • если мы рассмотрим к примеру узел со значением 7(или любой другой), то увидим что все значения элементов в левом поддереве будут меньше, в правом — больше. А это значит, что условия 2 и 3 соблюдены.

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

Поиск элемента

Структуры данных: двоичное дерево в Java - 4

При поиске элемента с заданным значением мы начинаем с корневого элемента:

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

К примеру, в продемонстрированном выше дереве двоичного поиска мы хотим найти элемент со значением 5:

  • сравниваем его с корневым элементом, видим, что корневой больше, поэтому мы переходим к левому потомку, который имеет значение 3;
  • сравниваем искомый и элемент со значением 3, видим, что искомый больше, поэтому нам нужен правый потомок рассматриваемого элемента, а именно — элемент со значением 5;
  • сравниваем этого потомка с искомым и видим, что значения равны — элемент найден.

Вставка элемента

  1. Сравниваем новый с корневым (если его нет — новый элемент и есть корневой).
  2. Если новый элемент:
    • меньше, то переходим к левому наследнику, если его нет, новый элемент и занимает место левого наследника, и алгоритм закончен;
    • больше или равен корневому, то мы переходим к правому наследнику. И аналогично, если данного элемента нет, то новый элемент займет место правого элемента и алгоритм закончен.
  • сравниваем с корневым элементом 7 и видим, что корневой меньше, поэтому переходим к правому наследнику;
  • следующий рассматриваемый элемент имеет значение 9, что меньше чем новый 11, поэтому переходим к правому наследнику;
  • правый наследник имеет значение 10, что опять же меньше, поэтому мы переходим к первому элементу, а так как его нет, то новый элемент со значением 11 и становится на это место.

Структуры данных: двоичное дерево в Java - 5

Удаление элемента

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

  1. Удаляемый узел является листовым (не имеет потомков). Пожалуй, самый простой. Всё сводится к тому, что мы его просто отсекаем от дерева, без лишних манипуляций. К примеру, из нашего дерева мы удаляем узел со значением 8: Структуры данных: двоичное дерево в Java - 7Структуры данных: двоичное дерево в Java - 8
  2. Удаляемый узел имеет одного потомка. В таком случае мы удаляем выбранный узел, и на его место ставим его потомка (по сути просто вырежем выбранный узел из цепочки). В качестве примера удалим из дерева узел со значением 9: Структуры данных: двоичное дерево в Java - 9Структуры данных: двоичное дерево в Java - 10
  3. Удаляемый узел имеет двух потомков. Самая интересная часть. Ведь если удаляемый узел имеет сразу двух потомков, нельзя просто так заменить его одним из этих потомков (особенно если у потомка есть собственные потомки). Пример: в рассматриваемом выше дереве, какой узел должен быть левым потомком узла 3? Если немного задуматься, то станет очевидно, что это должен быть узел со значением 4. Ну а если дерево не будет таким простым? Если оно будет вмещать сотни значений, будет ли так просто понять, кто будет преемником? Понятное дело, что нет. Поэтому тут нужен свой небольшой алгоритм поиска приемника:
    1. Сперва мы должны перейти к правому потомку выбранного узла, значение которого должно быть больше значения узла.
    2. После мы переходим к левому потомку правого потомка (если такой существует), дальше — к левому потомку левого потомка и т. д., следуя вниз по цепи левых потомков.
    3. Соответственно, последний левый потомок на этом пути и будет являться преемником исходного узла.

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

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

    Как будет выглядеть дерево после удаления узла со значением 3:

    Структуры данных: двоичное дерево в Java - 11

А теперь пришло время перейти от практики к теории. Давайте взглянем, каким же образом можно отобразить данную структуру данных в Java. Класс одного узла:

 class Node < private int value; // ключ узла private Node leftChild; // Левый узел потомок private Node rightChild; // Правый узел потомок public void printNode() < // Вывод значения узла в консоль System.out.println(" Выбранный узел имеет значение :" + value); >public int getValue() < return this.value; >public void setValue(final int value) < this.value = value; >public Node getLeftChild() < return this.leftChild; >public void setLeftChild(final Node leftChild) < this.leftChild = leftChild; >public Node getRightChild() < return this.rightChild; >public void setRightChild(final Node rightChild) < this.rightChild = rightChild; >@Override public String toString() < return "Node class Tree < private Node rootNode; // корневой узел public Tree() < // Пустое дерево rootNode = null; >public Node findNodeByValue(int value) < // поиск узла по значению Node currentNode = rootNode; // начинаем поиск с корневого узла while (currentNode.getValue() != value) < // поиск покуда не будет найден элемент или не будут перебраны все if (value < currentNode.getValue()) < // движение влево? currentNode = currentNode.getLeftChild(); >else < //движение вправо currentNode = currentNode.getRightChild(); >if (currentNode == null) < // если потомка нет, return null; // возвращаем null >> return currentNode; // возвращаем найденный элемент > public void insertNode(int value) < // метод вставки нового элемента Node newNode = new Node(); // создание нового узла newNode.setValue(value); // вставка данных if (rootNode == null) < // если корневой узел не существует rootNode = newNode;// то новый элемент и есть корневой узел >else < // корневой узел занят Node currentNode = rootNode; // начинаем с корневого узла Node parentNode; while (true) // мы имеем внутренний выход из цикла < parentNode = currentNode; if(value == currentNode.getValue()) < // если такой элемент в дереве уже есть, не сохраняем его return; // просто выходим из метода >else if (value < currentNode.getValue()) < // движение влево? currentNode = currentNode.getLeftChild(); if (currentNode == null)< // если был достигнут конец цепочки, parentNode.setLeftChild(newNode); // то вставить слева и выйти из методы return; >> else < // Или направо? currentNode = currentNode.getRightChild(); if (currentNode == null) < // если был достигнут конец цепочки, parentNode.setRightChild(newNode); //то вставить справа return; // и выйти >> > > > public boolean deleteNode(int value) // Удаление узла с заданным ключом < Node currentNode = rootNode; Node parentNode = rootNode; boolean isLeftChild = true; while (currentNode.getValue() != value) < // начинаем поиск узла parentNode = currentNode; if (value < currentNode.getValue()) < // Определяем, нужно ли движение влево? isLeftChild = true; currentNode = currentNode.getLeftChild(); >else < // или движение вправо? isLeftChild = false; currentNode = currentNode.getRightChild(); >if (currentNode == null) return false; // yзел не найден > if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) < // узел просто удаляется, если не имеет потомков if (currentNode == rootNode) // если узел - корень, то дерево очищается rootNode = null; else if (isLeftChild) parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя else parentNode.setRightChild(null); >else if (currentNode.getRightChild() == null) < // узел заменяется левым поддеревом, если правого потомка нет if (currentNode == rootNode) rootNode = currentNode.getLeftChild(); else if (isLeftChild) parentNode.setLeftChild(currentNode.getLeftChild()); else parentNode.setRightChild(currentNode.getLeftChild()); >else if (currentNode.getLeftChild() == null) < // узел заменяется правым поддеревом, если левого потомка нет if (currentNode == rootNode) rootNode = currentNode.getRightChild(); else if (isLeftChild) parentNode.setLeftChild(currentNode.getRightChild()); else parentNode.setRightChild(currentNode.getRightChild()); >else < // если есть два потомка, узел заменяется преемником Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла if (currentNode == rootNode) rootNode = heir; else if (isLeftChild) parentNode.setLeftChild(heir); else parentNode.setRightChild(heir); >return true; // элемент успешно удалён > // метод возвращает узел со следующим значением после передаваемого аргументом. // для этого он сначала переходим к правому потомку, а затем // отслеживаем цепочку левых потомков этого узла. private Node receiveHeir(Node node) < Node parentNode = node; Node heirNode = node; Node currentNode = node.getRightChild(); // Переход к правому потомку while (currentNode != null) // Пока остаются левые потомки < parentNode = heirNode;// потомка задаём как текущий узел heirNode = currentNode; currentNode = currentNode.getLeftChild(); // переход к левому потомку >// Если преемник не является if (heirNode != node.getRightChild()) // правым потомком, < // создать связи между узлами parentNode.setLeftChild(heirNode.getRightChild()); heirNode.setRightChild(node.getRightChild()); >return heirNode;// возвращаем приемника > public void printTree() < // метод для вывода дерева в консоль Stack globalStack = new Stack(); // общий стек для значений дерева globalStack.push(rootNode); int gaps = 32; // начальное значение расстояния между элементами boolean isRowEmpty = false; String separator = "-----------------------------------------------------------------"; System.out.println(separator);// черта для указания начала нового дерева while (isRowEmpty == false) < Stack localStack = new Stack(); // локальный стек для задания потомков элемента isRowEmpty = true; for (int j = 0; j < gaps; j++) System.out.print(' '); while (globalStack.isEmpty() == false) < // покуда в общем стеке есть элементы Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека if (temp != null) < System.out.print(temp.getValue()); // выводим его значение в консоли localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего элемента localStack.push(temp.getRightChild()); if (temp.getLeftChild() != null || temp.getRightChild() != null) isRowEmpty = false; >else < System.out.print("__");// - если элемент пустой localStack.push(null); localStack.push(null); >for (int j = 0; j < gaps * 2 - 2; j++) System.out.print(' '); >System.out.println(); gaps /= 2;// при переходе на следующий уровень расстояние между элементами каждый раз уменьшается while (localStack.isEmpty() == false) globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный > System.out.println(separator);// подводим черту > > 

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

 public class Application < public static void main(String[] args) < Tree tree = new Tree(); // вставляем узлы в дерево: tree.insertNode(6); tree.insertNode(8); tree.insertNode(5); tree.insertNode(8); tree.insertNode(2); tree.insertNode(9); tree.insertNode(7); tree.insertNode(4); tree.insertNode(10); tree.insertNode(3); tree.insertNode(1); // отображение дерева: tree.printTree(); // удаляем один узел и выводим оставшееся дерево в консоли tree.deleteNode(5); tree.printTree(); // находим узел по значению и выводим его в консоли Node foundNode = tree.findNodeByValue(7); foundNode.printNode(); >> 

Операции поиска/вставки/удаления в дереве двоичного поиска имеют временную сложность O(log(N)) . Но это в лучшем случае. Вообще, временная сложность операций варьируется от O(log(N)) до O(N) . Это зависит от степени вырожденности дерева.

Что такое вырожденное дерево?

Это дерево, в котором элементы попадали при добавлении в позицию крайнего левого узла (наименьшие число) или крайнего большего узла (наибольшие). Это может случиться, если, например, всё левое дерево пусто на каждом уровне, есть только правые деревья, и в таком случае дерево вырождается в список (идущий вправо). Да, именно так вырожденное дерево фактически становится односвязным списком, в котором каждый элемент знает только о последующем за ним. В таком случае все операции по данной структуре приближаются ко временной сложности O(N) .

В каком случае дерево может стать вырожденным?

Например, если добавлять список отсортированных элементов. Если список отсортирован по возрастанию, то корнем будет первый, соответственно, наименьший. Следующий после него займет позицию правого потомка. А тот, который попадет после, будет больше второго и займет позицию его правого преемника, и так далее… Если же список будет по убыванию, то будет то же самое, но уже с крайними левыми элементами. Чтобы избежать этого, можно после получения ряда элементов попросту их перемешать. Тогда сортированность пропадет, и числа будет более-менее равномерно разбросаны по дереву. Структуры данных: двоичное дерево в Java - 13На этом у меня сегодня всё, спасибо за уделенное внимание!Структуры данных: двоичное дерево в Java - 14

Бинарные деревья поиска и рекурсия – это просто

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

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

image

Рис. 1 Бинарное дерево

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

image

Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.

image

Рис. 3 Сбалансированное бинарное дерево поиска

Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.

image

Рис. 4 Экстремально несбалансированное бинарное дерево поиска

Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).

int factorial(int n) < if(n return n * factorial(n - 1); //рекурсивеый вызов с другим аргументом > // factorial(1): return 1 // factorial(2): return 2 * factorial(1) (return 2 * 1) // factorial(3): return 3 * factorial(2) (return 3 * 2 * 1) // factorial(4): return 4 * factorial(3) (return 4 * 3 * 2 * 1) // Вычисляет факториал числа n (n должно быть небольшим из-за типа int // возвращаемого значения. На практике можно сделать long long и вообще // заменить рекурсию циклом. Если важна скорость рассчетов и не жалко память, то // можно совсем избавиться от функции и использовать массив с предварительно // посчитанными факториалами). void reverseBinary(int n) < if (n == 0) // Базовый случай < return; >cout // Печатает бинарное представление числа в обратном порядке void forvardBinary(int n) < if (n == 0) // Базовый случай < return; >forvardBinary(n/2); //рекурсивеый вызов с другим аргументом cout // Поменяли местами две последние инструкции // Печатает бинарное представление числа в прямом порядке // Функция является примером эмуляции стека void ReverseForvardBinary(int n) < if (n == 0) // Базовый случай < return; >cout // Функция печатает сначала бинарное представление в обратном порядке, // а затем в прямом порядке int product(int x, int y) < if (y == 0) // Базовый случай < return 0; >return (x + product(x, y-1)); //рекурсивеый вызов с другим аргументом > // Функция вычисляет произведение x * y ( складывает x y раз) // Функция абсурдна с точки зрения практики, // приведена для лучшего понимания рекурсии 

Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.

Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).

Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.

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

Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.

DFS применяется в алгоритме нахождения компонентов сильной связности в ориентированном графе. BFS применяется для нахождения кратчайшего пути в графе, в алгоритмах рассылки сообщений по сети, в сборщиках мусора, в программе индексирования – пауке поискового движка. И DFS и BFS применяются в алгоритме поиска минимального покрывающего дерева, при проверке циклов в графе, для проверки двудольности.
Обходу в ширину в графе соответствует обход по уровням бинарного дерева. При данном обходе идет посещение узлов по принципу сверху вниз и слева направо. Обходу в глубину в графе соответствуют три вида обходов бинарного дерева: прямой (pre-order), симметричный (in-order) и обратный (post-order).

Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.

Если нам дано изображение дерева, и нужно найти его обходы, то может помочь следующая техника (см. рис. 5). Обводим дерево огибающей замкнутой кривой (начинаем идти слева вниз и замыкаем справа вверх). Прямому обходу будет соответствовать порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами слева. Для симметричного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами снизу. Для обратного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами справа. В коде рекурсивного вызова прямого обхода идет: вызов, левый, правый. Симметричного – левый, вызов, правый. Обратного – левый правый, вызов.

image

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

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

struct TreeNode < double data; // ключ/данные TreeNode *left; // указатель на левого потомка TreeNode *right; // указатель на правого потомка >; void levelOrderPrint(TreeNode *root) < if (root == NULL) < return; >queue q; // Создаем очередь q.push(root); // Вставляем корень в очередь while (!q.empty() ) // пока очередь не пуста < TreeNode* temp = q.front(); // Берем первый элемент в очереди q.pop(); // Удаляем первый элемент в очереди cout data left != NULL ) q.push(temp->left); // Вставляем в очередь левого потомка if ( temp->right != NULL ) q.push(temp->right); // Вставляем в очередь правого потомка > > void preorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >cout data left); //рекурсивный вызов левого поддерева preorderPrint(root->right); //рекурсивный вызов правого поддерева > // Функция печатает значения бинарного дерева поиска в прямом порядке. // Вместо печати первой инструкцией функции может быть любое действие // с данным узлом void inorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->left); //рекурсивный вызов левого поддерева cout data right); //рекурсивный вызов правого поддерева > // Функция печатает значения бинарного дерева поиска в симметричном порядке. // То есть в отсортированном порядке void postorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->left); //рекурсивный вызов левого поддерева preorderPrint(root->right); //рекурсивный вызов правого поддерева cout data // Функция печатает значения бинарного дерева поиска в обратном порядке. // Не путайте обратный и обратноотсортированный (обратный симметричный). void reverseInorderPrint(TreeNode *root) < if (root == NULL) // Базовый случай < return; >preorderPrint(root->right); //рекурсивный вызов правого поддерева cout data left); //рекурсивный вызов левого поддерева > // Функция печатает значения бинарного дерева поиска в обратном симметричном порядке. // То есть в обратном отсортированном порядке void iterativePreorder(TreeNode *root) < if (root == NULL) < return; >stack s; // Создаем стек s.push(root); // Вставляем корень в стек /* Извлекаем из стека один за другим все элементы. Для каждого извлеченного делаем следующее 1) печатаем его 2) вставляем в стек правого! потомка (Внимание! стек поменяет порядок выполнения на противоположный!) 3) вставляем в стек левого! потомка */ while (s.empty() == false) < // Извлекаем вершину стека и печатаем TreeNode *temp = s.top(); s.pop(); cout data right) s.push(temp->right); // Вставляем в стек правого потомка if (temp->left) s.push(temp->left); // Вставляем в стек левого потомка > > // В симметричном и обратном итеративном обходах просто меняем инструкции // местами по аналогии с рекурсивными функциями. 

Java. Помогите понять задание с бинарным деревом

Не совсем понимаю как построить само дерево. В данной задаче рассматриваются бинарные деревья. На рисунке ниже показан пример бинарного дерева, состоящего из семи узлов. введите сюда описание изображения Двоичное дерево-это либо пустое дерево, либо узел (называемый корнем), содержащий одно целое значение и связанный с двумя другими двоичными деревьями. Нас интересуют пути (последовательности связанных смежных узлов), которые начинаются в корне и следуют за краями дерева (отмечены стрелками на рисунке выше). Например, последовательность узлов A, B, D является допустимым путем, а последовательность a, B, G-нет. Проблема Мы хотим найти максимальное количество различных значений, которые появляются на пути, начиная от корня дерева. Например, на пути, состоящем из узлов A, B, D, G, есть два различных значения (4 и 5). На пути A, C, E есть три различных значения (1, 4 и 6). Не существует пути, содержащего четыре или более различных значений. Написать функцию: решение класса < public int solution (Tree T); >это, учитывая двоичное дерево T, состоящее из N узлов, возвращает максимальное количество различных значений, которые появляются на пути, начинающемся с корня дерева T. например, учитывая дерево, показанное выше, функция должна возвращать 3. Технические подробности Двоичное дерево задается с помощью структуры данных указателя. Предположим, что приведены следующие объявления:

public class Tree

Пустое дерево представлено пустым указателем (обозначается null). Непустое дерево представлено указателем на объект, представляющий его корень. Атрибут x содержит целое число, содержащееся в корне, тогда как атрибуты l и r содержат левое и правое поддеревья двоичного дерева соответственно. Предубеждения Напишите эффективный алгоритм для следующих предположений: * N-целое число в диапазоне [1..50,000]; • высота дерева t (количество ребер на самом длинном пути от корня до листа) находится в диапазоне [0..3,500]; • каждое значение в дереве T является целым числом в диапазоне [1..Северный.] @ИмяФамилия Думал вот таки образом

public void preOrder(Tree tree) < if (tree == null)< return; >//тут делать что нибудь со значением листка preOrder(tree.l); preOrder(tree.r); > > 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *