Оптимальные бинарные деревья поиска

У меня есть задание по оптимальным бинарным деревьям поиска, и при его выполнении возникло несколько вопросов. Я нашел много ссылок в Интернете полезными (только из поиска Google), но мне было интересно...

Почему ключи должны быть изначально отсортированы?

Если я получаю более низкую стоимость (для оптимального BST), когда ключи не отсортированы, означает ли это, что в моем коде должна быть ошибка?

Должен ли оптимальный BST быть полным/идеальным? (используя определения полного и совершенного из Википедии)

Идеальное бинарное дерево — это полное бинарное дерево, в котором все листья находятся на одной глубине или на одном уровне. [1] (Его также неоднозначно называют полным бинарным деревом.)

Полное бинарное дерево — это бинарное дерево, в котором все уровни, за исключением, возможно, последнего, полностью заполнены, а все узлы находятся максимально слева. [2]

Что касается последнего вопроса, я бы предположил, что оптимальное дерево должно быть полным/идеальным, но некоторые онлайн-апплеты заставляют меня думать иначе. Я не могу объяснить, почему, хотя...


data-structures binary-search-tree
person Chet    schedule 30.09.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Почему ключи должны быть изначально отсортированы?

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

Если я получаю более низкую стоимость (для оптимального BST), когда ключи не отсортированы, означает ли это, что в моем коде должна быть ошибка?

Нет, если только вы не программируете самобалансирующееся дерево (ваш алгоритм самобалансировки не работает).

должен ли оптимальный BST быть полным/идеальным?

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

person Robert Harvey    schedule 30.09.2011
comment
Я не использую самобалансирующееся дерево. Означает ли это, что либо оптимальное дерево неуникально (при условии уникальных ключей), либо что дерево (упомянутое ранее, сгенерированное с отсортированными ключами) не является оптимальным? - person Chet; 01.10.2011
comment
Небалансное двоичное дерево, в которое вставлены ключи в отсортированном порядке, не является оптимальным, поскольку ключи не будут распределяться равномерно. Вместо этого вы получите связанный список, потому что все ключи будут вставлены вниз по одной стороне дерева. jaltiere.com/blogImages/redblacktree/binarysearchtree.png - person Robert Harvey; 01.10.2011
comment
В порядке. Я понял все, что вы мне сказали, и теперь я точно определил свою проблему. Хотя не похоже, что большинство онлайн-апплетов вообще генерируют оптимальные деревья (linneus20 .ethz.ch:8080/4_7_2.html) Например, использование 2,9 и 11 в качестве ключей должно оптимально создать дерево с 11 в качестве корня, но я получаю это как оптимальный результат (9 - это корень ) postimage.org/image/fm8qsgkk Я еще не знаю, как это исправить. Если только у меня где-то нет изъяна в логике. - person Chet; 01.10.2011
comment
Неважно. Большие числа справа и меньшие слева. - person Chet; 01.10.2011