структура данных

Линейная структура:

Массивы, очереди, связанные списки, стеки

Нелинейная структура:

Двумерный массив, многомерный массив, обобщенная таблица, древовидная структура, графовая структура

структура данных:

Массив, связанный список, стек, очередь, хэш-таблица, двоичное дерево, куча, таблица переходов, граф, Trie-книга

множество

Массив (массив) представляет собойлинейныйструктура данных. он использует наборнепрерывное пространство памяти, чтобы хранить группу данных одного типа.

Тогда посмотрите на данные линейного типа структуры↓: все они следуютпервым пришел-первым вышелправило.

Добавить описание:Стек является первым пришел последним

Массив тематической регрессии

Запрос

Когда мы случайным образом обращаемся к определенному значению массива: (временная сложность O (1))

a[i]_address = base_address + i * data_type_size

a[i][j]_address = base_address + ( i * n + j) * type_size

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

вставлять

Мы хотим вставить часть данных в k-ю позицию в массиве. Чтобы освободить k-ю позицию для новых данных, нам нужно переместить элементы частей с k-й по n-ю на один бит назад по порядку.

(Временная сложность в среднем составляет O(n), в лучшем случае O(1), в худшем случае O(n)).

Вопрос: Вставка значения в указанную позицию массива, оптимальное время?

Идея: поставить C в конце и X в этой позиции

Удалить

При фактическом удалении элементов массива данные необходимо перемещать для обеспечения непрерывности памяти.

Идея продления удаления:

В массиве a[10] хранится восемь элементов: a, b, c, d, e, f, g, h. Теперь мы хотим удалить три элемента a, b, c по очереди.

Чтобы избежать трехкратного перемещения данных d, e, f, g и h, мы можем сначала записать удаленные данные.

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

связанный список

структура:

   

1) Связанный списокУзел способ хранения, это цепное хранилище

2) Каждый узел содержитполе данных,следующее поле: указать на следующий узел.

3) Как показано на рисунке:Обнаружено, что каждый узел связанного списка не обязательно хранится непрерывно.
4) Связный список делится на связанный список с головным узлом и связанный список без головного узла, который определяется по фактическим потребностям

Единый список

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

Указатель преемника хвостового узла указывает на пустой нулевой адрес.

Вставка и удаление односвязного списка:

вставлять: сначала найдите предыдущий узел (B) в позиции, которую нужно вставить, хвостовой узел x указывает на c, а хвостовой узел b указывает на x

Удалить: Найдите предыдущий узел (a) удаляемого узла, прямо укажите на c из хвостового узла a, а B не будет указывать и будет переработан jvm.

(Преимущество односвязного списка перед массивом в том, что он быстрее вставляет и удаляет элементы, не нужно перемещать большое количество элементов, достаточно изменить точку указателя

Тогда временная сложность вставки и удаления головы и хвоста равна O(1), а временная сложность запроса, вставки и удаления указанной позиции равна O(n))

Круговой связанный список

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

Вопрос: Как определить, является ли связанный список круговым связанным списком?

Идея: если это круговой связанный список, установите две переменные, быструю и медленную, и одновременно проходя по быстрой, вы догоните медленную.

Двусвязный список

• Указывает на адрес предыдущего узла (указатель-предшественник prev) и адрес следующего узла (указатель-преемник next)

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

вставлять:

Поместите x между a и b, укажите предыдущую часть x на следующую из a и укажите следующую часть a на предыдущую часть x.

(Точно так же, как и при рукопожатии, левая рука x тянется к правой руке a, а правая рука a также тянется к левой руке x, это считается удачным удерживанием за руку.)

Тогда следующий из x указывает на предыдущий из b, а предыдущий из b указывает на следующий из x.

Удалить:

Чтобы удалить элемент B

элемент ВПредыдущий**** следующего узла указывает наПредыдущий узел элемента B ** (элемент A) следующий**

элемент Вследующий из предыдущего узла направление**(элемент C) предыдущий** следующего узла элемента B

затем отпустите элемент B

Есть две ситуации, в которых часть данных удаляется из связанного списка:

