Спор с педагогом, рассудите "Двоичное дерево поиска"

@LamerDegedrol · Регистрация: 23.01.2015

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

Двоичное дерево поиска
Спор у нас на том, что:
Если значение одинаково в дереве, то оно исчезает, или же идёт в правую сторону

утверждение 1
Left < X < Right
то есть, влево если меньше
вправо если больше
Вообще не рассматриваем если оно одинаково

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

Кликните здесь для просмотра всего текста

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

утверждение 2
Left < X <= Right
то есть, влево если меньше
вправо если больше, либо РАВНО.

Обосновывая на том что.
1) Как то неправильно вычёркивать вводные данные
2) Везде куда не тыкни пишется что право больше или равно, вики, иные учебники.
3) Дерево выглядеть может много иначе
4) Да, я знаю что поиск ломается, и должен быть как либо переделан, но сам факт.
Может кто грамотный, или у кого иные учебники,

Это так же изменяет и реализацию кода как вы понимаете.

@TheCalligrapher · 22.11.2019, 01:33

Сообщение от LamerDegedrol

Если значение одинаково в дереве, то оно исчезает, или же идёт в правую сторону

Можно и так, и так. Оно может идти и в левую сторону. Как сделаете, так и будет.

Сообщение от LamerDegedrol

Дерево двоичного поиска - это бинарное дерево, узлы которого помечены элементами множества.

Совсем не обязательно. Дерево представляет упорядоченную последовательность. Все. А уж на этом вы можете строить множество, мультимножество или еще что угодно.

Сообщение от LamerDegedrol

1) Как то неправильно вычёркивать вводные данные

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

Ваш спор бессмыслен.

IGPIGP · 22.11.2019, 02:21

LamerDegedrol, время изменяет подходы. Я помню, когда BST выделяли из двоичных деревьев именно строгостью неравенств справа и слева от узла. То есть повторов не допускалось и поиск строго детерминирован в результате. Количество найденных элементов или ноль или один. Сейчас можно встретить и деревья с повторами, которые причисляются к BST. Поэтому спор неразрешим.

Сообщение от LamerDegedrol

Обосновывая на том что.
1) Как то неправильно вычёркивать вводные данные

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

@Undisputed · 22.11.2019, 09:53

TheCalligrapher,
Думаю вариант счётчик "одинаковых" может принести проблемы. В дереве объекты могут сортироваться по конкретному полю которое не единственное. То есть кроме поля по которому идёт сортировка все другие поля хранимого обьекта могут иметь разное значение и эти значения тоже могут быть важны при обработке элементов дерева. Например может понадобится получить диапазон "одинаковых" элементов из дерева, а потом пройтись по их полям, которые не входят в процесс сортировки и что-то сделать с этими данными. Если будет счётчик, то обьект в дереве будет только один

@oleg-m1973 · 22.11.2019, 10:28

Сообщение от LamerDegedrol

Спор у нас на том, что:
Если значение одинаково в дереве, то оно исчезает, или же идёт в правую сторону

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

IGPIGP · 22.11.2019, 10:39

Сообщение от oleg-m1973

Для последного случая я бы сделал список коллизий, наподобите того, как это делается в хэш-таблице

В двоичном дереве они получаются естественным образом, но могут быть имплементированы по разному. У меня была идея расширить двоичное дерево с повторами до троичного. Это кажется дороговато (1 "лишний" указатель) но за то, для, как вы правильно заметили, равномерно распределённых деревьев меньше балансировок. Третий указатель - для эквивалентных и у тех кто уникален указывает на ноль)

@oleg-m1973 · 22.11.2019, 10:47

Сообщение от IGPIGP

В двоичном дереве они получаются естественным образом, но могут быть имплементированы по разному. У меня была идея расширить двоичное дерево с повторами до троичного. Это кажется дороговато (1 "лишний" указатель) но за то, для, как вы правильно заметили, равномерно распределённых деревьев меньше балансировок. Третий указатель - для эквивалентных и у тех кто уникален указывает на ноль)

Естественным образом - они ухудшают характеристики.
Я и говорил о этом самом "троичном" - тут, как обычно, выбираешь - либо экономишь на памяти, либо на производительности.

IGPIGP · 22.11.2019, 11:41

Сообщение от oleg-m1973

Естественным образом - они ухудшают характеристики.
Я и говорил о этом самом "троичном" - тут, как обычно, выбираешь - либо экономишь на памяти, либо на производительности.

Ну да. Согласен. Третий указатель и скорость слегка подъест. Его проверять постоянно при итерациях нужно. Вот тут в блоге, в диалоге с Avazart, в самом конце я как раз о таком 3-дереве фантазировал:
https://www.cyberforum.ru/blog... g4772.html

