Обсуждение:Двоичное дерево поиска
Слева мало, справа много.
Признать статью законченной 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)
Сложность в О-символике
[править код]В карточке указано, что сложность вставки/удаления в двоичное дерево это "в среднем". А разве высота случайного двоичного дерева это не что-то порядка ? 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)