1. Удалить узел со значением, равным XX, вам нужно пройти сравнение, а затем удалить операцию указателя, временная сложность O (n)
2. Удалить узел, на который указывает данный указатель:

При удалении односвязного списка вам нужно знать, что такое предыдущий узел n, и проходить его с самого начала, пока p>next=n

Затем укажите найденный узел на следующий узел из n, а временная сложность будет равна O(n). Когда двусвязный список удаляется, он имеет предыдущий узел и задний узел, а временная сложность равна O (1).

куча

Стек представляет собой линейную таблицу с «запрещенными операциями», то есть способом нажатия маркеров, разрешенным только водин конецВставка и удаление данных. (First-in, last-out) Эквивалентно массиву или связанному списку, открывающему слишком много операционных интерфейсов, операция действительно гибкая, но более неконтролируемая при использовании и, естественно, более подвержена ошибкам.

Сценарии применения

1. Вызов подпрограммы: перед переходом к подпрограмме адрес следующей инструкции будет сохранен в стеке, а затем адрес будет извлечен после выполнения подпрограммы и возврата в исходную программу.

2. Обработка рекурсивных вызовов: аналогична вызовам подпрограмм, за исключением того, что помимо хранения адреса следующей инструкции в стеке также хранятся такие данные, как параметры и переменные области.

3. Преобразование выражений и оценка

4. Обход бинарного дерева

5. Графический метод поиска в глубину

пропустить стол

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

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

Динамическое обновление индекса:

Когда мы вставляем данные в таблицу пропуска, мы можем одновременно вставлять эти данные в часть индексного слоя. Таблица пропуска использует случайную функцию, чтобы решить, в какой уровень индексов вставить этот узел.Например, если случайная функция генерирует значение K, то этот узел добавляется к индексу уровня K с первого уровня на уровень K. .

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

Конечно, есть и другие причины, по которым Redis использует таблицы переходов для реализации упорядоченных коллекций, например:

• Таблицы пропуска легче кодировать. Его легче понять и написать, чем красно-черное дерево, а простота означает лучшую читабельность и меньшую подверженность ошибкам.

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

очередь

первым пришел-первым вышелПолитика FIFO (первым пришел, первым ушел)

1. Сама очередь естьупорядоченный список, реализация массива или связанного списка, если структура массива используется для хранения данных очереди, объявление массива очереди показано на рисунке ниже, где maxSize — максимальная емкость очереди.

2. Поскольку выходные и входные данные очереди обрабатываются с передней и задней сторон соответственно, для записи индексов передней и задней частей очереди необходимы две переменные front и back соответственно. , а задняя часть изменится при вводе данных. измените, как показано на рисунке:

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

Хеш-таблица

Давайте сначала рассмотрим массивы и связанные списки.Запросы массива просты, но вставка и удаление сложны; запросы связанного списка сложны, но вставка и удаление просты.

Затем хеш-таблица: вставка и удаление запросов легко;

значение:

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

Эта функция отображения называется хэш-функцией.

Массив записей называется хеш-таблицей.

Хэш-функция:

• **хеш(ключ):** где ключ представляет значение ключа элемента, а значение хеш(ключ) представляет собой хеш-значение, вычисленное хэш-функцией.

• хранимая процедура: сопоставьте ключ значения элемента с индексом с помощью хеш-функции, а затем сохраните данные в позиции соответствующего индекса в массиве.

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

Основные требования к дизайну хэш-функции:

1. Хеш-значение, вычисляемое хэш-функцией, является неотрицательным целым числом, поскольку индекс массива начинается с 0;

2. Если ключ1 = ключ2, то хеш(ключ1) == хеш(ключ2);

3. Если ключ1 ≠ ключ2, то хеш(ключ1) ≠ хэш(ключ2).

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

Часто используемые решения для коллизии хэшей:

Открытая адресация и связанный список

1. открытая адресация

Когда происходит коллизия хэшей, переопределяйте свободное место и вставляйте его

⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ①Линейное обнаружение

Вставить данные в хеш-таблицу:

Размер хэш-таблицы равен 10, и 6 элементов были вставлены в хэш-таблицу до того, как элемент x будет вставлен в хэш-таблицу. После алгоритма Hash x хешируется до позиции с индексом 7, но в этой позиции уже есть данные, поэтому возникает конфликт.

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

