че?

https://www.youtube.com/watch?v=aK0E-qrXo_I&t=894

Выдыхай. А по теме - попробуй исполнить алгоритмы в мозге/на бумаге - должно помочь

Вопросом на вопрос

По ссылке ходил?

The tree tends to become unbalanced to the right

Немного поясняет да, но это частный случай.

Конечно, можно было бы обойтись стандартным don't overthinking, но это тот случай, когда интересно разобраться.

Это дерево используется специальным образом - хитрая куча с приоритетом. С хитрым удалением, который умеет удалять только самый длиный левый путь. Естественно будет перекос.

А ну так я про это и спрашивал в ОП. Это обусловлено операцией удаления или есть «скрытые пружины»?

Просто где-то раньше натыкался, что мол в классическом бинарном дереве при большом количестве элементов перекос идет в тоже из-за своеобразного «парадокса дней рождения» в переносном смысле, конечно.

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

Ну вот да, именно про это я анализ и находил на сайте какого-то западного универа. Мол это фундаментальное свойство бинарного дерева, если количество элементов в нём достаточно велико.

А меня сразу на вилы. ЛОР уже не торт)

Уже точно не помню, но где-то читал, что такого рода разбалансировка классического двоичного дерева имеет таки статистико-вероятностную природу :-)

С трудом представляю, чтобы обычное двоичное дерево само балансировалось. Разблансировка такого дерева - скорее норма, чем исключение.

Может быть, и можно выдвинуть какую-то гипотезу об исходном распределении, потом посчитать вероятность разбалансировки. Ну, окажется, что она p=0,9999999999999, но зачем, когда очевидно, что это происходит?

Другое дело, если у тебя вполне заданное распределение исходных данных, и у тебя есть код, где используется обычное двоичное дерево (но почему? - если только не деревья k-d). И стоит задача узнать, когда становится все плохо. Тут уже математика нужна.

Кстати, и в таком случае можно по-быстрому оценить вероятность по методу Монте-Карло, особенно не парясь с заумной математикой. Нужен только критерий разбалансированности, а их явно больше, чем один.

Вот, уже третий человек в треде, который понял о чем я :-)

Просто странно, почему все учебники обходят этот вопрос стороной? Ну вот оно у нас разбалансируется и все тут, всё.

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

Так что, разобравшись толком я бы мог написать ответ лучше, чем по ссылке на SO. Другое дело, а кому он нужен ))

Там сейчас все равно, наверное, 2/3 аудитории индусо-макаки...

Ты вообще о чем? Про идеально сбалансированное дерево, или про разные виды (почти) сбалансированных деревьев, или про наивные верящие в о-великий-рандом деревья?
Идеал (почти всегда) требует польной перестройки дерева при изменении, а это как минимум линейная сложность, если ты оракул; а на деле получишь экспоненту. Почти сбалансированные жертвуют идеалом, но дают некоторые вполне интересные гарантии без перестройки всего дерева. А наивными деревьями ты можешь троллить на всяких разных форумах про несправедливость рандома.

Нет, я как раз из тех, кто ничего не понял. Если ты можешь ввести упорядоченность по ключу (реализовать класс типов Ord), то можешь получить готовую реализацию самобалансирующего двоичного дерева (хоть, красно-черные, хотя AVL) или B-дерево (чуть по-лучше дружат с кешем процессора, чем двоичные деревья, но фиг знает, как там с балансировкой). Если же ты можешь посчитать стабильный хеш-код ключа, то можно использовать готовую реализацию хеш-мапы, что обычно много лучше, чем простейшее двоичное дерево поиска. Но бывают случаи, когда именно нужно обычное двоичное дерево, например, для реализации дерева k-d или еще чего. Вот там уже надо думать и смотреть.

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

Т.е. рано или поздно вылезут статистические свойства и мы будем вынуждены балансировать наше деревце.

За инфу спасибо, погуглю на досуге.

P.S. Или я что-то упустил?

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

Это-то как раз очень легко проверяется на компьютере. Тут даже статью писать не надо. Но я очень сильно сомневаюсь в твоем предположении. Чутье подсказывает, что оно ложно.

А в чем проверить, Julia, Mathematica ?

Разбалансировка классическоего дерева имеет вполне себе детерминированную природу, если вставлять упорядоченную последовательность.

вы график биномиального распределения c p=0.5 увидеть хотите чтоли?

Ну, я же выше написал. Попробую расписать.

Вот ты пишешь «идеальный рандом». Это я понимаю как почти отсутствие информации о случайной величине, что можно перевести на более формальный язык как «случайная величина по закону равномерного распределения». Добавим некоторые границы: минимум, максимум. И так, есть на входе случайная величина по этому закону, пусть целочисленная. Для простоты будем рассматривать только добавление элемента в дерево.

Дальше берем метод Монте-Карло, т.е. устраиваем серию экспериментов. Пусть будет 10000 запусков.

Во время каждого запуска имитируем поток событий по добавлению. Пусть с глубиной 1000 событий добавления на каждый запуск. В конце получили некоторое двоичное дерево.

Теперь нам нужен критерий, который будет говорить о том, наше двоичное дерево сбалансированное или нет. Может у Кнута есть, а можно и самому придумать. Что-то взять совсем простое.

Если дерево сбалансированное, то запуск возвращает число 1, иначе - 0.

Итого. На 10000 запусков у нас получается 10000 чисел 0 или 1. Находим среднее. Это будет оценкой вероятности того, что дерево обычно становится сбалансированным при случайных операциях вставки на случайных данных. Уже что-то. Вполне информативно.

Ну, а дальше можно залезть в дебри математической статистики по желанию.

Спасибо!

Это понятно. Это есть у Седжвика на видео в комментариях выше.

Меня интересует, когда начнёт проявляться разбалансированность, если сделать много случайных вставок, «хорошо распределённых» случайных величин.

Как в этом посте Разбалансировка двоичного дерева (поиска) (комментарий)

Кстати, критерий сбалансированности это когда высота левого и правого поддеревьев отличается не более, чем на один элемент.

Так что да, в своей гипотезе я уже не сильно уверен)

Wikipedia

After a long intermixed sequence of random insertion and deletion, the expected height of the tree approaches square root of the number of keys, √n, which grows much faster than log n.

https://en.wikipedia.org/wiki/Binary_search_tree

Да, дошло)

Да, видимо распределения тут ни при чём, всё-таки.

Вот интересная игрушка по сабжу

Кстати, критерий сбалансированности это когда высота левого и правого поддеревьев отличается не более, чем на один элемент.

Это утопия. Нам, индусам, главное, чтобы оно не выродилось в отсортированный список.

Игрушка зачётная. Покажу жене дома.

У тебя жена тоже программист?

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