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

Question

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

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

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

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

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

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

Answer 6

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

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

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

Answer 7

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

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

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

    5
   / \
  3   9
 / \   \
1   2   12

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

Имеет смысл?

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

Answer 8

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

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

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

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

Answer 9

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

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

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

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

Answer 10

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

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