Данные запроса хеш-таблицы:

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

Данные удаления хеш-таблицы:

Операция удаления немного особенная. Мы не можем просто сделать удаляемый элемент пустым. Это приведет к сбою исходного алгоритма поиска. Данные, которые изначально существовали, будут считаться несуществующими. Чтобы решить эту проблему, вы можете удалить элемент,Специально помечено как удаленное. При линейном поиске, если он встречает пробел, помеченный как удаленный, он не останавливается, а продолжает поиск.

②Вторичное обнаружение

Не используйте только хеш-функцию. Вместо этого используйте набор хэш-функций hash1 (ключ), hash2 (ключ), hash3 (ключ)...

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

③ Двойной хэш

Подобно линейному обнаружению, размер шага каждого обнаружения линейного обнаружения равен 1, тогда последовательность нижних индексов, которую он обнаруживает, равна

    решётка(ключ)+0, решётка(ключ)+1, решётка(ключ)+2…

Размер шага обнаружения вторичного обнаружения становится исходным «квадратичным», а последовательность индексов его обнаружения — хеш (ключ) + 0, хеш (ключ) + 1, хэш (ключ) + 2 ...

Вышеупомянутый метод открытой адресации, тогда есть проблема с открытым методом адресации:

Когда в хэш-таблицу вставляется все больше и больше данных, вероятность коллизии хэшей будет становиться все больше и больше, свободного места будет все меньше и меньше, а время обнаружения будет все больше и больше.

В крайних случаях нам может понадобиться проверить всю хэш-таблицу, поэтому временная сложность в наихудшем случае составляет O(n).

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

Чтобы обеспечить максимальную эффективность работы хеш-таблицы, в целом мы постараемся сделать все возможное, чтобы в хеш-таблице была определенная доля свободных слотов. Мы используем **коэффициент загрузки**, чтобы указать количество вакансий.

** ** Коэффициент загрузки хеш-таблицы = количество элементов, заполненных в таблице / длина хеш-таблицы**

Чем больше коэффициент загрузки, тем меньше свободного места, тем больше конфликтов и производительность хеш-таблицы будет снижаться. Когда коэффициент загрузки слишком велик, необходимоДинамическое расширение, перемещение данных требует пересчета места хранения каждых данных с помощью хэш-функции.

1. метод связанного списка

• В хеш-таблице каждому «сегменту» или «слоту» будет соответствовать связанный список,

• Все элементы с одинаковым значением хеш-функции помещаются в связанный список, соответствующий одному и тому же слоту.

• При вставке нам нужно только вычислить соответствующий хэш-слот с помощью хэш-функции и вставить его в соответствующий связанный список, поэтому временная сложность вставки составляет O(1).

• При поиске и удалении элемента мы также вычисляем соответствующий слот с помощью хеш-функции, а затем просматриваем связанный список для поиска или удаления. Временная сложность этих двух операций пропорциональна длине k связанного списка, которая равна O(k). Теоретически для хэш-функции с относительно однородным хэшем k=n/m, где n представляет количество данных в хэше, а m представляет количество «слотов» в хеш-таблице.

• Мы преобразуем связанный список в методе связанного списка в другие эффективные динамические структуры данных, такие как списки пропуска и красно-черные деревья. Таким образом, даже если возникает конфликт хэшей, в крайних случаях все данные хешируются в одну и ту же корзину, а время поиска окончательной вырожденной хеш-таблицы составляет всего O(logn). Это может эффективно избежать атак столкновений хэшей.

Сравнение методов разрешения хэш-коллизий

Открытая адресация против метода связанного списка

Данные в хеш-таблице с открытой адресацией хранятся в массиве, который может эффективно использовать кэш ЦП для ускорения запроса и относительно прост для сериализации. При удалении данных необходимо специально помечать удаляемые данные, все данные хранятся в массиве, а стоимость разрешения конфликтов высока, верхний предел коэффициента загрузки не может быть слишком большим. Этот метод тратит больше памяти, чем метод связанного списка.

