Различие между LinkedList и деревом двоичного поиска
NullPointerException s - исключения, возникающие при попытке использовать ссылку, которая указывает на отсутствие местоположения в памяти (null), как если бы она ссылалась на объект. Вызов метода по нулевой ссылке или попытка получить доступ к полю нулевой ссылки вызовет функцию NullPointerException. Они наиболее распространены, но другие способы перечислены на странице NullPointerException javadoc.
Вероятно, самый быстрый пример кода, который я мог бы придумать для иллюстрации NullPointerException, be:
public class Example {
public static void main(String[] args) {
Object obj = null;
obj.hashCode();
}
}
В первой строке внутри main я явно устанавливаю ссылку Object obj равной null. Это означает, что у меня есть ссылка, но она не указывает на какой-либо объект. После этого я пытаюсь обработать ссылку так, как если бы она указывала на объект, вызывая метод на нем. Это приводит к NullPointerException, потому что нет кода для выполнения в местоположении, на которое указывает ссылка.
(Это техничность, но я думаю, что она упоминает: ссылка, которая указывает на null, равна 't то же, что и указатель C, указывающий на недопустимую ячейку памяти. Нулевой указатель буквально не указывает на в любом месте , который отличается от указаний на местоположение, которое оказывается недопустимым.)
13 ответов
Связанный список:
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 подузла, где (в случае дерева двоичного поиска) ключ левого узла меньше, чем ключ узла и ключ правильного узла являются больше, чем узел. Пока дерево сбалансировано, searchpath к каждому объекту намного короче, чем это в связанном списке.
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
------ ------ ------
Они - полностью различные структуры данных.
связанный список А является последовательностью элемента, где каждый элемент связан со следующим, и в случае двунаправленного связанного списка, предыдущим.
дерево двоичного поиска А является чем-то полностью различным. Это имеет корневой узел, корневой узел имеет до двух дочерних узлов, и каждый дочерний узел может иметь до двух дочерних примечаний и т.д. и т.д. Это - довольно умная структура данных, но это было бы несколько утомительно для объяснения его здесь. Проверьте Википедия artcle на нем.
Дерево двоичного поиска может быть реализовано любым способом, оно не должно использовать связанный список.
связанный список А является просто структурой, которая содержит узлы и указатели/ссылки на другие узлы в узле. Учитывая главный узел списка, можно просмотреть к любому другому узлу в связанном списке. Двунаправленные связанные списки имеют два указателя/ссылки: нормальная ссылка на следующий узел, но также и ссылка на предыдущий узел. Если последний узел в двунаправленном связанном списке ссылается на первый узел в списке как следующий узел, и первый узел ссылается на последний узел как на свой предыдущий узел, это, как говорят, циклический список.
дерево двоичного поиска А является деревом, которое разделяет его вход на две примерно равных половины на основе алгоритма сравнения двоичного поиска. Таким образом только требуется очень немного поисков для нахождения элемента. Например, если бы у Вас было дерево с 1-10, и необходимо было искать три, сначала элемент наверху был бы проверен, вероятно, 5 или 6. Три были бы меньше, чем это, поэтому только первая половина дерева будет тогда проверена. Если следующее значение равняется 3, у Вас есть оно, иначе, сравнение сделано, и т.д., пока или это не найдено или его данные, возвращается. Таким образом дерево быстро для поиска, но не nessecarily быстро для вставки или удаления. Это очень грубые описания.
Связанный список из Википедии, и Дерево двоичного поиска , также из Википедии.
Связанный список является прямыми Линейными данными с соседними узлами, соединенными друг с другом, например, A-> B-> C. Можно рассмотреть его как прямой забор.
BST является иерархической структурой точно так же, как дерево с основной соединительной линией, подключенной к ответвлениям и тем ответвлениям внутренний изгиб, подключенный к другим ответвлениям и так далее. "Двоичное" слово здесь означает, что каждое ответвление подключено максимум к двух ответвлений.
Вы используете связанный список для представления прямых данных только с каждым объектом, подключенным максимум к одного объекта; тогда как можно использовать BST для соединения объекта с двумя объектами. Можно использовать BST для представления данных, таких как родословная, но это станет деревом поиска не, поскольку может быть больше чем два ребенка каждому человеку.
У них действительно есть общие черты, но основное различие - то, что Дерево двоичного поиска разработано для поддержки эффективного поиска элемента или "ключа".
дерево двоичного поиска А, как двунаправленный связанный список, указывает на два других элемента в структуре. Однако при добавлении элементов к структуре, вместо того, чтобы просто добавить их до конца списка, двоичное дерево реорганизовано так, чтобы элементы, связанные с "левым" узлом, были меньше, чем текущий узел и элементы, связанные с "правильным" узлом, больше, чем текущий узел.
В простой реализации, новый элемент сравнивается с первым элементом структуры (корень дерева). Если это меньше, "левое" ответвление взято, иначе "правильное" ответвление исследовано. Это продолжает каждый узел, пока ответвление, как не находят, пусто; новые заливки элемента то положение.
С этим простым подходом, если элементы добавляются в порядке, Вы заканчиваете со связанным списком (с той же производительностью). Различные алгоритмы существуют для поддержания некоторой меры баланса в дереве путем реконструкции узлов. Например, деревья AVL делают большую часть работы для хранения дерева максимально сбалансированным, давая лучшее время поиска. Красно-черные деревья не сохраняют дерево столь сбалансированным, приводя к немного более медленным поискам, но действительно меньше работают в среднем, как ключи вставлены или удалены.
Проблема со связанным списком ищет в нем (вставляют ли для извлечения или).
Для единственного связанного списка, необходимо запустить в голове и искать последовательно для нахождения желаемого элемента. Для предотвращения потребности просканировать целый список Вам нужны дополнительные ссылки на узлы в рамках списка, в этом случае, это больше не простой связанный список.
двоичное дерево А допускает более быстрый поиск и вставку, будучи по сути отсортированным и пригодный для навигации.
альтернативой, которую я использовал успешно в прошлом, является SkipList. Это обеспечивает что-то сродни связанному списку, но с дополнительными ссылками для разрешения поисковой производительности, сопоставимой с двоичным деревом.
Связанный список - просто это... список. Это линейно; каждый узел имеет ссылку на следующий узел (и предыдущее, если Вы говорите о двунаправленном связанном списке). Дерево переходит---, каждый узел имеет ссылку на различные дочерние узлы. Двоичное дерево является особым случаем, в котором каждый узел имеет только двух детей. Таким образом, в связанном списке, каждый узел имеет предыдущий узел и следующий узел, и в двоичном дереве, узел имеет покинутого ребенка, правильного ребенка и родителя.
Эти отношения могут быть двунаправлены или однонаправлены, в зависимости от того, как необходимо быть в состоянии пересечь структуру.
Связанные списки и BSTs действительно не имеют много общего, за исключением того, что они - оба структуры данных то действие как контейнеры. Связанные списки в основном позволяют Вам вставлять и удалять элементы эффективно в любом местоположении в списке при поддержании упорядочивания списка. Этот список реализован с помощью указателей от одного элемента до следующего (и часто предыдущее).
А дерево двоичного поиска , с другой стороны, является структурой данных более высокой абстракции (т.е. это не определило , как это реализовано внутренне), который допускает эффективные поиски (т.е. для нахождения определенного элемента, Вы не должны смотреть на все элементы.
Уведомление, что связанный список может считаться ухудшившимся двоичным деревом, т.е. деревом, где все узлы только имеют одного ребенка.
Связанный список является порядковым номером "узлов", связанных друг с другом, т.е.:
public class LinkedListNode
{
Object Data;
LinkedListNode NextNode;
}
Дерево двоичного поиска А использует подобную структуру узла, но вместо того, чтобы связаться со следующим узлом, оно связывается с двумя дочерними узлами:
public class BSTNode
{
Object Data
BSTNode LeftNode;
BSTNode RightNode;
}
По следующим определенным правилам при добавлении новых узлов к BST, можно создать структуру данных, которая очень быстра для пересечения. Другие ответы здесь подробно изложили эти правила, я просто хотел показать на уровне кода различие между классами узла.
важно отметить, что при вставке отсортированных данных в BST Вы закончите со связанным списком, и Вы теряете преимущество использования дерева.
из-за этого, linkedList является O (N) пересекающаяся структура данных, в то время как BST является O (N) пересекающаяся структура данных в худшем случае, и O (зарегистрируйте N) в лучшем случае.
Я сказал бы, что Основное различие - то, что дерево двоичного поиска отсортировано. То, когда Вы вставляете в дерево двоичного поиска, где те элементы заканчивают тем, что были сохранены в памяти, является функцией их значения. Со связанным списком элементы вслепую добавляются к списку независимо от своего значения.
Сразу же Вы можете некоторая торговля offs: порядком вставки заповедника Связанных списков и вставкой являются менее дорогие Деревья двоичного поиска, обычно более быстры для поиска
В информатике дерево двоичного поиска (BST) является структурой данных двоичного дерева, которая имеет следующие свойства:
- каждый узел (объект в дереве) имеет отличное значение;
- оба левые и правые поддеревья должны также быть деревьями двоичного поиска;
- левое поддерево узла содержит только значения меньше, чем значение узла;
- правильное поддерево узла содержит только значения, больше, чем или равный значению узла.
В информатике, связанный список является одной из фундаментальных структур данных и может использоваться для реализации других структур данных.
, Таким образом, Дерево двоичного поиска является абстрактным понятием, которое может быть реализовано со связанным списком или массивом. В то время как связанный список является фундаментальной структурой данных.
Это на самом деле довольно просто. Связанный список является просто набором объектов, объединенных в цепочку вместе без определенного порядка. Можно думать о нем как о действительно тощем дереве, которое никогда не переходит:
1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (который в последний раз художественная ASCII попытка завершающегося пустого указателя)
Дерево двоичного поиска А отличается 2 способами: двоичная часть означает, что каждый узел имеет 2 дети, не один, и поисковая часть означает, что те дочерние элементы расположены для ускорения поисков - только меньшие объекты налево, и только большие направо:
5
/ \
3 9
/ \ \
1 2 12
9 не имеет никакого покинутого ребенка, и 1, 2, и 12 "листы" - у них нет ответвлений.
Имеют смысл?
Для большинства видов "поиска" использования, BST лучше. Но для просто "хранения списка вещей иметь дело с более поздним Методом "первым пришел - первым вышел" или В обратном порядке" видами вещей, связанный список мог бы работать хорошо.
Дерево двоичного поиска является двоичным деревом, в котором каждый внутренний узел x хранилища элемент, таким образом что элемент, сохраненный в левом поддереве , x меньше чем или равны x и элементы, сохраненные в правильном поддереве , x больше, чем или равны x .
Теперь Связанный список состоит из последовательности узлов, каждый содержащий произвольные значения и одну или две ссылки, указывающие на следующие и/или предыдущие узлы.
