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

StackOverflow https://stackoverflow.com/questions/270080

Вопрос

Каковы основные различия между связанным списком и BinarySearchTree?Является ли BST просто способом поддержания LinkedList?Мой инструктор говорил о LinkedList, а затем о 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
------ ------ ------

Другие советы

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

alt text

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

«Связанный

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

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

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

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

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

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

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

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) в лучшем случае.

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

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

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

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

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

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

    5
   / \
  3   9
 / \   \
1   2   12

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

Имеет смысл?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top