Так когдаКогда объем данных относительно невелик, а коэффициент загрузки невелик, целесообразно использовать метод открытой адресации..

Метод обработки конфликтов хэшей на основе связанного списка больше подходит для хранения хеш-таблиц с большими объектами и большими объемами данных, кроме того, по сравнению с методом открытой адресации он более гибкий и поддерживает больше стратегий оптимизации, таких как замена связанных списков на красно-черные деревья.

бинарное дерево

• Высота: самый длинный путь от узла к конечному узлу (количество ребер).

• Глубина: отслеживает количество ребер, пройденных узлом до этого узла.

• Уровень: глубина узла +1

• высота дерева: высота корневого узла

Полное бинарное дерево:

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

Полное бинарное дерево:

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

Обход бинарного дерева:

• Обход в прямом порядке, обход в обратном порядке и обход в обратном порядке

• Обход в прямом порядке означает, что для любого узла в дереве сначала печатается узел, затем печатается его левое поддерево и, наконец, печатается его правое поддерево.

•

• Обход по порядку означает, что для любого узла в дереве сначала печатается его левое поддерево, затем печатается само себя и, наконец, печатается его правое поддерево.

•

• Обход в обратном порядке означает, что для любого узла в дереве сначала печатается его левое поддерево, затем правое поддерево и, наконец, печатается сам узел.

Бинарное дерево поиска

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

Запрос

public class BinarySearchTree {
        private Node tree;
        public Node find(int data) {
            Node p = tree;
            while (p != null) {
                if (data < p.data) p = p.left;
                else if (data > p.data) p = p.right;
                else return p;
            }
            return null;
        }
        public static class Node {
            private int data;
            private Node left;
            private Node right;
        }
  }

вставлять

Если значение узла совпадает со значением новых данных во время процесса вставки, новый узел следует рассматривать как значение, превышающее его, то есть поместить его в правильный узел.

public void insert(int data) {
 if (tree == null) {    tree = new Node(data);     return;     }
 Node p = tree;
 while (p != null) {
     if (data > p.data) {
         if (p.right == null) {
             p.right = new Node(data);
             return;
         }
         p = p.right;
     } else { // data < p.data
         if (p.left == null) {
            p.left = new Node(data);
            return;
         }
     p = p.left;
 }
}
}

Удалить

• Три случая удаления: нет дочернего узла, только один дочерний узел и два дочерних узла.

Если под удаленным узлом есть дочерний узел, то на эту позицию помещается узел с наименьшим дочерним узлом.

public void delete(int data) {
     // p 指向要删除的节点，初始化指向根节点
      Node p = tree; 
     // pp 记录的是 p 的父节点
      Node pp = null;  
      while (p != null && p.data != data) {
          pp = p;
          if (data > p.data) p = p.right;
          else p = p.left;
      }
     if (p == null) return; // 没有找到
      // 要删除的节点有两个子节点
     if (p.left != null && p.right != null) { 
         // 查找右子树中最小节点
         Node minP = p.right;
          Node minPP = p; // minPP 表示 minP 的父节点
          while (minP.left != null) {
              minPP = minP;
              minP = minP.left;
          }
          // 将 minP 的数据替换到 p 中
           p.data = minP.data;
           // 下面就变成了删除 minP 了
           p = minP; 
           pp = minPP;
      }
 // 删除节点是叶子节点或者仅有一个子节点
      Node child; // p 的子节点
      if (p.left != null) child = p.left;
      else if (p.right != null) child = p.right;
      else child = null;
      if (pp == null) tree = child; // 删除的是根节点
      else if (pp.left == p) pp.left = child;
      else pp.right = child;
}

Отметить для удаления:

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

Листинг бинарного дерева VS

Временная сложность операций вставки, удаления и поиска в хэш-таблице может быть постоянным уровнем O (1).

В случае сбалансированного бинарного дерева поиска временная сложность операций вставки, удаления и поиска составляет O(logn).

Во-первых, данные в хеш-таблице хранятся не по порядку, если вы хотите вывести упорядоченные данные, вам нужно сначала их отсортировать. Для бинарного дерева поиска нам нужен обход по порядку только для вывода упорядоченной последовательности данных с временной сложностью O(n).

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

