Базовые знания подобны фундаменту здания, они определяют высоту нашей технологии
В интервью много вопросов про деревья, например, вас спросят, каков порядок обхода pre-in-post-order дерева? Трудности заставят вас писать алгоритмические вопросы о деревьях, или некоторые знания о деревьях будут задействованы в собеседованиях по серверной части Java, например, вHashMapПочему связанный список, сгенерированный столкновением хэшей, должен при определенных условиях преобразовываться в красно-черное дерево? , зачем использовать красно-черное дерево вместо дерева B+? Зачем использовать дерево B+ вместо других деревьев для хранения индексов в Mysql и так далее. На самом деле мы все используем эти вещи в процессе ежедневной разработки, на самом деле каждый программист не готов работать каждый день.CRUD, то эти структуры данных на самом деле являются внутренними сильными сторонами.Мы научились анализировать проблемы в повседневной работе, какие наборы выбирать и как их сортировать.У нас будет больше выбора в этих задачах.
что такое дерево
Дерево — это абстрактный тип данных (ADT) или структура данных, которая реализует этот абстрактный тип данных и используется для моделирования набора данных с древовидной структурой. Он состоит из n (n>0) конечных узлов, образующих набор с иерархической взаимосвязью. Его называют «деревом», потому что оно выглядит как перевернутое дерево, что означает, что у него корни вверх, а листья вниз.
Интуитивной диаграммы для полного определения не существует.Давайте сначала взглянем на диаграмму (здесь заимствована диаграмма г-на Ван Чжэна, автора структуры данных и алгоритма, и мы видим тот же стиль диаграммы ниже).
Мы видим, что дерево здесь очень похоже на дерево в нашей реальной жизни, где каждый элемент называется узлом, а отношение, соединенное прямой линией, называется отношением родитель-потомок. Так что же можно назвать деревом?
- Каждый узел имеет только ограниченное количество дочерних элементов или не имеет дочерних элементов.
- Узел без родителя называется корневым узлом.
- Каждый некорневой узел имеет один и только один родительский узел.
- За исключением корневого узла, каждый дочерний узел может быть разделен на несколько непересекающихся поддеревьев.
- В дереве нет петель
Существует множество классификаций деревьев, но мы часто используем бинарные деревья (Дерево, имеющее не более двух поддеревьев на узел, называется бинарным деревом.), как показано на рисунке ниже, на самом деле является бинарным деревом.
В двоичном дереве также будут классификации, из которых ② на приведенном выше рисунке является полным двоичным деревом (За исключением листовых узлов, у каждого узла есть левый и правый дочерние узлы.), приведенный выше рисунок ③ представляет собой полное бинарное дерево (Количество узлов в других слоях достигло максимального значения, а все последние узлы тесно расположены непрерывно слева направо Такое бинарное дерево называется полным бинарным деревом.), где ключевые точки расположены слева направо. Так почему же существует полное бинарное дерево? Здесь задействованы два метода хранения деревьев, один из которых интуитивно понятен — это хранение напрямую связанных списков. Узел Node устанавливает два элемента левого и правого дочерних узлов. код показывает, как показано ниже.
1class TreeNode <T>{
2 public T data;
3 public TreeNode leftNode;
4 public TreeNode rightNode;
5
6 TreeNode(T data){
7 this.data = data;
8 }
9}
Другой способ - хранить на основе порядка массива, мы помещаем дерево из корневого узла в индекс индекса массива 1, а затем помещаем его слева направо.
| серийный номер | положение левого узла | правая позиция узла |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 4 | 5 |
| 3 | 6 | 7 |
| ... | ... | ... |
| n | 2n | 2n-1 |
Здесь, если корневой узел находится в индексе 0, то левый узел равен 2n+1, а правый узел равен 2n+2.
В соответствии с приведенной выше таблицей мы должны получить, что для каждого узла n его позиция левого узла равна 2n, а позиция его правого узла равна 2n+1. Таким образом, мы можем хранить полное бинарное дерево в структуре массива. Если неполное двоичное дерево также хранится в массиве, в середине массива будет много дыр, что приведет к пустой трате памяти.
Преимущество использования массива для хранения данных заключается в том, что нет необходимости хранить указатели на левый и правый дочерние узлы, как в связанном списке, что экономит место.
обход бинарного дерева
Мы вкратце разобрались с определением дерева выше, а затем узнаем об обходе бинарного дерева (обход в прямом порядке, обход в порядке, обход в постпорядке), который также часто задают в интервью.
- Обход в прямом порядке означает, что для любого узла в дереве сначала печатается узел, затем печатается его левое поддерево и, наконец, печатается его правое поддерево.
- Обход по порядку означает, что для любого узла в дереве сначала печатается его левое поддерево, затем печатается само себя и, наконец, печатается его правое поддерево.
- Обход в обратном порядке означает, что для любого узла в дереве сначала печатается его левое поддерево, затем правое поддерево и, наконец, печатается сам узел.
Давайте выразим это более интуитивно в коде.
1/**
2* @Description: 前序遍历
3* @Param: [treeNode]
4* @return: void
5* @Author: hu_pf
6* @Date: 2019/11/26
7*/
8private static void frontOrder(TreeNode<String> treeNode){
9 if (treeNode == null){
10 return;
11 }
12 System.out.printf(treeNode.data);
13 frontOrder(treeNode.leftNode);
14 frontOrder(treeNode.rightNode);
15}
16
17/**
18* @Description: 中序遍历
19* @Param: [treeNode]
20* @return: void
21* @Author: hu_pf
22* @Date: 2019/11/26
23*/
24private static void middleOrder(TreeNode<String> treeNode){
25 if (treeNode == null){
26 return;
27 }
28 middleOrder(treeNode.leftNode);
29 System.out.printf(treeNode.data);
30 middleOrder(treeNode.rightNode);
31}
32
33/**
34* @Description: 后序遍历
35* @Param: [treeNode]
36* @return: void
37* @Author: hu_pf
38* @Date: 2019/11/26
39*/
40private static void afterOrder(TreeNode<String> treeNode){
41 if (treeNode == null){
42 return;
43 }
44 afterOrder(treeNode.leftNode);
45 afterOrder(treeNode.rightNode);
46 System.out.printf(treeNode.data);
47}
бинарное дерево поиска
В бинарном дереве поиска значение каждого узла больше значения левого узла поддерева и меньше значения правого узла поддерева.
Двоичное дерево поиска - это динамическая поддержка добавления, удаления, модификации и поиска данных, и оно по-прежнему естественно упорядочено.Пока мы проходим обход по порядку, полученные данные являются упорядоченными данными.
Вставка в бинарное дерево поиска
Нам нужно только начать с корневого узла и, в свою очередь, сравнить взаимосвязь между вставляемыми данными и узлом. Если вставленные данные больше, чем текущий узел, а в правом узле нет данных, поместите их в правый узел.Если в правом узле есть данные, снова пройдите его правое поддерево. Процесс аналогичен, если вставленные данные меньше, чем текущие данные.
Выражается в коде следующим образом.
1private void insertTree(int data){
2 if (this.rootNode == null){
3 rootNode = new TreeNode(data);
4 return;
5 }
6 TreeNode<Integer> p = rootNode;
7 while (p!=null){
8 Integer pData = p.data;
9 if (data>=pData){
10 if (p.rightNode == null){
11 p.rightNode = new TreeNode(data);
12 break;
13 }
14 p = p.rightNode;
15 }else {
16 if (p.leftNode == null){
17 p.leftNode = new TreeNode(data);
18 break;
19 }
20 p = p.leftNode;
21 }
22 }
23}
Поиск по бинарному дереву поиска
Поиск бинарного дерева относительно прост. Сравните найденные данные с корневым узлом. Если искомые данные меньше его, ищите в левом поддереве, а если искомые данные больше его, ищите в правом поддерево.
1private TreeNode findTreeNode(int data){
2
3 if (this.rootNode == null){
4 return null;
5 }
6
7 TreeNode<Integer> p = rootNode;
8 while (p != null){
9 if (p.data == data) return p;
10 if (data >= p.data) p = p.rightNode;
11 else p = p.leftNode;
12 }
13 return null;
14}
Удаление бинарного дерева поиска
Операция удаления бинарного дерева поиска более сложна, и необходимо рассмотреть три ситуации.
- У удаленного узла нет дочерних узлов: просто удалите его напрямую
- У удаленного узла есть только один узел: ссылка родительского узла может быть заменена его дочерним узлом.
- Удаленный узел имеет два узла: тогда нам нужно подумать об этом, данные левого дочернего узла Переместите узел с самым большим левым дочерним элементом или узел с самым маленьким правым дочерним элементом. Здесь нам всем нужно тщательно его смаковать. Зачем так двигаться.
Чтобы найти узел с наименьшим правым дочерним узлом, просто найдите правый дочерний узел без левого узла, что означает, что узел является самым маленьким.Наоборот, если вы хотите найти узел с самым большим левым дочерним узлом, просто найти левый дочерний узел без правого узла.Узел является самым большим.
Далее смотрим на удаленный код
1private void deleteTreeNode(int data){
2
3 if (this.rootNode == null ) return;
4
5 TreeNode<Integer> treeNode = rootNode;
6 TreeNode<Integer> treeNodeParent = null;
7 while (treeNode != null){
8 if (treeNode.data == data) break;
9 treeNodeParent = treeNode;
10 if (data >= treeNode.data) treeNode = treeNode.rightNode;
11 else treeNode = treeNode.leftNode;
12 }
13
14 // 没有找到节点
15 if (treeNode == null) return;
16
17 TreeNode<Integer> childNode = null;
18 // 1. 删除节点没有子节点
19 if (treeNode.leftNode == null && treeNode.rightNode == null){
20 childNode = null;
21 if (treeNodeParent.leftNode == treeNode) treeNodeParent.leftNode = childNode;
22 else treeNodeParent.rightNode = childNode;
23 return;
24 }
25
26 // 2. 删除节点只有一个节点
27 if ((treeNode.leftNode !=null && treeNode.rightNode==null)||(treeNode.leftNode ==null && treeNode.rightNode!=null)){
28 // 如果此节点是左节点
29 if (treeNode.leftNode !=null) childNode = treeNode.leftNode;
30 // 如果此节点是右节点
31 else childNode = treeNode.rightNode;
32 if (treeNodeParent.leftNode == treeNode) treeNodeParent.leftNode = childNode;
33 else treeNodeParent.rightNode = childNode;
34 return;
35 }
36
37
38 // 3. 删除的节点有两个子节点都有,这里我们演示的是找到右子节点最小的节点
39 if (treeNode.leftNode !=null && treeNode.rightNode!=null){
40 TreeNode<Integer> minNode = treeNode.rightNode;
41 TreeNode<Integer> minNodeParent = treeNode;
42 while (minNode.leftNode!=null){
43 minNodeParent = minNode;
44 minNode = minNode.leftNode;
45 }
46 treeNode.data = minNode.data;
47 if (minNodeParent.rightNode != minNode) minNodeParent.leftNode = minNode.rightNode;
48 else minNodeParent.rightNode = minNode.rightNode;
49 }
50}
Удаленный код более сложен, и здесь есть простой способ сделать это — пометить его для удаления. Таким образом, нет необходимости перемещать данные, и вы можете решить, удалять ли их при вставке данных. Но это займет больше памяти.
Сбалансированное бинарное дерево - красно-черное дерево
Сбалансированное бинарное дерево обладает следующими свойствами: оно является пустым деревом или абсолютное значение разности высот между его левым и правым поддеревьями не превышает 1, причем и левое, и правое поддеревья являются сбалансированным бинарным деревом.
То, о чем мы говорили выше, это поиск бинарного дерева, тогда поиск бинарного дерева может превратиться в связный список в некоторых крайних случаях, поэтому эффективность поиска станет ниже, и сбалансированное бинарное дерево должно решить эту проблему , Дерево выглядит относительно однородным, с примерно одинаковым количеством левых и правых дочерних узлов. Это не превратится в связанный список в крайних случаях. Тогда обычно используемое сбалансированное бинарное деревокрасно-черное дерево.
Я не буду здесь объяснять код, реализованный красно-черным деревом, потому что это слишком хлопотно, расскажу вкратце о сценарии его применения в Java-бэкенде. ДжаваHashMapСтруктура на самом деле представляет собой массив плюс связанный список.Если в слоте слишком много связанных списков, это также повлияет на производительность.Поэтому, когда длина связанного списка равна 8, он будет автоматически преобразован в красный -черное дерево для повышения производительности запросов. Далее я расскажу вам о моментах, которые часто задают красно-черным деревьям в интервью на основе моего собственного интервью.
-
HashMapКогда связанный список будет преобразован в красно-черное дерево?Случай, когда длина связанного списка равна 8 - При каких обстоятельствах красно-черное дерево будет преобразовано в связанный список?Когда узел красно-черного дерева равен 6
- Почему связанный список преобразуется в красно-черное дерево?Ответьте на запрос связанного списка, производительность не очень хорошая
- Почему бы не использовать другое дерево?Ключевым моментом является балансировка дерева, просто отвечайте на преимущества красно-черного дерева.
- почему бы нет
B+Дерево?Ключевые точки, диск, память. Красно-черные деревья в основном используются для внутренней сортировки, то есть все они размещаются в памяти. Когда дерево B+ в основном используется во внешней памяти, дерево B+ также называют структурой данных, удобной для диска.
В обычных условиях интервьюер не даст вам написать красно-черные деревья и тому подобное во время интервью.Наверное, я столкнулся с вышеперечисленными немногими в интервью.Достаточно ответить о преимуществах и сценариях применения красно-черных деревьев.
Сортировка деревьев
Это относится к алгоритму сортировки, разработанному с использованием структуры данных кучи. Куча — это структура, которая аппроксимирует полное бинарное дерево и в то же время удовлетворяет свойству укладки в стопку: то есть значение ключа или индекс дочернего узла всегда меньше (или больше) его родительского узла.
На самом деле, в интервью часто встречаются некоторые алгоритмы сортировки, такие как сортировка кучи или некоторые приложения сортировки кучи, такие как предыдущие данные TopN. По сути, структура кучи — это тоже дерево. Куча — это полное бинарное дерево со следующими свойствами: значение каждого узла больше или равно значению его левого и правого дочерних узлов, которое называется большой верхней кучей; или значение каждого узла меньше или равно значению его левого и правого дочерних узлов, называемому маленькой верхней кучей.
1-й и 2-й — это большая верхняя куча, 3-й — маленькая верхняя куча, а 4-й — не куча. Поскольку куча по сути представляет собой полное двоичное дерево, мы можем использовать массивы для хранения данных кучи. Тогда, если текущий узел равен n, его левый дочерний узел равен 2n, а его правый дочерний узел равен 2n+1.
1class Heap{
2 // 存放堆中的数据，用数组来装
3 private int [] a;
4
5 // 堆中能存放的最大数
6 private int n;
7
8 // 堆中已经存放的数量
9 private int count;
10
11 public Heap(int capacity){
12 a = new int [capacity + 1];
13 this.n = capacity;
14 count = 0;
15 }
16}
Как вставить данные в кучу
Далее, как нам динамически вставлять данные в кучу?
Например, мы вставляем элемент 22 в кучу на рисунке выше, так что же нам делать, чтобы он оставался кучей? В это время куча большой верхней части, которую мы продемонстрировали на рисунке выше, затем мы должны обеспечить концептуальные требования к куче большой верхней части, и значение каждого узла больше или равно значению его левого и правого дочерних узлов. Затем мы помещаем его в последнюю позицию массива, а затем сравниваем его с его родительским узлом (n/2 — его родительский узел), если он больше, чем его родительский узел, меняем позицию с родительским узлом и продолжаем с его родительский узел Сравнение останавливается до тех пор, пока он не станет меньше, чем его родитель. Код реализован следующим образом.
1public void insert(int data){
2 if (count >= n) return;
3
4 count++;
5 // 把数据放到数组中
6 a[count] = data;
7
8 int index = count;
9 // 开始进行比较，先判断跳出条件
10 // 1. 首先能想到的是插入的数据满足了大（小）顶堆的数据要求
11 // 2. 加上极值条件，及是一颗空树情况
12 while (index/2>0 && a[index]>a[index/2]){
13 swap(a,index,index/2);
14 index = index/2;
15 }
16}
17
18private void swap(int [] a, int i , int j){
19 int swap = a[i];
20 a[i] = a[j];
21 a[j] = swap;
22}
Как удалить верхний элемент стека
Мы достигаем максимального или минимального значения до значения корневого узла размера верхней кучи. Затем, если удаляется верхний элемент кучи, то следует выбрать самый большой или самый маленький из левого и правого дочерних узлов и поместить его в корневой узел, и так далее. Затем, если мы будем двигаться в соответствии с тем, что мы только что проанализировали, это может создать дыры в массиве.
Мы можем удалить корневой узел, затем переместить последнее значение массива в корневой узел, а потом сравнивать и менять позиции по очереди, чтобы не было дыр в массиве.
код показывает, как показано ниже
1public void removeMax(){
2
3 if (count == 0) return;
4
5 // 将最后的元素移动到堆顶
6 a[1] = a[count];
7
8 count--;
9
10 heapify(a,count,1);
11}
12
13private void heapify(int [] a,int n,int i){
14 // 定义什么时候结束，当前节点与其左右子节点进行比对，如果当前节点是最大的则跳出循环（代表当前节点已经是最大的）
15 while (true){
16 int maxIndex = i;
17 // 找到三个节点中最大节点的索引值
18 if (2*i<= n && a[i]<a[2*i]) maxIndex = 2*i; // 判断当前节点,是否小于左节点
19 if (2*i+1<= n && a[maxIndex]<a[2*i+1]) maxIndex = 2*i+1;// 判断最大节点是否小于右节点
20 // 如果当前节点已经是最大节点就停止交换并停止循环
21 if (maxIndex == i )break;
22 // 找到中最大值的位置，并交换位置
23 swap(a,i,maxIndex);
24 i = maxIndex;
25 }
26}
сортировка кучей
Как мы используем кучу для сортировки переданного неупорядоченного массива? Итак, поскольку куча используется для сортировки, наш первый шаг должен заключаться в том, чтобы сначала превратить этот массив в структуру кучи.
строить кучу
Как превратить неупорядоченный массив в структуру кучи? Первый, который мы можем легко придумать, — это последовательно вызвать наш метод вставки выше, но используемая память будет удвоена, то есть мы создадим новую память для хранения кучи. Так что, если мы хотим превратить исходный массив в кучу, не добавляя новую память?
Массив здесь не куча, так как же превратить его в кучу? Здесь мы используем метод построения кучи снизу вверх, что это значит? По сути, это идея рекурсии, мы сначала строим кучу внизу, а потом по очереди пропускаем ее вверх. Сначала мы собираем в кучу дерево с номером 4, затем дерево с номером 3, затем дерево с номером 2, а затем дерево с номером 1. действовать последовательно. К концу у нас есть куча. Круги на рисунке ниже представляют размеры его дерева с кучей. код показывает, как показано ниже
1public void buildHeap(int[] a,int n){
2 for (int i =n/2;i>=1;i--){
3 heapify(a,n,i);
4 }
5}
6
7private void heapify(int [] a,int n,int i){
8// 定义什么时候结束，当前节点与其左右子节点进行比对，如果当前节点是最大的则跳出循环（代表当前节点已经是最大的）
9while (true){
10 int maxIndex = i;
11 // 找到三个节点中最大节点的索引值
12 if (2*i<= n && a[i]<a[2*i]) maxIndex = 2*i; // 判断当前节点,是否小于左节点
13 if (2*i+1<= n && a[maxIndex]<a[2*i+1]) maxIndex = 2*i+1;// 判断最大节点是否小于右节点
14 // 如果当前节点已经是最大节点就停止交换并停止循环
15 if (maxIndex == i )break;
16 // 找到中最大值的位置，并交换位置
17 swap(a,i,maxIndex);
18 i = maxIndex;
19}
20}
Сортировать
Сортировка проста, потому что корневой узел кучи является самым большим или самым маленьким элементом, поэтому первое, о чем мы все еще можем думать, это напрямую вынуть значение корневого узла и поместить его в другой массив, а затем удалить верхний. элемент кучи, затем удалите верхний элемент кучи, затем удалите его и так далее. Недостаток этого в том, что он занимает память, потому что мы переопределяем массив, поэтому есть ли способ напрямую отсортировать исходный массив, не занимая память?
Второй способ - не использовать другой массив, как это сделать? Преимущество этого процесса аналогично удалению верхнего элемента кучи. Разница в том, что мы напрямую отбрасываем верхний элемент кучи, чтобы удалить верхний элемент кучи. Для сортировки нам нужно поменять местами верхний элемент и последний элемент кучи.Куча, затем поменять местами верхний элемент кучи с предыдущим элементом последнего элемента, затем снова куча и так далее.
Как найти верхние N данных
Я считаю, что все используют Weibo, так как же в режиме реального времени отображаются десять самых популярных поисковых запросов? На самом деле, первые N данных в основном используются в куче, мы можем создать размер Nнебольшой верхний ворс, если это статические данные, то брать элементы из массива по очереди инебольшой верхний ворсЕсли он больше, чем верхний элемент кучи, то отбрасываем верхний элемент кучи, а затем помещаем элементы массива на вершину кучи, а затем кучи. По порядку окончательный результат — это данные TopN. Если это динамические данные, то они такие же, как и статические данные, и они также постоянно сравниваются. Наконец, если вам нужны данные с большим TopN, вы можете напрямую вернуть эту кучу.
Далее я буду использовать анимацию, чтобы продемонстрировать, как получить данные TopN.
Массив: 1 2 3 9 6 5 4 3 2 10 15
Получить Топ5
Кодовый адрес этой статьи
Если вам интересно, можете обратить внимание на мой новый паблик аккаунт и поискать [Сумка с сокровищами программиста]. Или просто отсканируйте код ниже.