Разница между LinkedList и деревом двоичного поиска

В чем основные отличия между Linked List и BinarySearchTree? Является ли BST просто способом поддержки LinkedList? Мой инструктор говорил о LinkedList, а затем BST, но не сравнивал их или не говорил, когда предпочитал один за другим. Это, наверное, немой вопрос, но я действительно смущен. Я был бы признателен, если бы кто-то мог прояснить это простым способом.

Ответ 1

Связанный список:

Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)

Двоичное дерево:

                 Node(1)
                /
            Node(2)
           /    \
          /      Node(3)
  RootNode(4)
          \      Node(5)
           \    /
            Node(6)
                \
                 Node(7)

В связанном списке элементы связаны друг с другом одним указателем. В двоичном дереве каждый node может иметь 0, 1 или 2 поднода, где (в случае двоичного дерева поиска) ключ слева node меньше, чем ключ node, а ключ правый node больше, чем node. Пока дерево сбалансировано, путь поиска к каждому элементу намного короче, чем в связанном списке.

SearchPaths:

------ ------ ------
key    List   Tree
------ ------ ------
1      1      3
2      2      2
3      3      3
4      4      1
5      5      3
6      6      2
7      7      3
------ ------ ------
avg    4      2.43
------ ------ ------

По более крупным структурам средний путь поиска становится значительно меньшим:

------ ------ ------
items  List   Tree
------ ------ ------
     1      1   1
     3      2   1.67
     7      4   2.43
    15      8   3.29
    31     16   4.16
    63     32   5.09
------ ------ ------

Ответ 2

A Дерево двоичного поиска - это двоичное дерево, в котором каждый внутренний node x хранит элемент, так что элемент, хранящийся в левом поддереве x, меньше или равен x и сохраненным элементам в правом поддереве x больше или равно x.

Теперь Связанный список состоит из последовательности узлов, каждая из которых содержит произвольные значения и одну или две ссылки, указывающие на следующий и/или предыдущие узлы.

Ответ 3

В информатике дерево двоичного поиска представляет собой структуру данных двоичного дерева, которая обладает следующими свойствами:

каждый node (элемент в дереве) имеет отличное значение;
как левое, так и правое поддеревья также должны быть двоичными деревьями поиска;
левое поддерево node содержит только значения, меньшие значения node;
в правом поддереве node содержатся только значения, больше или равные значению node.

В информатике связанный список является одной из фундаментальных структур данных и может использоваться для реализации других структур данных.

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

Ответ 4

Я бы сказал, что главное отличие состоит в том, что дерево двоичного поиска сортируется. Когда вы вставляете в двоичное дерево поиска, где эти элементы в конечном итоге хранятся в памяти, является функцией их значения. Со связанным списком элементы вслепую добавляются в список независимо от их значения.

Сразу же вы можете получить компромисс: Связанные списки сохраняют порядок вставки, а вставка менее дорогая Деревья двоичного поиска обычно быстрее выполняют поиск

Ответ 5

Связанный список - это последовательное число "узлов", связанных друг с другом, то есть:

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

В двоичном дереве поиска используется аналогичная структура node, но вместо ссылки на следующий node он ссылается на два дочерних узла:

public class BSTNode
{
    Object Data
    BSTNode LeftNode;
    BSTNode RightNode;
}

Следуя определенным правилам при добавлении новых узлов в BST, вы можете создать структуру данных, которая очень быстро перемещается. Другие ответы здесь подробно описаны в этих правилах, я просто хотел показать на уровне кода разницу между классами node.

Важно отметить, что если вы вставляете отсортированные данные в BST, вы получите связанный список, и вы потеряете преимущество использования дерева.

Из-за этого связанныйList представляет собой структуру данных обхода O (N), тогда как BST представляет собой структуру данных обхода O (N) в худшем случае и O (log N) в лучшем случае.

Ответ 6

Связанные списки и BST на самом деле не имеют много общего, за исключением того, что они являются структурами данных, которые действуют как контейнеры. Связанные списки в основном позволяют эффективно вставлять и удалять элементы в любом месте в списке, сохраняя при этом порядок список. Этот список реализуется с использованием указателей от одного элемента к другому (и часто предыдущего).

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

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

Ответ 7

Это на самом деле довольно просто. Связанный список - это всего лишь куча предметов, соединенных вместе, в определенном порядке. Вы можете думать об этом как о действительно худой дереве, которое никогда не веткится:

1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (последним является попытка ascii-art при завершении нулевого значения)