В-третьих, хотя временная сложность таких операций, как поиск в хеш-таблице, постоянна, из-за существования коллизий хэшей эта константа не обязательно меньше, чем logn, поэтому фактическая скорость поиска не обязательно может быть выше, чем O(logn). Помимо трудоемкости хеш-функции, она не обязательно более эффективна, чем сбалансированное двоичное дерево поиска.

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

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

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

баланс бинарного дерева

АВЛ-дерево: для каждого узлаАбсолютное значение разницы высот между левым и правым поддеревьями не превышает 1И оба левые, так и правые поддельники являются сбалансированным бинарным деревом.

Зачем балансировать бинарное дерево?

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

Полное бинарное дерево и полное бинарное дерево являются сбалансированными бинарными деревьями.

повернуть влево, повернуть вправо

** Итак, на каком основании мы решаем, следует ли вращаться влево или вправо? ** Приближается важный фактор

коэффициент баланса

• Разница между высотой (глубиной) левого поддерева и правого поддерева узла является коэффициентом баланса (BF, Balance Factor) узла.

Коэффициент баланса всех узлов в сбалансированном бинарном дереве может быть только -1, 0 или 1.

Когда коэффициент баланса BF корневого узла минимального несбалансированного дерева больше 1, оно правостороннее.

Когда коэффициент баланса BF корневого узла минимального несбалансированного дерева меньше -1, оно является левосторонним.

После вставки узла, когда БФ наименьшего неуравновешенного поддерева находится напротив БФ его поддерева, необходимо один раз повернуть узел, чтобы знак совпал, а затем повернуть в обратную сторону, чтобы завершить операцию балансировки.

красно-черное дерево

Красно-черное дерево — это рыхлое приблизительно сбалансированное сбалансированное бинарное дерево поиска.

резюме:

• Корневой узел черный

• Каждый конечный узел является черным пустым узлом (NIL), конечный узел не хранит данные (устанавливается для реализации кода)

• Никакие соседние узлы не могут быть одновременно красными, красные узлы разделены черными узлами.

• Каждый узел, все пути от этого узла к его достижимым листовым узлам содержат одинаковое количество черных узлов.

А как насчет красно-черных деревьев по сравнению с деревьями AVL?

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

Высота примерно логина. Таким образом, высота черного дерева не превышает log2n, а высота положиния красного узла назад не превышает 2log2n

Вывод: высота красно-черного дерева всего в два раза превышает высоту дерева AVL, и снижение производительности незначительное. Однако стоимость поддержания баланса ниже, чем у дерева AVL. Следовательно, производительность поиска, вставки и удаления красно-черного дерева относительно стабильна.

Реализация красно-черного дерева

• Никакие соседние узлы не могут быть одновременно красными, красные узлы разделены черными узлами.

• Каждый узел, все пути от этого узла к его достижимым листовым узлам содержат одинаковое количество черных узлов.

Применение красно-черных деревьев

• 1. В STL, широко используемом в C++, и Map, и Set реализованы с красно-черными деревьями;

• 2. Известный планировщик процессов Linux Completely Fair Scheduler использует красно-черное дерево для управления блоком управления процессом.Область виртуальной памяти процесса хранится в красно-черном дереве, и каждой области виртуального адреса соответствует к узлу красно-черного дерева, левый указатель указывает на соседнее адресное виртуальное пространство памяти, а правый указатель указывает на соседнее старшее адресное виртуальное адресное пространство;

• 3. Реализация мультиплексирования ввода-вывода epoll использует красно-черное дерево для организации и управления sockfd для поддержки быстрого добавления, удаления, модификации и проверки;

• 4. В Nginx для управления таймером используется красно-черное дерево, так как красно-черное дерево упорядочено, можно быстро получить таймер с наименьшим расстоянием;

• 5. Реализация TreeMap на Java;

B-дерево

B-дерево — это сбалансированное дерево поиска с несколькими ответвлениями, что означает, что может быть открыто не более m ответвлений (m>=2), Мы называем его b-деревом m-порядка.

B-дерево m-порядка удовлетворяет следующим условиям:

