Обсуждение:Двоичное дерево поиска

Слева мало, справа много.

Признать статью законченной 77.94.34.155 12:35, 2 января 2008 (UTC)Григорий

Почему „TRAVERSE“? В английской Википедии обход называется traversal (en:Binary_search_tree#Traversal). — Artem M. Pelenitsyn 06:12, 1 апреля 2009 (UTC).

Множество или мультимножество?

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

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

Иными словами key[left[X]] < key[X] < key[right[X]], что противоречит дальнейшим утверждениям. В частности на таком дереве нельзя реализовать мультимножества.

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

alvelcom 15:42, 20 сентября 2011 (UTC)

Приведенное определение не единственное. Иногда, например, не требуют строгого выполнения одного или обоих неравенств. Но даже с текущим опредением можно реализовывать мультимножества - достаточно лишь добавить счетчик или связный список элементов к каждой вершине. -- X7q 21:36, 20 сентября 2011 (UTC)

операция сравнения

"Очевидно, данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше" - отношение будет, вероятно, корректней K-payl 13:01, 13 марта 2013 (UTC)

У некоторых авторов узлы левого поддерева строго Anatkriz 19:38, 17 мая 2013 (UTC)меньше, а правого - строго больше. Anatkriz 19:38, 17 мая 2013 (UTC)

ошибка в операции удаления

В результате описанного алгоритма получится, что данные узла 5 будет правее данных узла 6. Правильно было бы от узла 8 дойти до конца дерева по левой ветке (т.е. while(m->left) m = m->left;) и найденный крайний узел переместить на место удалённого узла 'n' (т.е. скопировать данные в 'n' и удалить тот крайний узел, удаление там простое).

GrayFace 22:46, 27 ноября 2013 (UTC)

В описании поворота что-то неправильно.

Смотрите, L<a, b>a, C<b, R>b.

При этом же нет гарантии, что C>a. Я предположу, что нужно "попытаться" пристыковать C к a, и если всё получилось, то и хорошо. Если нет -- то нужно пройти по L (как-то), пытаясь пристыковать C к элементам L. Lockywolf (обс.) 15:23, 8 мая 2017 (UTC)

• По условию всё, что справа от узла, больше этого узла. С находится справа от а, поэтому С>a. — Алексей Копылов 22:23, 8 мая 2017 (UTC)

Сложность в О-символике

В карточке указано, что сложность вставки/удаления в двоичное дерево это $O(\log n)$ "в среднем". А разве высота случайного двоичного дерева это не что-то порядка $O({\sqrt {n}})$? adamant.pwn — contrib/talk 11:42, 1 марта 2020 (UTC)

• Не знаю про высоту. Но высота - это максимальная глубина, а время вставки/удаления - это средняя глубина, а она вроде O(log n). — Алексей Копылов 19:44, 1 марта 2020 (UTC)

Сообщение об ошибке

Перенесено со страницы ВП:Сообщения об ошибках#Двоичное дерево поиска.

К обсуждению

(у всех узлов левого поддерева произвольного узла X значения ключей данных меньше либо равны, нежели значение ключа данных самого узла X;) (Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.) Несоответсвие информации в первых двух перечислениях

Автор сообщения: 185.190.40.181 09:32, 27 марта 2023 (UTC)

• Из нескольких разных описаний предмета статьи можно предположить, что жёсткого определения просто нет, термины "меньше", "равно", "больше" устанавливаются для всего дерева пользователем, варианты различны. Требуется всю статью переработать и дать необходимые ссылки на источники, а не на единственный источник в целом. — Egor (обс.) 09:24, 16 сентября 2023 (UTC)