Публикации по теме 'binary-search-tree'
Структуры данных: баланс в бинарном дереве поиска
Пока я занимался проблемами структур данных, я наткнулся на проблему, как найти высоту дерева и проверить, является ли дерево сбалансированным. Зачем нужна эта балансировка? Что мы понимаем под балансом?
Во-первых, многие структуры данных имеют инвариант баланса. В зависимости от структуры данных достижение баланса будет достигаться разными средствами. Рассмотрим перекошенное двоичное дерево поиска, в котором все узлы (кроме листьев) имеют только правый дочерний элемент, а левый..
Двоичные представления дерева поиска в JavaScript
Отображение разных представлений бинарного дерева поиска — частый вопрос, который задают во многих интервью, даже самых крупных!
Независимо от того, является ли это JavaScript или нет, вы должны быть в состоянии взломать логику. Но давайте немного конкретнее и посмотрим, как вы можете решить эту проблему в JavaScript. Прежде чем определить верхнее, нижнее, левое и правое представление бинарного поиска — нам нужно построить дерево.
Давайте начнем с построения бинарного дерева поиска..
Вопросы по теме 'binary-search-tree'
Реализация часового пояса Rails BST
Кто-нибудь знает, как я могу использовать BST для config.time_zone в моем файле rails config/environment.rb?
На данный момент я оставил его как UTC и думаю добавить BST в список поддерживаемых часовых поясов, а затем расширить класс Time, чтобы...
3314 просмотров
schedule
25.02.2023
Оптимальная структура данных на диске для поиска файла?
Я потратил пару часов на чтение сообщений, связанных с вопросом, пытаясь найти решение, но мне не удалось его найти.
Итак, вот: меня однажды спросили в интервью, какую структуру данных я бы использовал для поиска, если бы определенное слово...
1873 просмотров
schedule
04.10.2022
BST с рекурсией и заданными структурами
Мне нужно закодировать некоторые методы для BST, и у меня есть некоторые проблемы, позвольте мне объяснить.
У меня есть следующие структуры:
struct node {
struct node *lChild;
struct node *rChild;
int value;
};
а также...
373 просмотров
schedule
16.04.2023
Случайное двоичное дерево поиска
у меня есть BST, где я вставляю ключи от 1 до n случайным образом (каждая перестановка выполняется с вероятностью 1/n!) . мой вопрос: почему результирующие деревья не равномерны , даже если перестановка однородна ?
947 просмотров
schedule
20.04.2023
Проблема с двоичным деревом поиска
Почему поиск и преемник и предшественник возвращают -1?
// BST.cpp : main project file.
#include "stdafx.h"
#include <cstdlib>
#include <iostream>
#define SIZE 10
using namespace std;
struct Node {...
3171 просмотров
schedule
29.05.2024
Пересечение двух бинарных деревьев поиска
Привет, Итак, я хочу создать новое дерево, которое в основном представляет собой пересечение (математическое определение пересечения) двух заданных бинарных деревьев поиска. У меня есть метод, который распечатывает все узлы на определенном уровне...
6455 просмотров
schedule
30.10.2023
ошибка компиляции при возврате указателя
У меня есть класс BST такой же, как в эта тема
BST.hpp
template<class T>
class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
T data;
tree_node( const T & thedata,...
175 просмотров
schedule
07.04.2022
Определение степени ленивой оценки
Дано
data BTree a = End
| Node a (BTree a) (BTree a)
deriving(Show,Eq,Ord)
data Msg = Msg { from :: String
, to :: String
, when :: Int
, message :: String }
instance Ord Msg where...
116 просмотров
schedule
04.01.2023
Повторяющиеся записи в двоичном дереве поиска
У меня очень простой вопрос относительно BST. Я видел несколько определений BST, касающихся повторяющихся записей. Некоторые определяют BST как не допускающие дублирования записей, другие определяют, что левый дочерний элемент узла ‹= значению узла,...
2745 просмотров
schedule
25.02.2022
Как найти максимальное значение в любом диапазоне массива за время log (n)?
Например. Массив: {1, 5, 2, 3, 2, 10}
Диапазон: 0-1 Ответ: 5 Диапазон: 2-4 Ответ: 3 Диапазон: 0-5 Ответ: 10 и т. Д.
5944 просмотров
schedule
22.04.2024
MIPS — реализация бинарного дерева поиска
В качестве нашего временного проекта мы реализуем бинарное дерево поиска. За этим стоит следующая мысль:
Предположим, что bst с 3 узлами:
10
/ \
/ \
8 14
Его адресное представление выглядит следующим образом (значение, адрес...
9658 просмотров
schedule
22.06.2023
стандартный мл сделать бст из списка
Я хочу сделать стандартную функцию ml, которая берет список и функцию и делает из нее BST. Тип функции: 'a list -> ('a * 'a -> bool) -> 'a tree , но у меня с ней проблемы, вот код, который я написал:
datatype 'data tree =
EMPTY
|...
2027 просмотров
schedule
19.05.2023
Проблема с двоичным деревом поиска
Я действительно застрял, я получаю сообщение об ошибке "CTree.add(num);" говоря, что «CTree» не объявлен, что не имеет смысла, потому что я инициализировал его в tree.h?
Программа должна предлагать пользователю, пользователь вводит команду...
357 просмотров
schedule
24.07.2022
Первый общий предок бинарного дерева
Если у меня есть бинарное дерево поиска, подобное этому, то какой самый низкий общий предок узлов 6 и 1?
1983 просмотров
schedule
28.08.2022
Как выполнить обход BST по порядку без рекурсии или стека, но с использованием родительских указателей?
Можно ли выполнить итеративный обход по порядку на BST, узел которого имеет родительский указатель (родитель корня — null ) без использования флага visited или stack ?
Я гуглил и не нашел ответа. Дело в том, как я могу знать - в определенном...
18150 просмотров
schedule
17.03.2024
Храните самые большие 5000 номеров из потока номеров
Учитывая следующую проблему:
"Сохранение 5000 самых больших номеров из потока номеров"
Решение, которое приходит на ум, — это двоичное дерево поиска, поддерживающее подсчет количества узлов в дереве и ссылку на наименьший узел, когда...
4130 просмотров
schedule
23.03.2024
удаление листьев не влияет на BST - C
Я написал функцию для обнуления всех листьев BST. Конечно, BST имеет левый и правый указатель и символ, называемый данными, для хранения значения узла.
void removeLeaves(struct Tree* T){
if(T->left == NULL && T->right == NULL){...
147 просмотров
schedule
13.11.2023
Создание нового экземпляра класса с использованием шаблона, не знаю, как обрабатывать ошибку
Я постараюсь сделать код коротким.
Я пытаюсь создать B инарный S поиск T (сокращенно BST), используя шаблоны.
В моей функции добавления я получаю сообщение об ошибке, и я уверен, что каким-то образом неправильно использую шаблоны.
Весь...
1358 просмотров
schedule
15.05.2024
Как работает этот алгоритм удаления узла BST?
Я пытаюсь следовать алгоритму BST в «Структуры данных и алгоритмы» Гранвилла Барнетта , но я не понимаю описанный ниже алгоритм удаления узла.
Раздел 3.3 (стр. 22)
Удалить узел из BST довольно просто, нужно рассмотреть четыре случая:...
3491 просмотров
schedule
23.08.2022
Что такое средняя высота журнала n?
Я узнал, что высота деревьев Random-BST/Red-Black и некоторых других деревьев равна O(log n) .
Я удивляюсь, как это может быть. Допустим, у меня есть такое дерево
Высота дерева по сути является глубиной дерева, которая в данном случае...
1696 просмотров
schedule
03.05.2022