1. У корневого узла есть как минимум два потомка;

2. Каждый узел дерева содержит не более m дочерних элементов, кроме корневого узла и листового узла, остальные узлы имеют не менее [ceil(m / 2) (представляющее функцию взятия верхнего предела)] дочерних элементов, если Когда узел не является конечным узлом, он имеет как минимум двух дочерних элементов (кроме корневого узла без дочерних элементов).

3. Если узел имеет n-1 ключевых слов, то узел имеет n ветвей. Ключевые слова n-1 не равны друг другу и расположены в порядке возрастания. Количество ключевых слов j, содержащихся в каждом некорневом узле, удовлетворяет условию: ceil(m / 2) - 1

4. Все конечные узлы отображаются в одном слое, а конечные узлы не содержат никакой информации о ключевых словах;

B-дерево нескольких порядков

• Каждый внутренний узел: n — количество ключевых слов в узле, ki — ключевое слово узла и ki

M=B-дерево 5-го порядка:

В+ дерево

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

1. Узел с n поддеревьями содержит n ключевых слов (также считается n-1 ключевыми словами).

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

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

Разница между B-деревом и B+ деревом

• Каждый узел B-дерева хранит данные, и все узлы составляют дерево. Дерево B+ имеет только листовые узлы для хранения данных (в числе B+ есть два указателя головы: один указывает на корневой узел, другой указывает на листовой узел с наименьшим ключевым словом), листовые узлы содержат все данные дерева B+. дерево, и все конечные узлы используют связанные списки. Связанные для облегчения интервального поиска и обхода, а все нелистовые узлы играют роль индекса.

• Ключевые слова, содержащиеся в листовых узлах B-дерева, и ключевые слова, содержащиеся в других узлах, не повторяются.Элемент индекса B+дерева содержит только самое большое ключевое слово соответствующего поддерева и указатель на поддерево и не содержит содержать соответствующую запись ключевого слова адрес хранения.

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

соответствующие преимущества

Преимущества B-деревьев:

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

Преимущества дерева B+:

• Поскольку дерево B+ не содержит информации о внутренних узлах, в страницах памяти может храниться больше ключей. Данные хранятся более тесно и имеют лучшую пространственную локализацию.

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

Зачем использовать дерево B+ в качестве индекса базы данных?

•Наши данные в MySQL вообще размещаются на диске.При чтении данных обязательно будет операция по доступу к диску.В диске есть две части механического движения,а именно вращение диска и движение магнитная рука. Вращение диска — это количество оборотов в минуту, указанное на рынке, а движение диска — чтение и запись данных после того, как диск повернется в указанное положение и будет перемещен магнитный рычаг. Затем идет процесс нахождения блока на диске, а позиционирование — это блок, доступ к диску которого занимает относительно много времени, ведь время, затрачиваемое на механическое движение, гораздо больше, чем на электронное. Когда крупномасштабные данные хранятся на диске, очевидно, что позиционирование — это очень трудоемкий процесс, но мы можем оптимизировать его через B-дерево, чтобы повысить эффективность позиционирования при чтении с диска.

•

• Почему деревья B-типа можно оптимизировать? Мы можем построить дерево B-типа с несколькими порядками в соответствии с характеристиками дерева B-типа, а затем сохранить соответствующую информацию о как можно большем количестве узлов, чтобы количество слоев было как можно меньше, чтобы мы могли быстрее находить информацию позже, дисковые операции ввода-вывода также меньше, а дерево B-типа является сбалансированным деревом, а высота каждого узла до конечного узла одинакова, что также обеспечивает стабильность каждого запроса.

•

• В целом B+-дерево представляет собой сбалансированное многоканальное дерево поиска, предназначенное для дисков или других устройств хранения (по сравнению с двоичным, B-дерево имеет несколько ветвей на каждый внутренний узел), по сравнению с красно-черным деревом. узел, высота дерева B/B+ намного меньше высоты красно-черного дерева (упомянутого в анализе производительности дерева B/B+ ниже). Время работы дерева B/B+ обычно складывается из времени доступа к диску и времени вычислений процессора, а скорость процессора очень высока, поэтому эффективность работы дерева B зависит от количества обращений к диску, а общее количество ключевых слов одинаково.Чем ниже высота B-дерева, тем меньше времени требуется для дискового ввода-вывода.

