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

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

  • автор:

Бинарное дерево на основе массива

Author24 — интернет-сервис помощи студентам

Всем привет. Начал изучать бинарное дерево на основе массива, нужна подсказка, я правильно начал делать? Или лучше использовать классы? И кто-нибудь может показать, для примера, как написать функцию добавления элемента. Поискал в интернете, но на основе массива толком ничего нет. Заранее спасибо!

1 2 3 4 5 6 7 8 9 10 11 12 13
#include using namespace std; const int MaxLength = 100; //Описание структуры struct Node { int Values[MaxLength]; int father; int left; int right; int free; // Индекс свободного списка Node() { father = left = right = free = 0; }; };

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при.

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

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

Бинарное дерево с использованием статического массива
Помогите пожалуйста с программой. Мне дали вот такое задание: Cпроектировать структуру типа.

Форумчанин

Эксперт CЭксперт С++

8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453

Бинарное дерево — структура данных с самоадресацией, массив ограничивает количество элементов, так что с помощью него никто Бин.дерево не реализовывает, это изврат.

Комп_Оратор)

Эксперт по математике/физике

8945 / 4699 / 629
Регистрация: 04.12.2011
Сообщений: 13,999
Записей в блоге: 16

ЦитатаСообщение от Aidar Посмотреть сообщение

ачал изучать бинарное дерево на основе массива

Aidar, ссылку дайте. Бывают разреженные массивы и хеш-таблицы не основе BST но не наоборот.
Хотя массив бинарных деревьев указателей на бинарные деревья создать можно.

Регистрация: 21.09.2015
Сообщений: 51
MrGluck, преподавателю также сказать?
Форумчанин

Эксперт CЭксперт С++

8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453

ЦитатаСообщение от Aidar Посмотреть сообщение

MrGluck, преподавателю также сказать?
Можете сказать. Только прикрепите это реализацией на структурах с указателями.
Регистрация: 21.09.2015
Сообщений: 51

IGPIGP, вот, что я имел виду(задание): реализовать все типовые операции над двоичным деревом поиска на базе одномерного массива.

Добавлено через 6 минут
MrGluck, а если не пройдет, вы поможете?

Добавлено через 5 минут
MrGluck, а если использовать динамический массив, допустим, вектор, это тоже изврат?

Комп_Оратор)

Эксперт по математике/физике

8945 / 4699 / 629
Регистрация: 04.12.2011
Сообщений: 13,999
Записей в блоге: 16

ЦитатаСообщение от Aidar Посмотреть сообщение

IGPIGP, вот, что я имел виду(задание): реализовать все типовые операции над двоичным деревом поиска на базе одномерного массива.

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

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); > > 

Обход дерева — PHP: Деревья

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

В данном курсе используется один порядок обхода — обход в глубину, так как он естественным образом получается при рекурсивном обходе. Об остальных способах можно прочитать на википедии либо в рекомендуемых Хекслетом книгах.

Обход в глубину (Depth-first search)

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

Рассмотрим данный алгоритм на примере следующего дерева:

// * A // / | \ // * B C * D // /| |\ // E F G J 

Каждая нелистовая вершина обозначена звездочкой. Обход начинается с корневого узла.

  1. Проверяем, есть ли у вершины A дети. Если есть, то запускаем обход рекурсивно для каждого ребенка независимо;
  2. Внутри первого рекурсивного вызова оказывается следующее поддерево:
// * B // /| // E F 

Повторяем логику первого шага. Проваливаемся на уровень ниже.

  1. Внутри оказывается листовой элемент E . Функция убеждается, что у узла нет дочерних элементов, выполняет необходимую работу и возвращает результат наверх
  2. Снова оказываемся в ситуации:
// * B // /| // E F 

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

 $tree = mkdir('/', [ mkdir('etc', [ mkfile('bashrc'), mkfile('consul.cfg'), ]), mkfile('hexletrc'), mkdir('bin', [ mkfile('ls'), mkfile('cat'), ]), ]); function dfs($tree)  // Распечатываем содержимое узла echo getName($tree) . "\n"; // Если это файл, то возвращаем управление if (isFile($tree))  return; > // Получаем детей $children = getChildren($tree); // Применяем функцию dfs ко всем дочерним элементам // Множество рекурсивных вызовов в рамках одного вызова функции // называется древовидной рекурсией array_map(fn($child) => dfs($child), $children); > dfs($tree); // => / // => etc // => bashrc // => consul.cfg // => hexletrc // => bin // => ls // => cat 

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

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

 function changeOwner($tree, $owner)  $name = getName($tree); $newMeta = getMeta($tree); $newMeta['owner'] = $owner; if (isFile($tree))  // Возвращаем обновленный файл return mkfile($name, $newMeta); > $children = getChildren($tree); // Ключевая строчка // Вызываем рекурсивное обновление каждого ребенка $newChildren = array_map(function ($child) use ($owner)  return changeOwner($child, $owner); >, $children); // Создаем директорию $newTree = mkdir($name, $newChildren, $newMeta); // Возвращаем обновленную директорию return $newTree; > // Эту функцию можно обобщить до map (отображения) работающего с деревьями 

