Описание тега binary-search-tree
Бинарное дерево поиска - это структура данных, которая состоит из корневого узла с левым и правым дочерними узлами. Левый узел и все его потомки имеют меньшие значения, чем корневой узел, тогда как правый узел и все его потомки имеют большие значения, чем корневой узел. Потомки корневого узла следуют этому же шаблону. Это дает нам дерево, состоящее из упорядоченных элементов.
1
ответ
BST в массиве обхода
У меня есть следующая реализация двоичного дерева в массиве; 32 / \ 2 -5 / \ -331 399 Данные сгруппированы по 3 показателям одновременно. index%3==0 это значение узла, index%3==1 является индексом значения левого узла и index%3==2 это индекс значени…
19 май '13 в 04:30
1
ответ
Алгоритм определения количества узлов с ключом, превышающим целое число K на BST
У меня была следующая проблема в тесте неделю назад. Я не получил свою оценку, но я уверен, что мое решение не полностью охватило все базовые случаи проблемы. Утверждение следующее: Для дерева бинарного поиска напишите алгоритм (используя псевдокод)…
09 ноя '13 в 14:21
3
ответа
Количество двоичных деревьев и BST с узлом n
Если число узлов = n, мы имеем Количество BST = C (n) Число структурно различных бинарных деревьев = C (n) Количество бинарных деревьев = n! * C(n) где C (n) = каталонское число = (2n)! / [ (n+1)! * п! ] Я понимаю #1. Я могу сделать это, используя с…
23 дек '14 в 07:11
1
ответ
Как посчитать неконечные узлы в бинарном дереве поиска?
Я отправляю новый вопрос с моим кодом. Я пытаюсь сосчитать неконечные узлы двоичного дерева поиска. Я создаю не листовой метод, а затем пытаюсь вызвать его в тестовом классе. Кто-нибудь может мне помочь? Вот код: public class BST { private Node<I…
15 фев '14 в 18:45
1
ответ
Двоичное дерево поиска, имеющее проблемы с функцией вставки
Я использую рекурсивные функции для вставки узла в мое двоичное дерево поиска. Программа работает путем создания корневого узла, если его нет. Корень - это указатель на структуру узла. Если корень уже существует, я вызываю рабочую функцию. Примечани…
11 ноя '17 в 12:05
1
ответ
Java Создание бинарного дерева поиска (оно работает, но я знаю, что делаю это неправильно)
Меня попросили создать двоичное дерево поиска с использованием целых чисел, затем строки попросили изменить его, чтобы оно было универсальным и позволяло пользователю выбирать, какое дерево ему нужно. Теперь я изменил свой код узла и дерева, чтобы о…
25 ноя '16 в 01:14
3
ответа
Структура данных с постоянными операциями времени
Мне нужно использовать структуру данных, реализуемую в C++, которая может выполнять основные операции, такие как поиск, вставка и удаление, в постоянное время. Мне, однако, также нужно быть в состоянии найти максимальное значение в постоянное время.…
23 июл '15 в 02:10
3
ответа
Деревья бинарного поиска и данные с Python
У меня есть функция двоичного дерева с 3 кусками данных в каждом узле. Они классифицируются по идентификационным номерам. Они также содержат "Имя" и "Марка" Определенная функция, с которой у меня проблемы - это функция поиска имени, она выглядит так…
10 апр '12 в 21:54
1
ответ
Выполнить поиск двоичных деревьев на основе набора данных
Меня попросили написать код BTS для набора данных с координатами x, y и z, который имеет отрицательное и положительное число, и требования приведены ниже: Эта программа способна выполнять поиск двоичных деревьев на основе набора данных. Пожалуйста, …
28 май '15 в 04:50
0
ответов
Двоичное дерево поиска с методом вставки пары значений ключей
Этот вопрос заключается в том, как правильно создать новый узел для реализации метода вставки? Я использую Eclipse IDE для написания этого кода, но я застрял. public KeyValueDSBinarySearchTree(Class<K> keyType, Class<V> valueType, DSComp…
01 дек '18 в 00:52
1
ответ
Удаление узла только с одним дочерним элементом из дерева двоичного поиска
Это код для удаления узла из дерева двоичного поиска. Мой вопрос: почему мы передаем указатель узла по ссылке на DelSingle функция, но мы только передаем указатель на узел DelDoubleByCopying функционировать? template <class T> bool BST<T>…
24 янв '14 в 21:29
3
ответа
Как вернуть узел, случайным образом, из двоичного дерева поиска?
Учитывая BST (может быть или не быть сбалансированным), как можно вернуть "любой" узел равномерно случайным образом? Ограничение: вы не можете использовать внешнюю структуру данных индексации. Вы должны пройти по дереву таким образом, чтобы каждый у…
19 сен '14 в 20:11
0
ответов
Проблемы с удалением узла бинарного дерева поиска
Я пишу бинарное дерево поиска, и я почти закончил. У меня проблемы с удалением узлов. Каждый узел имеет ссылку на свой левый, правый и родительский узлы (корневому узлу присваивается фиктивный родительский элемент), элемент данных и число целых чисе…
19 апр '13 в 18:36
3
ответа
Стратегия создания BBST, когда мы знаем, что большинство вставок в порядке?
У меня есть ситуация, когда мне нужно сбалансированное бинарное дерево поиска. Я использовал дерево AVL, но оно требует много поворотов для создания высоты баланса при вставке. Я заметил, что большинство входов уже в порядке. Например: 8 9 10 11 12 …
17 фев '14 в 22:18
2
ответа
Невозможно использовать TreeSet's метод has()
У меня есть TreeSet, где элементы являются объектами с двумя атрибутами (имя и возраст). Каждый раз, когда я хочу найти объект с определенным именем, мне приходится прибегать к расширенному циклу for или итератору. Я не могу использовать contains() …
17 дек '16 в 00:49
1
ответ
Сравнения в AVL Tree, состоящие из указателей на объекты
У меня есть дерево AVL, которое использует шаблоны и предполагает, что объекты узла сравнимы, поэтому оно сравнивает их напрямую, а не сравнивает какой-то ключ, связанный с объектами: void insert( const Comparable & x, AvlNode * & t ) { if( …
30 окт '14 в 12:38
1
ответ
Пожалуйста, помогите мне разобраться в этом методе "BinarySearchCountAll" в моей книге
В моей книге " Поваренная книга C# 3.0" О'Рейли есть следующий пример, который меня смущает. (Точная транскрипция ниже.) // Count the number of times an item appears in the sort List<T>. public static int BinarySearchCountAll<T>(this Lis…
28 мар '16 в 00:47
0
ответов
Троичные деревья поиска VS Бинарные деревья поиска
Троичные деревья поиска очень распространены в области редактирования текста. Их можно использовать для реализации функции "Автозаполнение", проверки орфографии, поиска совпадений по частям, поиска по соседству и многих других опций.Причиной их изве…
12 ноя '17 в 21:52
0
ответов
Ошибка: запрос на член 'data' в '* root', который имеет тип указателя 'nodeBST*'
Ошибка: запрос на член 'data' в '* root', который имеет тип указателя 'nodeBST*' Я просто использовал указатель на указатель для разыменования членов данных. Я следую неправильному подходу?? #include<iostream> using namespace std; class nodeBS…
07 июн '17 в 17:21
1
ответ
Что такое амортизируемая сложность в Splay Tree?
Я попытался понять амортизированную сложность и сделал несколько поисков в сети, но пока не смог найти хороший ресурс. Так может ли кто-нибудь объяснить, что такое амортизируемая сложность и как она становится O(lg n) в Splay Tree на одну операцию?
01 ноя '13 в 03:48