куча

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

• Значение каждого узла в куче должно быть больше или равно (или меньше или равно) значению каждого узла его поддерева.

•

Куча с большой вершиной: значение каждого узла больше или равно значению каждого узла в поддереве (1, 2)

Маленькая верхняя куча: значение каждого узла меньше или равно значению каждого узла в поддереве (3, 4)

как реализовать кучу

Реализация массива, индекс массива i :

• Левый дочерний индекс i * 2

• Правый дочерний индекс i * 2 + 1

• Нижний индекс родительского узла i / 2

Преимущества реализации массива: экономия места, не нужно хранить указатели на левый и правый дочерние узлы, поиск по индексу.

(Это то, о чем я говорил ранее, почему существует особая структура бинарного дерева, такая как полное бинарное дерево)

Вставка кучи

1. Вставить в конец массива

2. Heapify (heapify): настроить расположение данных так, чтобы оно снова удовлетворяло характеристикам кучи

Нагромождение: следуйте по пути узла, сравните его вверх или вниз, а затем поменяйте местами.

Корректировка снизу вверх: каждое сравнение с родительским узлом, замена

Настраивайте сверху вниз: каждый раз сравнивайте с дочерними узлами, меняйте местами

Например реализация кода:

удаление кучи

Код

Накопление временной сложности

Полное бинарное дерево с n узлами высотой не более log2n. Куча вставки и удаления сравнивается и обменивается по пути, где находится узел, поэтому временная сложность пропорциональна высоте дерева, которая составляет O (logn).

сортировка кучей

• Временная сложность: O(n logn)

• Алгоритм сортировки на месте (не требуется дополнительное вспомогательное пространство или требуется очень мало)

Два шага сортировки кучи:

1. Создайте кучу

2. Сортировать

Сортировка кучей — создание кучи

Есть два способа построить кучу:

• 1. Создайте новый массив кучи и последовательно выполните операции вставки кучи и восходящего кучи над исходным массивом;

• 2. В исходном массиве начните с последнего неконечного элемента, чтобы выполнить операцию кучи сверху вниз.

приложение кучи

• Очередь: первым пришел первый вышел

• Приоритетная очередь: первый обслужен с высоким приоритетом

• Очередь с приоритетом, реализованная кучей: верхний элемент кучи выходит первым

• Использование: кодирование Хаффмана, кратчайшие пути в графах, алгоритмы минимального остовного дерева.

• Планировщик задач в системе заданий

• Приоритизировать запросы от пользователей высокого уровня (сообщения, задания...)

• очередь приоритетов RabbitMQ

• Java PriorityQueue

• C++ Priority_Queue

• Топ k лидеров

静态数据排行：包含n个数据的数组中，查找前k大的数据•维护大小为k的小顶堆，遍历数组元素，与堆顶元素比较，如果大于堆顶元素，则将堆顶元素删除，并插入当前遍历的元素。•遍历复杂度O(n)，堆化复杂度O(logk），总时间复杂度：O(nlogk）动态数据排行：•维护大小为k的小顶堆，添加元素时，与堆顶元素比较，如果大于堆顶元素，则将堆顶元素删除，并插入添加的元素。•时间复杂度：O(logk）

Применение кучи — найти медиану

• Массивы сортируются от меньшего к большему, когда число массивов n нечетно, медиана равна n/2.

• Когда n — четное число, медиана равна n/2 и n/2+1, принимая n/2

• Статические данные: сначала сортируйте, напрямую берите n/2-е данные

• Динамические данные: сортировка неэффективна при каждой вставке данных.

Динамические данные реализованы с кучей:

После сортировки текущего массива сохраняются две кучи:

Большая верхняя куча хранит первую половину данных массива (первые n/2 элементов, когда n нечетно, сохраняются первые n/2+1 элементов)

Маленькая верхняя куча хранит данные во второй половине массива (последние n/2).

В это время верхний элемент большой верхней кучи является медианой.

Общественный номер: На севере Пекина есть рыба