Открыть доступ

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

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов

Наши выпускники работают в компаниях:

Дерево поиска, наивная реализация

Бинарное дерево поиска (англ. binary search tree, BST) — структура данных для работы с упорядоченными множествами.

Бинарное дерево поиска обладает следующим свойством: если [math]x[/math] — узел бинарного дерева с ключом [math]k[/math] , то все узлы в левом поддереве должны иметь ключи, меньшие [math]k[/math] , а в правом поддереве большие [math]k[/math] .

Операции в бинарном дереве поиска

Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:

struct Node: T key // ключ узла Node left // указатель на левого потомка Node right // указатель на правого потомка Node parent // указатель на предка 

Обход дерева поиска

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:

  • [math]\mathrm[/math] — обход узлов в отсортированном порядке,
  • [math]\mathrm[/math] — обход узлов в порядке: вершина, левое поддерево, правое поддерево,
  • [math]\mathrm[/math] — обход узлов в порядке: левое поддерево, правое поддерево, вершина.
func inorderTraversal(x : Node): if x != null inorderTraversal(x.left) print x.key inorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 3 4 6 7 8 10 13 14.

func preorderTraversal(x : Node) if x != null print x.key preorderTraversal(x.left) preorderTraversal(x.right)

При выполнении данного обхода вершины будут выведены в следующем порядке: 8 3 1 6 4 7 10 14 13.

func postorderTraversal(x : Node) if x != null postorderTraversal(x.left) postorderTraversal(x.right) print x.key

При выполнении данного обхода вершины будут выведены в следующем порядке: 1 4 7 6 3 13 14 10 8.

Данные алгоритмы выполняют обход за время [math]O(n)[/math] , поскольку процедура вызывается ровно два раза для каждого узла дерева.

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

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

Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы [math]O(h)[/math] , где [math]h[/math] — высота дерева.

Node search(x : Node, k : T): if x == null or k == x.key return x if k < x.key return search(x.left, k) else return search(x.right, k)

Поиск минимума и максимума

Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям [math]left[/math] от корня дерева, пока не встретится значение [math]null[/math] . Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.

Node minimum(x : Node): if x.left == null return x return minimum(x.left)
Node maximum(x : Node): if x.right == null return x return maximum(x.right)

Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время [math]O(h)[/math] .

Поиск следующего и предыдущего элемента

Реализация с использованием информации о родителе

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

Node next(x : Node): if x.right != null return minimum(x.right) y = x.parent while y != null and x == y.right x = y y = y.parent return y
Node prev(x : Node): if x.left != null return maximum(x.left) y = x.parent while y != null and x == y.left x = y y = y.parent return y

Обе операции выполняются за время [math]O(h)[/math] .

Реализация без использования информации о родителе

Рассмотрим поиск следующего элемента для некоторого ключа [math]x[/math] . Поиск будем начинать с корня дерева, храня текущий узел [math]current[/math] и узел [math]successor[/math] , последний посещенный узел, ключ которого больше [math]x[/math] .
Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла [math]current[/math] . Если [math]current.key \leqslant x[/math] , значит следующий за [math]x[/math] узел находится в правом поддереве (в левом поддереве все ключи меньше [math]current.key[/math] ). Если же [math]x \lt current.key[/math] , то [math]x \lt next(x) \leqslant current.key[/math] , поэтому [math]current[/math] может быть следующим для ключа [math]x[/math] , либо следующий узел содержится в левом поддереве [math]current[/math] . Перейдем к нужному поддереву и повторим те же самые действия.
Аналогично реализуется операция поиска предыдущего элемента.

Node next(x : T): Node current = root, successor = null // root — корень дерева while current != null if current.key > x successor = current current = current.left else current = current.right return successor

Вставка

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

Реализация с использованием информации о родителе
func insert(x : Node, z : Node): // x — корень поддерева, z — вставляемый элемент while x != null if z.key > x.key if x.right != null x = x.right else z.parent = x x.right = z break else if z.key < x.key if x.left != null x = x.left else z.parent = x x.left = z break 
Реализация без использования информации о родителе
Node insert(x : Node, z : T): // x — корень поддерева, z — вставляемый ключ if x == null return Node(z) // подвесим Node с key = z else if z < x.key x.left = insert(x.left, z) else if z > x.key x.right = insert(x.right, z) return x

Время работы алгоритма для обеих реализаций — [math]O(h)[/math] .

Удаление

Нерекурсивная реализация

Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на [math]null[/math] . Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева. Время работы алгоритма — [math]O(h)[/math] .

