LINUX.ORG.RU

Разбалансировка двоичного дерева (поиска)

 , ,


2

4

Вопрос по сабжу, почему так происходит?

Например, тут это объясняется алгоритмом работы операции удаление для двоичного дерева, но разве при многократной вставке новых элементов не будет перекоса одной из веток?!

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

Если это так, хотелось бы ссылку на статью.

И да, в целом ни у Кормена, ни у Седжвика этот вопрос толком не освещается.

Может, выше спорол чепуху, но все равно интересно знать.

★★★★★

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

Deleted ()
Ответ на: комментарий от pru-mike

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

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

Twissel ★★★★★ ()
Ответ на: комментарий от Twissel

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

Twissel ★★★★★ ()
Последнее исправление: Twissel (всего исправлений: 1)
Ответ на: комментарий от Twissel

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

Twissel ★★★★★ ()
Последнее исправление: Twissel (всего исправлений: 2)

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

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

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

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

dave ★★★★★ ()
Ответ на: комментарий от dave

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

dave ★★★★★ ()
Последнее исправление: dave (всего исправлений: 1)
Ответ на: комментарий от dave

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

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

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

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

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

Twissel ★★★★★ ()
Последнее исправление: Twissel (всего исправлений: 1)
Ответ на: комментарий от Twissel

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

anonymous ()
Ответ на: комментарий от Twissel

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

dave ★★★★★ ()
Ответ на: комментарий от anonymous

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

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

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

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

Twissel ★★★★★ ()
Последнее исправление: Twissel (всего исправлений: 4)
Ответ на: комментарий от Twissel

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

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

dave ★★★★★ ()

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

slovazap ★★★★★ ()
Ответ на: комментарий от Twissel

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

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

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

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

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

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

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

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

dave ★★★★★ ()
Ответ на: комментарий от slovazap

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

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

Twissel ★★★★★ ()
Ответ на: комментарий от dave

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

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

Twissel ★★★★★ ()
Ответ на: комментарий от Twissel

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

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

crutch_master ★★★★★ ()
Последнее исправление: crutch_master (всего исправлений: 1)
Ответ на: комментарий от Twissel

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

crutch_master ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.