Я понимаю структуру бинарных деревьев и как их пройти. Тем не менее, я изо всех сил пытаюсь понять их фактическое использование, цели в программах и программировании. Когда я думаю о «реальных» примерах иерархических данных, они почти наверняка имеют более двух детей. Например, в родословной у матери часто может быть более двух детей.
Действительно ли «двоичные деревья» полезны только для хранения линейно связанных данных из-за более быстрого времени обработки массивов и списков? Или же они служат определенной цели для хранения иерархических данных? Если да, то какие есть примеры применения бинарных деревьев? Какие данные таковы, что узел имеет не более 2 дочерних элементов?
data-structures
binary-tree
sw123456
источник
источник
Ответы:
Нет, двоичные деревья не предназначены для хранения иерархических данных в том смысле, о котором вы думаете. Основным вариантом использования n-арных деревьев, где
nзадано фиксированное число, является возможность быстрого поиска , а не семантическая иерархия.Вспомните старую игру, в которой один человек думает о числе от 1 до 100, а другой должен угадать его, используя как можно меньше догадок, и, если вы ошибаетесь, человек, думающий о числе, должен сказать вам, слишком ли вы высокий или слишком низкий? Через некоторое время становится скучно, потому что вы быстро понимаете, что всегда следует начинать с 50, затем переходить к 25 или 75 и продолжать делить диапазон для поиска пополам с каждым новым предположением после этого, и в конечном итоге вы можете угадать любое число в большинстве 7 догадок, гарантировано.
Это может не пригодиться для забавной игры, но именно это свойство делает бинарные (и другие n-арные) деревья полезными: их можно использовать для поиска очень большого набора данных за очень короткое время.
источник
Любая древовидная структура, в которой узел может иметь неограниченное количество дочерних элементов, может быть реализована с использованием бинарного дерева.
Для каждого узла в вашем дереве замените его на узел с указателем вправо и влево. Левый указатель переходит к первому из дочерних узлов. Правый узел переходит к следующему брату узла. Все дочерние элементы данного узла находятся в связанном списке, к которому присоединяются их правые указатели, причем на заголовок списка указывает левый указатель их родителя.
Ваше сложное n-арное дерево стало простым бинарным деревом.
Я уверен, что это в Кнуте, Vol. 1 где-то
источник
Бинарные деревья зачем их использовать?
В программировании вы много работаете с коллекциями однотипных данных.
Два основных способа хранения этих данных: связанные списки и массивы.
Оба они имеют свои плюсы и минусы: в связанный список легко добавлять элементы в любую позицию или удалять элементы. Но доступ к определенному элементу сложнее, потому что вам нужно пройти по списку, пока вы не достигнете нужного элемента.
С массивом получить доступ к определенному элементу легко, но сложнее вставить или удалить элемент, потому что вставка означает: расширить массив на один, сдвинуть все элементы до позиции 1 вставки вправо и вставить элемент.
Таким образом, и связанный список, и массив имеют недостатки.
Двоичные деревья созданы для решения как проблем массива, так и связанного списка:
Таким образом, двоичное дерево создано для случаев, когда у вас много данных, которые регулярно меняются.
источник