Случай Иллюстрация
Удаление листа Bst del1.png
Удаление узла с одним дочерним узлом Bst del2.png
Удаление узла с двумя дочерними узлами Bst del3.png
func delete(t : Node, v : Node): // [math]t[/math] — дерево, [math]v[/math] — удаляемый элемент p = v.parent // предок удаляемого элемента if v.left == null and v.right == null // первый случай: удаляемый элемент - лист if p.left == v p.left = null if p.right == v p.right = null else if v.left == null or v.right == null // второй случай: удаляемый элемент имеет одного потомка if v.left == null if p.left == v p.left = v.right else p.right = v.right v.right.parent = p else if p.left == v p.left = v.left else p.right = v.left v.left.parent = p else // третий случай: удаляемый элемент имеет двух потомков successor = next(v, t) v.key = successor.key if successor.parent.left == successor successor.parent.left = successor.right if successor.right != null successor.right.parent = successor.parent else successor.parent.right = successor.right if successor.right != null successor.right.parent = successor.parent
Рекурсивная реализация

При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить этот минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма — [math]O(h)[/math] . Рекурсивная функция, возвращающая дерево с удаленным элементом [math]z[/math] :

Node delete(root : Node, z : T): // корень поддерева, удаляемый ключ if root == null return root if z < root.key root.left = delete(root.left, z) else if z > root.key root.right = delete(root.right, z) else if root.left != null and root.right != null root.key = minimum(root.right).key root.right = delete(root.right, root.key) else if root.left != null root = root.left else if root.right != null root = root.right else root = null return root

Задачи о бинарном дереве поиска

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

Задача:
Определить, является ли заданное двоичное дерево деревом поиска.

Пример дерева, для которого недостаточно проверки лишь его соседних вершин

Для того чтобы решить эту задачу, применим обход в глубину. Запустим от корня рекурсивную логическую функцию, которая выведет [math]\mathtt[/math] , если дерево является BST и [math]\mathtt[/math] в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение [math]\mathtt[/math] . Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение [math]\mathtt[/math] .

Функция принимает на вход исследуемую вершину, а также два значения: [math]\mathtt[/math] и [math]\mathtt[/math] , которые до вызова функции равнялись [math] \infty [/math] и [math] -\infty [/math] соответственно, где [math] \infty [/math] — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся. Например, в этом дереве вершина с номером [math]8[/math] находится левее вершины, в которой лежит [math]5[/math] , чего не должно быть в дереве поиска, однако после проверки функция бы вернула [math]\mathtt[/math] .

bool isBinarySearchTree(root: Node): // Здесь root — корень заданного двоичного дерева. bool check(v : Node, min: T, max: T): // min и max — минимально и максимально допустимые значения в вершинах поддерева. if v == null return true if v.key or max return false return check(v.left, min, v.key) and check(v.right, v.key, max) return check(root, [math] -\infty [/math], [math] \infty [/math])

Время работы алгоритма — [math]O(n)[/math] , где [math]n[/math] — количество вершин в дереве.

Задачи на поиск максимального BST в заданном двоичном дереве

Задача:
Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.

Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за [math]O(n^2)[/math] . Но её можно решить за [math]O(n)[/math] , идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:

  • Значение в вершине больше максимума в её левом поддереве;
  • Значение в вершине меньше минимума в её правом поддереве;
  • Левое и правое поддерево являются деревьями поиска.

Введём [math]\mathtt[/math] и [math]\mathtt[/math] , которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины [math]\mathtt[/math] между этими значениями [math]\mathtt[/math] и [math]\mathtt[/math] . Если вершина является листом, она автоматически становится деревом поиска, а её ключ — минимумом или максимумом для её родителя (в зависимости от расположения вершины). Функция [math]\mathtt[/math] записывает в [math]\mathtt[/math] количество вершин в дереве, если оно является деревом поиска или [math]\mathtt[/math] в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением [math]\mathtt[/math] .

int count(root: Node): // root — корень заданного двоичного дерева. int cnt(v: Node): if v == null v.kol = 0 return = 0 if cnt(v.left) != -1 and cnt(v.right) != -1 if v.left == null and v.right == null v.min = v.key v.max = v.key v.kol = 1 return 1 if v.left == null if v.right.max > v.key v.min = v.key v.kol = cnt(v.right) + 1 return v.kol if v.right == null if v.left.min < v.key v.max = v.key v.kol = cnt(v.left) + 1 return v.kol if v.left.min < v.key and v.right.max > v.key v.min = v.left.min v.max = v.right.max v.kol = v.left.kol + v.right.kol + 1 v.kol = cnt(v.left) + cnt(v.right) + 1 return v.kol return -1 return cnt(root)

Алгоритм работает за [math]O(n)[/math] , так как мы прошлись по дереву два раза за время, равное количеству вершин.

Восстановление дерева по результату обхода preorderTraversal

Задача:
Восстановить дерево по последовательности, выведенной после выполнения процедуры [math]\mathrm[/math] .

Восстановление дерева поиска по последовательности ключей

Как мы помним, процедура [math]\mathrm[/math] выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.

Процедура восстановления дерева работает за [math]O(n)[/math] .

Разберём алгоритм на примере последовательности [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] [math]\mathtt[/math] .

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

См. также

  • Поисковые структуры данных
  • Рандомизированное бинарное дерево поиска
  • Красно-черное дерево
  • АВЛ-дерево

Источники информации

  • Википедия — Двоичное дерево поиска
  • Wikipedia — Binary search tree
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

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

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