Новичок · 22.11.2019, 13:21

Есть std::set, есть std::multiset, есть std::map. Т.е это все детали реализации и спор ни о чем.

IGPIGP · 22.11.2019, 13:31

Сообщение от Новичок

Т.е это все детали реализации и спор ни о чем.

Это утверждение имеет сомодавлеющий смысл. Для вас этот спор не о чём, - точно. А для меня в нём есть смысл. Разрешающая способность предиката это компромисс между скоростью и вероятностью получения повторов. Причём, иногда она может занижена из-за разгильдяйства, а иногда из-за недостаточной изученности логического смысла свойств объектов в разрабатываемом алгоритме, типа: - расставим по росту а там видно будет. Всё это чревато затратами в обработке ветвей. С другой стороны, некоторые объекты идентифицировать/сравнивать настолько дорого, что от сравнений вообще отказываются в пользу хеширования.
Смысл разговоров о сравнении в том, чтобы сравнить разные методы сравнения. Сравнение это инструмент познания (всё познаётся в сравнении), но при не желании сравнивать (мыслить/познавать) в споре ни какой истины породить нельзя.

@LamerDegedrol · 22.11.2019, 15:47 **[ТС]**

Если мы к примеру построим физическую модель дерева двоичного поиска с "Одинаковым значением" создавая элемент Узла, то будет 2 решения.

1) Мы вкладываем элемент внутрь совпадения (счётчик) - ни каких проблем с иными функциями.

2) Мы переносим его правее элемента - Но если число будет находится Ниже? возможно ли это? Не логическая ли это ошибка?
и тут есть проблема с иными функциями.
А так же у элемента не может быть лева. В прочем причина этого будет назову это "Свойство числа", и если брать не целые числа, но проблемы нет.

Вот пример рисунка 1 и 2 решения дерева.
Вот 2 жизнеспособно или ошибочно

@oleg-m1973 · 22.11.2019, 15:53

Сообщение от LamerDegedrol

Вот пример рисунка 1 и 2 решения дерева.
Вот 2 жизнеспособно или ошибочно

Ты не забывай, что здесь будет ещё балансировка дерева. Так, что второй вариант вряд ли получится.

@LamerDegedrol · 22.11.2019, 16:00 **[ТС]**

Педагог просто утверждает на основании формулировки:

Дерево двоичного поиска - это бинарное дерево, узлы которого помечены элементами множества.

то есть

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

поэтому если я сортирую как либо одинаковые, а не игнорирую их, так как "они не существуют во множестве" я неправ.

с другой стороны эта формулировка взята отсюда

Кликните здесь для просмотра всего текста

Структуры данных и алгоритмы
Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман

Звучит она так:

Кликните здесь для просмотра всего текста

Начнем с деревьев двоичного поиска — основной структуры данных для представления множеств, чьи элементы упорядочены посредством некоторого отношения линейного порядка, которые, как обычно, обозначим символом "<". Эти структуры особенно полезны, когда исходное множество такое большое, что не рационально использовать его элементы непосредственно в качестве индексов массивов. Предполагается, что все элементы множеств являются элементами некоторого универсального множества — универсума, примером которого служит множество возможных идентификаторов в программе на языке Pascal. На деревьях двоичного поиска можно реализовать операторы INSERT, DELETE, MEMBER и MIN, причем время их выполнения в среднем имеет порядок O(logn) для множеств, состоящих из п элементов.
Дерево двоичного поиска — это двоичное дерево, узлы которого помечены элементами множеств (мы также будем говорить, что узлы дерева содержат или хранят элементы множества). Определяющее свойство дерева двоичного поиска заключается в том, что все элементы, хранящиеся в узлах левого поддерева любого узла ж, меньше элемента, содержащегося в узле х, а все элементы, хранящиеся в узлах правого поддерева узла х, больше элемента, содержащегося в узле х. Это свойство называется характеристическим свойством дерева двоичного поиска и выполняется для любого узла дерева двоичного поиска, включая его корень.

@oleg-m1973 · 22.11.2019, 16:05

Сообщение от LamerDegedrol

поэтому если я сортирую как либо одинаковые, а не игнорирую их, так как "они не существуют во множестве" я неправ.

Дерево двоичного поиска, оно прежде всего сбалансированное, т.е. слева и справа находится примерно одинаковое кол-во элементов, иначе поиск по нему не будет бинарным.

@LamerDegedrol · 22.11.2019, 16:09 **[ТС]**

Сообщение от oleg-m1973

Ты не забывай, что здесь будет ещё балансировка дерева. Так, что второй вариант вряд ли получится.

Если его строить по алгоритмическому утверждению
key[left[X]] < key[X] ≤ key[right[X]]

