График, представленный как список смежности, как бинарное дерево, возможно ли это?

Question

извинения сначала, английский не мой первый язык.

Итак, вот мое понимание на графике, представленном в виде списка соприкосновений: обычно используется для разреженного графика, что имеет место для большинства графиков, и использует списки V (количество вершин). поэтому, V head pointers + 2e (# of edge) узлы для неориентированного графика. Поэтому сложность пространства = O (E + V) Поскольку любой узел может иметь до V-1 ребер (исключая себя), он имеет сложность времени O (V) для проверки смежности узла.

Что касается проверки всех ребер, то он принимает O (2e + V) так, что O (v + e) ​​ Теперь, поскольку он используется главным образом для разреженного графика, редко O (v) проверяет смежность, но просто количество ребер данной вершины имеет (что является O (V) в худшем случае, поскольку V-1 является возможным максимумом)

Что мне интересно, возможно ли сделать бинарное дерево списка (реберных узлов) ? Итак, чтобы выяснить, смещен ли узел A к узлу B, сложность времени будет O (logn), а не линейной O (n). Если это возможно, на самом деле это делается довольно часто? Также, как называется такая структура данных? Я был googling, если такие комбинации возможны, но ничего не могли найти. Я был бы очень благодарен, если бы кто-нибудь мог объяснить это мне подробно, поскольку я новичок в структуре данных. Спасибо.

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

Answer 1

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

Как вы говорите, это представление списка смежности часто используется для разреженных графиков. Часто «разреженный граф» означает, что определенная вершина смежна с несколькими другими. Поэтому ваш «список смежности» для конкретной вершины будет очень мал. В то время как это правда, что двоичный поиск - O (log n), а последовательный поиск - O (n), когда n - очень маленький последовательный поиск быстрее. Я видел случаи, когда последовательный поиск превосходит бинарный поиск, когда n меньше 16. Это зависит от реализации, конечно, но не рассчитывает, что бинарный поиск будет быстрее для небольших списков.

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

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

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