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

Я бы сказал, что ГЛАВНОЕ отличие состоит в том, что бинарное дерево поиска отсортировано. Когда вы вставляете в двоичное дерево поиска, где эти элементы в конечном итоге сохраняются в памяти, это функция их значения. В связанном списке элементы добавляются в список вслепую независимо от их значения.

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

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

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

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

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

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

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

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

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

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)

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

Пути поиска:

------ ------ ------
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
------ ------ ------

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

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

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

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

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

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

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

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

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

    5
   / \
  3   9
 / \   \
1   2   12

У 9 нет левого потомка, а 1, 2 и 12 - «листья» - у них нет ветвей.

Есть смысл?

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

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

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

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

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

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

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

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

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

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

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

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

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

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

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

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

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

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

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

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

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

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

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

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