Если
Лево меньше текущего
лево пусто заполнить, иначе сначала
Право больше или равно текущему идти вправо
Если пусто заполнить, иначе сначала

тогда оно строится в таком виде как на 2 и 3 изображении

Добавлено через 3 минуты

Сообщение от oleg-m1973

Дерево двоичного поиска, оно прежде всего сбалансированное, т.е. слева и справа находится примерно одинаковое кол-во элементов, иначе поиск по нему не будет бинарным.

примерно одинаковое?
Оно не идеально сбалансированное,

Если первый узел будет 1, а последующие 2 3 4 5, то они уйдут все вправо, но оно будет всё равно же двоичным.
да и пример даже в самой вики ни как не похож на Индеальносбалансированный

IGPIGP · 22.11.2019, 16:09

Сообщение от LamerDegedrol

Педагог просто утверждает на основании формулировки:

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

@oleg-m1973 · 22.11.2019, 16:09

Сообщение от LamerDegedrol

тогда оно строится в таком виде как на 2 и 3 изображении

После балансировки у тебя на втором рисунке корнем станет 10, а на третьем - 2-я пятёрка

@LamerDegedrol · 22.11.2019, 16:15 **[ТС]**

А, ты про сбалансированное по высоте.
хм...

Добавлено через 2 минуты

Сообщение от oleg-m1973

После балансировки у тебя на втором рисунке корнем станет 10, а на третьем - 2-я пятёрка

А вот про это мне не говорили...

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

Добавлено через 1 минуту

Сообщение от IGPIGP

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

А когда это стало иначе? нет статейки)
хм, ну в пример приведён учебник 2000 года... хм.

Добавлено через 1 минуту

Сообщение от oleg-m1973

После балансировки у тебя на втором рисунке корнем станет 10, а на третьем - 2-я пятёрка

Прочёл, неа, По высоте балансировать не обязательно

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска
то есть в случае ты подразумеваешь такую модификацию, а не иначе.

@oleg-m1973 · 22.11.2019, 16:35

Сообщение от LamerDegedrol

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

Несбалансированное дерево ты можешь строить как угодно, хоть в виде списка. Только для поиска от него будет мало толку.

@LamerDegedrol · 22.11.2019, 16:40 **[ТС]**

Сообщение от oleg-m1973

Несбалансированное дерево ты можешь строить как угодно, хоть в виде списка. Только для поиска от него будет мало толку.

Ясн дело,
Сбалансировать я могу его и получить рисунок 2.
а до баланса будет рисунок 3.

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

У нас точно Двоичного поичка и Бинарного поиска одно и тоже? В том плане что читаю eu, там всегда Бинарный.
У нас же, То бинарный, то двоичный, Мать вашу же.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	Установка Emscripten SDK (emsdk) и CMake на Windows для сборки C и C++ приложений в WebAssembly (Wasm) 8Observer8 30.01.2026 Чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. Система контроля версиями Git. . .	Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .

@Undisputed 901 / 478 / 93 Регистрация: 10.06.2014 Сообщений: 2,700
	22.11.2019, 09:53
	TheCalligrapher, Думаю вариант счётчик "одинаковых" может принести проблемы. В дереве объекты могут сортироваться по конкретному полю которое не единственное. То есть кроме поля по которому идёт сортировка все другие поля хранимого обьекта могут иметь разное значение и эти значения тоже могут быть важны при обработке элементов дерева. Например может понадобится получить диапазон "одинаковых" элементов из дерева, а потом пройтись по их полям, которые не входят в процесс сортировки и что-то сделать с этими данными. Если будет счётчик, то обьект в дереве будет только один 0

Новичок 1682 / 1098 / 489 Регистрация: 17.07.2012 Сообщений: 5,360
	22.11.2019, 13:21
	Есть std::set, есть std::multiset, есть std::map. Т.е это все детали реализации и спор ни о чем. 0

@LamerDegedrol 1 / 1 / 1 Регистрация: 23.01.2015 Сообщений: 94
	22.11.2019, 15:47 [ТС]
	Если мы к примеру построим физическую модель дерева двоичного поиска с "Одинаковым значением" создавая элемент Узла, то будет 2 решения. 1) Мы вкладываем элемент внутрь совпадения (счётчик) - ни каких проблем с иными функциями. 2) Мы переносим его правее элемента - Но если число будет находится Ниже? возможно ли это? Не логическая ли это ошибка? и тут есть проблема с иными функциями. А так же у элемента не может быть лева. В прочем причина этого будет назову это "Свойство числа", и если брать не целые числа, но проблемы нет. Вот пример рисунка 1 и 2 решения дерева. Вот 2 жизнеспособно или ошибочно Миниатюры 0