Предположим, мы хотим использовать какую-то структуру данных для хранения наборааккуратныйКоллекция данных int и надежда, что эта структура данных может быть максимально быстрой в таких операциях, как вставка, удаление и поиск, тогда какую структуру данных вы бы использовали?
множество
Очень простой метод должен быть использован массивы. С точки зрения поиска, если используется массивное хранилище, используйтедихотомияУказанный элемент может быть найден за время O(logn), но массив не является дружественным к операциям вставки и удаления.Время, необходимое для поиска целевой позиции, составляет O(logn), а время, необходимое для вставки и удаления, равно Степень сложности равна O(n), потому что все элементы нужно перемещать, поэтому окончательная требуемая временная сложность равна O(n). Например, для следующего массива:
вставить элемент 3
связанный список
Другим простым методом должно быть использование связанного списка, который находится ввставить, удалитьПоддержка относительно дружелюбна. Когда мы находим целевую позицию, временная сложность вставки и удаления элементов составляет O (1). Обратите внимание, чтоЯ говорю о нахождении целевой позиции., временная сложность вставки и удаления составляет O(1).
Однако связанный список неудобен с точки зрения поиска. Он не может использовать бинарный поиск, как массив. Он может быть пройден только по одному узлу за раз. Поэтому, плюс время, необходимое для поиска, общая временная сложность, необходимая для вставки и удаление - О. (n).
Если мы сможем повысить эффективность поиска в связанном списке и сделать временную сложность поиска в связанном списке как можно ближе к O(logn), тогда связанный список станет отличным выбором.
Улучшить скорость поиска в связанном списке
Можно ли улучшить скорость поиска связанного списка?
Для следующего связанного списка
Если мы хотим найти элементы 9, само собой разумеется, что нам нужно начать обход узлов с нуля, пройдя в общей сложности восемь узлов, чтобы найти элементы 9. Возможность взять некоторые из стратегий, давайте пройдемся по пяти, чтобы найти ее элементы 9? Пожалуйста, найдите минутку, чтобы подумать о том, как достичь?
За счет упорядочения элементов мы можем ускорить поиск, добавив несколько путей. Например
Таким образом, нам нужно пройти всего 5 раз, чтобы найти элемент 9 (красная линия — это путь поиска).
Можете ли вы продолжить ускорение поиска?
Ответ - да, просто добавьте еще один слой, чтобы найти его нужно всего 4 раза, точно так же, как когда мы едем в метро, когда мы едем на определенную станцию, есть несколько маршрутов: экспресс и медленный. медленные линии, мы можем быстрее добраться до определенной станции.
Конечно, он также может увеличить один слой.
Основываясь на этом методе, для связанного списка с n элементами мы можем принять форму пути указателя уровня (logn + 1), и мы можем найти цель в пределах временной сложности элемента O (logn), этой структуры данных, мы также называем этостол для прыжков, таблицу переходов также можно рассматривать как деформацию связанного списка, но онабинарный поискфункция.
Вставить и удалить
В приведенном выше примере есть 9 узлов, всего 4 слоя, что можно назвать идеальной таблицей переходов, но по мере того, как мы вставляем/удаляем узлы в таблице переходов, количество узлов таблицы переходов будет меняться, что означает jumping Количество слоев таблицы также будет меняться динамически.
Здесь мы сталкиваемся с проблемой, т.Сколько уровней должен охватывать вновь вставленный узел?
Эта проблема была решена для нас Даниэлем, и принятая стратегия состоит в том, чтобы пройтиПодбросьте монету, чтобы определить, сколько слоев охватывает вновь вставленный узел.: подбрасывать монету каждый раз, когда мы хотим вставить узел, если подбрасываниефронт, затем продолжайте подбрасывать, пока не будетотрицательныйПока в этом процессе появилась положительная статистика.частота, это число используется как количество слоев, охваченных узлом.
Таким образом, вы можете максимально приблизиться к идеальному количеству слоев. Вы представляете, почему это так?
вставлять
Например, мы хотим вставить узлы 3 и 4. Подбрасывая монету, мы знаем, что слои, натянутые узлами 3 и 4, равны 0 и 2 соответственно (количество слоев начинается с 0), и процесс вставки выглядит следующим образом:
Вставка 3, связующий слой 0.
Вставка 4, охватывающая 2 слоя.
Удалить
После решения вставки, давайте взглянем на удаление. Удаление относительно просто. Например, если мы хотим удалить 4, то мы можем напрямую удалить 4 и количество слоев, которые он охватывает.
резюме
Вставка и удаление таблицы переходов обсуждались до сих пор, и соответствующие свойства таблицы переходов приведены ниже:
(1) Каждый слой таблицы переходов является записьюупорядоченный связанный список.
(2) Количество операций поиска в таблице пропусков приблизительно равно количеству слоев, временная сложность — O(logn), а вставка и удаление — также O(logn).
(3) Самый нижний связанный список содержит все элементы.
(4) Таблица пропуска представляет собой рандомизированную структуру данных (количество слоев определяется подбрасыванием монеты).
(5) Объемная сложность таблицы переходов равна O(n).
Таблицы переходов против бинарных деревьев поиска
Некоторые люди могут сказать, что можно использовать и бинарное дерево поиска, потому что вставка, удаление и поиск в дереве поиска также требуют примерно O(logn) временной сложности.
Однако бинарное дерево поиска может иметь экстремальную ситуацию, то есть, если вставленные данные всегда будут в порядке, все узлы будут смещены в определенную сторону. Например
Эта структура соединения приведет к тому, что эффективность поиска двоичного дерева поиска станет равной O (n), что значительно уменьшит двоичное дерево поиска.
Таблицы прыжков против красных черных деревьев
Можно сказать, что красно-черный вариант бинарного дерева поиска.Красно-черный поиск, вставка и удаление временной сложности приблизительно O(logn), но те, кто изучал красно-черные деревья, знают, что красно-черные деревья сложнее, чем столы для прыжков.Больше, во всяком случае, я был оскорблен красно-черным деревом. При выборе структуры данных иногда необходимо учитывать стоимость обучения.
Более того, когда красно-черное дерево вставляет и удаляет узлы, оно корректирует структуру для поддержания баланса красно-черного дерева По сравнению с таблицей переходов, которая напрямую определяет, сколько слоев нужно пересечь через случайное число, стоимость временная сложность выше, чем у таблицы прыжков Таблица прыжков.
Конечно, красно-черное дерево не обязательно хуже таблицы переходов, в некоторых случаях красно-черное дерево будет лучшим выбором, поэтому ключ к выбору структуры данных зависит от случая.
Таким образом, если вы поддерживаете упорядоченный набор и хотите как можно быстрее выполнять такие операции, как поиск, вставка, удаление и т. д., то таблица пропуска будет хорошим выбором. Данные данных в Redis используют таблицу переходов.Конечно, Ridis также комбинирует структуры данных, такие как хэш-таблицы, и использует составную структуру данных.
код показывает, как показано ниже
package skiplist;
//节点
class Node{
int value = -1;
int level;//跨越几层
Node[] next;//指向下一个节点
public Node(int value, int level) {
this.value = value;
this.level = level;
this.next = new Node[level];
}
}
//跳跃表
public class SkipList {
//允许的最大层数
int maxLevel = 16;
//头节点，充当辅助。
Node head = new Node(-1, 16);
//当前跳跃表节点的个数
int size = 0;
//当前跳跃表的层数,初始化为1层。
int levelCount = 1;
public Node find(int value) {
Node temp = head;
for (int i = levelCount - 1; i >= 0; i--) {
while (temp.next[i] != null && temp.next[i].value < value) {
temp = temp.next[i];
}
}
//判断是否有该元素存在
if (temp.next[0] != null && temp.next[0].value == value) {
System.out.println(value + " 查找成功");
return temp.next[0];
} else {
return null;
}
}
// 为了方便，跳跃表在插入的时候，插入的节点在当前跳跃表是不存在的
//不允许插入重复数值的节点。
public void insert(int value) {
int level = getLevel();
Node newNode = new Node(value, level);
//update用于记录要插入节点的前驱
Node[] update = new Node[level];
Node temp = head;
for (int i = level - 1; i >= 0; i--) {
while (temp.next[i] != null && temp.next[i].value < value) {
temp = temp.next[i];
}
update[i] = temp;
}
//把插入节点的每一层连接起来
for (int i = 0; i < level; i++) {
newNode.next[i] = update[i].next[i];
update[i].next[i] = newNode;
}
//判断是否需要更新跳跃表的层数
if (level > levelCount) {
levelCount = level;
}
size++;
System.out.println(value + " 插入成功");
}
public void delete(int value) {
Node[] update = new Node[levelCount];
Node temp = head;
for (int i = levelCount - 1; i >= 0; i--) {
while (temp.next[i] != null && temp.next[i].value < value) {
temp = temp.next[i];
}
update[i] = temp;
}
if (temp.next[0] != null && temp.next[0].value == value) {
size--;
System.out.println(value + " 删除成功");
for (int i = levelCount - 1; i >= 0; i--) {
if (update[i].next[i] != null && update[i].next[i].value == value) {
update[i].next[i] = update[i].next[i].next[i];
}
}
}
}
//打印所有节点
public void printAllNode() {
Node temp = head;
while (temp.next[0] != null) {
System.out.println(temp.next[0].value + " ");
temp = temp.next[0];
}
}
//模拟抛硬币
private int getLevel() {
int level = 1;
while (true) {
int t = (int)(Math.random() * 100);
if (t % 2 == 0) {
level++;
} else {
break;
}
}
System.out.println("当前的level = " + level);
return level;
}
//测试数据
public static void main(String[] args) {
SkipList list = new SkipList();
for (int i = 0; i < 6; i++) {
list.insert(i);
}
list.printAllNode();
list.delete(4);
list.printAllNode();
System.out.println(list.find(3));
System.out.println(list.size + " " + list.levelCount);
}
}
Если вы считаете, что это хорошо, пожалуйста, поставьте лайк, чтобы больше людей увидели эту статью, я благодарен.
Наконец, продвигайте мой публичный аккаунт:трудолюбивый кодер, статьи сначала будут публиковаться на моем официальном аккаунте.На официальном аккаунте более 100 оригинальных статей, и я с нетерпением жду внимания и общения героев из всех слоев общества.