Двоичное дерево поиска отличается двумя способами: двоичная часть означает, что каждый node имеет 2 детей, а не один, а часть поиска означает, что эти дети настроены для ускорения поиска - только меньшие элементы слева, и только большие справа:

9 не имеет левого ребенка, а 1, 2 и 12 - "листья" - у них нет ветвей.

Имеют смысл?

Для большинства видов поиска, BST лучше. Но для просто "хранения списка вещей, чтобы иметь дело с более поздними вещами First-In-First-Out или Last-In-First-Out" связанный список мог бы работать хорошо.

Ответ 8

Связанный список - это просто... список. Он линейный; каждый node имеет ссылку на следующий node (и предыдущий, если вы говорите о двусвязном списке). Ветви дерева --- каждый node имеет ссылку на различные дочерние узлы. Бинарное дерево - это особый случай, когда каждый node имеет только двух детей. Таким образом, в связанном списке каждый node имеет предыдущий node и следующий node, а в двоичном дереве node имеет левый дочерний, правый и родительский.

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

Ответ 9

Проблема со связанным списком выполняет поиск внутри него (для извлечения или вставки).

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

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

Альтернативой, которую я успешно использовал в прошлом, является SkipList. Это обеспечивает нечто похожее на связанный список, но с дополнительными ссылками, позволяющими сопоставлять производительность поиска с бинарным деревом.

Ответ 10

У них есть сходства, но основное различие заключается в том, что двоичное дерево поиска предназначено для поддержки эффективного поиска элемента или "ключа".

Двоичное дерево поиска, подобно двусвязному списку, указывает на два других элемента в структуре. Однако при добавлении элементов в структуру, а не просто добавлении их в конец списка, двоичное дерево реорганизуется, так что элементы, связанные с "левым" node, меньше текущего node и элементов, связанных с "правый" node больше, чем текущий node.

В простой реализации новый элемент сравнивается с первым элементом структуры (корнем дерева). Если это меньше, берется "левая" ветвь, иначе рассматривается "правая" ветвь. Это продолжается с каждым node, пока не обнаружено, что ветвь пуста; новый элемент заполняет эту позицию.

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

Ответ 11

Связанный список является прямым Линейные данные со смежными узлами, связанными друг с другом, например. А- > В- > С. Вы можете считать это прямым забором.

BST - это иерархическая структура, подобная дереву с основным стволом, соединенным с ветвями, и те ветки, которые в свою очередь подключены к другим ветвям и т.д. "Двоичное" слово означает, что каждая ветвь связана с максимум двумя ветвями.

Вы используете связанный список для представления прямых данных только для каждого элемента, подключенного к максимум одному элементу; тогда как вы можете использовать BST для подключения элемента к двум элементам. Вы можете использовать BST для представления данных, таких как генеалогическое древовидное дерево, но это станет n-арным деревом поиска, поскольку каждому человеку может быть больше двух детей.

Ответ 12

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

Связанный список - это просто структура, которая содержит узлы и указатели/ссылки на другие узлы внутри node. Учитывая заголовок node списка, вы можете перейти к любому другому node в связанном списке. У двусвязных списков есть два указателя/ссылки: нормальная ссылка на следующий node, но также ссылка на предыдущий node. Если последний node в двусвязном списке ссылается на первый node в списке как следующий node, а первый node ссылается на последний node как на предыдущий node, сказано быть круговым списком.

Двоичное дерево поиска - это дерево, которое разбивает свой вход на две грубо равные половины на основе алгоритма сравнения бинарного поиска. Таким образом, для поиска элемента требуется всего лишь несколько поисков. Например, если у вас есть дерево с 1-10, и вам нужно искать три, сначала элемент сверху должен быть проверен, вероятно, 5 или 6. Три будут меньше, поэтому только первая половина дерево будет проверено. Если следующее значение равно 3, у вас оно есть, в противном случае выполняется сравнение и т.д., Пока он не будет найден или данные не будут возвращены. Таким образом, дерево выполняется быстро для поиска, но не очень быстро для вставки или удаления. Это очень грубые описания.

Связанный список из wikipedia и Дерево двоичного поиска, также из википедии.

Ответ 13

Это совершенно разные структуры данных.

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

Двоичное дерево поиска - это нечто совершенно другое. У этого есть корень node, корень node имеет до двух дочерних узлов, и каждый ребенок node может иметь до двух дочерних нот и т.д. И т.д. Это довольно умная структура данных, но это было бы немного утомительно чтобы объяснить это здесь. Посмотрите Wikipedia artcle на нем.